Monday, November 26, 2007

Origin of CAR and CDR

“It was soon noticed that extraction of a subexpression involved composing the extraction of the address part with cwr and that continuing along the list involved composing the extraction of the decrement part with cwr. Therefore, the compounds car, standing for ``Contents of the Address part of Register number'', and its analogs cdr, cpr, and ctr were defined. The motivation for implementing car and cdr separately was strengthened by the vulgar fact that the IBM 704 had instructions (connected with indexing) that made these operations easy to implement.”
--- John McCarthy, History of Lisp

The IBM 704 was not an early lisp machine.

Greenspun's Tenth Rule of Programming

“Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp.”

This quote is attributed to Philip Greenspun. Lately it seems someone got confused and attributed it to someone else and I'm seeing the misattribution over and over.

Thursday, November 22, 2007

In the Kingdom of Nouns

It is an open secret in the Kingom of Nouns that the King himself has a half-wit, good-for-nothing brother. His name was expunged from the official rolls long ago and everyone calls him null.

null is a true oddity in the Kingdom of Nouns. He is a second-class citizen. This is no doubt due to the fact that he is completely and utterly incapable of even the most trivial of actions. Whenever he is asked to perform a task, he responds by taking Exception and throwing a tantrum. Every other citizen in the Kingdom is expected to at least know his Class and how to present himself to the public. Not null, though.

The residents of the Kingdom take pride in order, so you might imagine that null's behavior would make him an outcast in the Kindom of Nouns. In fact, he had been disinherited by every single family in the kingdom!

null desperately wanted something to do. People would assign him mundane tasks like standing in for a citizen that was shortly expected to arrive or standing at the end of a line as a sort of marker. Occasionally when a request came from the castle, null would return to deliver the news that no one was able to satisfy the request.

Not everyone was impressed by null's `ability' (so to speak) to take up space. Sometimes, you just need a member of the right family or someone that is capable of performing a well-defined task. Requirements like these were spelled out explicitly in the contracts that people made: (TaskManager applicant) or (IMowLawns teenager). But because null was the king's brother, he had a special dispensation to ignore these restrictions. He'd walk right on in and pretend to be the manager or the teenager. Of course as soon as you asked him to do something, like start the mower or even tell you his name, he'd take Exception and throw another tantrum.

Some people just tried to pretend that null didn't exist and hope that the king or somebody would catch him as he threw his tantrum. Others took the time to proofread their contracts and add extra clauses everywhere to exclude null or deal with him in some ad-hoc way.

Unfortunately, there is no happy ending to this story. null continues vex and irritate the citizens of the Kingdom of Nouns and no relief is in sight.

Tuesday, November 20, 2007

Consider this problem. You are running a high school and you suspect some gang activities, so you want to be on the lookout for people wearing gang `uniforms'. But you don't know what any of the uniforms might be. So you watch the students and take note of what they are wearing: some have puffy jackets, some have hoodies, some have t-shirts, some have baggy pants, some have hats that they wear backwards, etc. etc. etc. Over the course of the day, you see a lot of different clothing, a lot of different combinations, and all in different colors. You note, however, that you did see five students wearing purple puffy jackets, baggy pants, and red baseball caps. What is the liklihood that this is a gang uniform? Obviously, it will depend on the size of the student population and the prevalence of certain kinds of clothing, but in the extreme case where you see, say, fifteen students with the *exact* same outfits that match in twenty-seven different random qualities, you can be pretty sure that is a gang. On the other hand, if you see two students that happen to wear the same color puffy jacket and otherwise have nothing in common, you can write that one off as coincidence. So given the number of students and the relative prevalence of various clothing elements, how many points of coincidence do you need to be fairly certain you have found a gang uniform?