Monday, November 12, 2012


What if you could create one of the first great computer languages with just six "elementary" functions?  Sounds easy doesn't it?  The predicate function ATOM is fairly easy to implement.  The predicate function EQ is perhaps equally as easy.  The CAR and CDR functions are similar enough that once you've built one the other is just the same but opposite.  And, the CONS function can be simple to put together.  But, when you get to the sixth "elementary" function COND you may start to realize that the jig is up.  The following is the "simple" form for COND...


    (condition1   result1 )

    (condition2   result2 )

    . . .

    (T    resultN ))

That seems fairly straight forward, except that it's not.  In fact some of the other elementary functions may assume some not so straight forward back-end details like garbage collection, stacks, and other "implementation" details that one shouldn't worry too much about.  Except when you go to implement them.  And, all of a sudden things grow extra legs.

That COND function has a lot to it that might not jump out immediately.  Each condition is an expression that can be EVALuated.  In theory COND can have an infinite number of condition-result blocks.  If each condition returns False, then COND really starts to look a lot like a procedural program as opposed to the functional nirvana that "functional" languages tout.  In implementing COND, one could use tail call recursion which brings yet another possibly ugly detail to the fore.  COND like an if-else if-else block gone wild is really the engine that drives the language, any language, maybe any program.

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

I've heard that every language and program eventually becomes a Lisp, but if you meditate on COND, you may realize why.  It may be more that every language and program uses some form of COND which provides mechanism for the edge cases for every program.  So, it's not so much that every program becomes Lisp, but more likely that programs can become overly complicated and start to grow extra legs.

Somehow, I feel like I am being conned.

No comments:

Post a Comment