A Tangential Discourse on Lisp and the Lineage of Languages

Levi Pearson levi at cold.org
Sat Mar 11 16:07:21 MST 2006

On Mar 11, 2006, at 2:08 AM, Daniel C. wrote:

> I was under the impression that Lisp is a glorified lambda calculus in
> the same way that C is a glorified UTM?

Well, if you put it that way, then sure.  But C is nowhere near a  
glorified UTM, though.  Have you ever written anything directly as a  
lambda calculus expression or a turing machine tape?  Although lambda  
calculus is a lot closer to something you might actually want to use  
(especially if you're a mathematician), neither is particularly  
appealing as a practical programming language.

Lisp was influenced by the lambda calculus in its initial creation,  
but its execution model is actually pretty different.  It also looks  
nothing like lambda calculus as it's typically written.  And C is the  
illegitimate child of father Algol and mother PDP-11 assembly, with  
some extra punctuation mixed in (birth defects?).  It's got its  
father's build, but it's a total mama's boy.  It bears no resemblance  
at all to a UTM, aside from the fact that you can prove the two  
theoretically equivalent in the computational problems they can solve.

Lisp is more of a family of languages than one particular language.   
The original LISP, invented by John McCarthy in 1958, was rather  
different than the Lisps of today.  Its design was originally  
published in 1960 as this paper: http://www-formal.stanford.edu/jmc/ 

If you read through that, you'll see that it includes two kinds of  
expressions, s-expressions (which are fully-parenthesized, and the  
native data format) and m-expressions that use brackets and a more  
math-like notation (with the operator on the outside of the  
brackets).  In the years that followed, programmers rejected the m- 
expressions in favor of the s-expressions that make up today's  
Lisps.  Hmm, maybe there's some value to the 'weird' syntax after  
all, eh?

Incidentally, Lisp has had native-code compilers since 1962, and  
incremental ones at that, which let you intermix interpreted and  
compiled code.  Some implementations of Common Lisp today provide no  
interpreter at all, and simply compile every expression you give it  
before executing it.  Having been used for so many years on hardware  
far less powerful than today's, it has very mature and sophisticated  
optimizing compilers.  So, for dynamic applications that require a  
lot of indirection and reflection, Lisp provides excellent  
performance and unparalleled flexibility.

You can also thank Lisp for such things as garbage collection, higher- 
order functions, recursive functions, cheap function calls, and even  
the now-ubiquitous if-then-else construction found in Algol-derived  
languages.  Having pioneered all that stuff, it continues to be an  
experimental platform for new language features and programming  
methodologies due to its extreme flexibility.

I'll close this with a quote from CS luminary Edsger Dijkstra:

Lisp has jokingly been called "the most intelligent way to misuse a  
computer". I think that description is a great compliment because it  
transmits the full flavor of liberation: it has assisted a number of  
our most gifted fellow humans in thinking previously impossible  
— Edsger Dijkstra, CACM, 15:10

If you still want to think of Lisp as a glorified lambda calculus, go  
right ahead, but it's really one of the crowning achievements of  
computer science to date.


More information about the PLUG mailing list