A Tangential Discourse on Lisp and the Lineage of Languages
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
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