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.

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.

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?

Signs of life

It is showing signs of life. I have gotten to the bootstrap step where we replace the bootstrap version of MAKE-INSTANCE with the generic version. On the next call to MAKE-INSTANCE a lot of stuff happens that eventually lands us in the yet-to-be-implemented primary method of MAKE-INSTANCE.

At this point, I need to clean up a few of the kludges and finish implementing a few of the important functions (for example, my wimpy sort routine only works on lists of a single element so far).

Function Cells in C#

I found this interesting syntactic hack to mimic function cells in C#. Suppose you know the signature and name of a function at compile time, but the value will be computed at runtime and may change over time. First, define a delegate type for the signature of the function:

delegate object FooFunction (string s, int i);

In the class where the function Foo will be defined, we create a static variable to hold the delegate:

static FooFunction currentFooFunction;

and a Property to read it:

public static FooFunction Foo
{
    get
    {
        return currentFooFunction;
    }
}

You can now write code like this:
object bar = Foo("test", 4);
which appears to be an ordinary static function call, but in actuality is a call that indirects through the currentFooFunction.

The basic trick here is to have a Property that returns a delegate. The Property code can perform an arbitrary computation to return the delegate, and the compiler knows that a delegate returned from a Property call can be used in a syntactic function position.

That is my final answer

The IL version had a problem that I didn't notice before. Generic functions need to be closed over themselves. This allows the implementation to store a trampoline function when the generic is created and/or modified. The trampoline function recomputes what code is run when the generic is run, and then smashes itself out of the code path. Subsequent runs of the generic function don't go through the trampoline.

The problem is that the method object held by the .NET delegate is a read-only object. It cannot be overwritten. No problem, we'll just indirect through the field we can write. But we need to pass in the delegate object itself as an argument so we can modify it. In order to do that the delegate method needs access to the this pointer in the delegate. But the point of a delegate is to provide the delegated method with a this pointer. That is the Target field in the delegate. But the target object held by the .NET delegate is also read-only. It isn't possible to construct a delegate that delegates to itself in .NET (at least not without major black magic). We can create a delegate that delegates to a static method within the delegate class itself, but then we no longer have access to the instance object.

The solution is another level of indirection. We create a ManifestInstance class that has mutable state we need and closes over itself. The delegate simply defers to the ManifestInstance. This is the way delegates are intended to be used, so there is no need to use IL to add extra fields or anything. We can do this with standard, simple C#.

But I still want my StandardObjects to be printed with some sort of useful debugging info rather than {Method = {System.Object uninitializedFuncallableInstanceMethod(System.Object[])}}. The StandardObject delegate needs a DebuggerTypeProxy. A DebuggerTypeProxy is a helper object that tells the debugger how to render objects when the standard mechanisms aren't sufficient. But for reasons I don't understand, you can't associate a DebuggerTypeProxy with a .NET delegate! Argh!!!!

But I found a trick. You can associate a DebuggerDisplay attribute with a delegate. This is a string attribute that is interpreted in the context of the object being debugged. You can put things like "Object {Name}" in the DebuggerDisplay attribute and it will print the literal string `Object' followed by the Name field of the object. For our StandardObject delegate, we tell it to print the Target field. This sort of works: "{Target}", but then the debugger uses the ToStringmethod of the ManifestInstance. It makes it hard to visually distinguish the ManifestInstance from the delegate that refers to it. Instead, we want to get a computed property of the ManifestInstance. Unfortunately, this doesn't work: "{Target.ObjectDebuggerDisplay}", but this does: "{((ManifestInstance)Target).ObjectDebuggerDisplay}". Now when the debugger sees a StandardObject, it calls a method defined in ManifestInstance that has access to the object's state.

Since all this can be done in simple C# code, there is no reason to hack IL for StandardObjects. Back to the hacking....