Lambda the Ultimate

inactiveTopic The Roots of Lisp
started 1/4/2002; 5:45:45 AM - last post 1/6/2002; 1:02:51 PM
Ehud Lamm - The Roots of Lisp  blueArrow
1/4/2002; 5:45:45 AM (reads: 2274, responses: 4)
The Roots of Lisp
In this article I'm going to try to explain in the simplest possible terms what McCarthy discovered. The point is not just to learn about an interesting theoretical result someone figured out forty years ago, but to show where languages are heading. The unusual thing about Lisp-- in fact, the defining quality of Lisp-- is that it can be written in itself. To understand what McCarthy meant by this, we're going to retrace his steps, with his mathematical notation translated into running Common Lisp code.

Constructive demonstrations of this sort are always fun.

Paul Graham admits to writing this article to help myself understand exactly what McCarthy discovered.

It may thus be helpful for those considering the still open question.

Posted to history by Ehud Lamm on 1/4/02; 5:47:23 AM

Frank Atanassow - Re: The Roots of Lisp  blueArrow
1/4/2002; 7:57:31 AM (reads: 1202, responses: 1)
The unusual thing about Lisp-- in fact, the defining quality of Lisp-- is that it can be written in itself.

You can do this in any Turing-complete language. I would say that a defining quality of LISP is that the quoting syntax lets you write data which look like what they represent, if they are intended to represent LISP code.

[From the article:] What we have here is a remarkably elegant model of computation. Using just quote, atom, eq, car, cdr, cons and cond, we can define a function, eval., that actually implements our language, and then using that we can define any additional function we want.

You don't need any of that. In particular, quoting is superfluous. You can define everything using variables, lambda and application. Now that's elegant!

(Actually, you don't even need variables or lambda. Every computable function can be expressed using application and a single constant. See The systematic construction of a one-combinator basis by Jeroen Fokker. But using a one-combinator basis for computable functions is like reducing classical logic to NAND... interesting, but not practical.)

Ehud Lamm - Re: The Roots of Lisp  blueArrow
1/4/2002; 8:10:37 AM (reads: 1273, responses: 0)
I knew I could count on you, Frank, to point this out...

Maybe these claim can be substantiated from a historical point of view. I am not sure, but I think Lisp was designed as an attempt to find a notation useful for describing its own evaluator.

Obviously, from a theoretical point of view the results of Turing, Church etc. predate Lisp.

Anton van Straaten - Re: The Roots of Lisp  blueArrow
1/6/2002; 12:44:50 PM (reads: 1139, responses: 0)
I think the benefits of Lisps with respect to self-implementation are practical ones, rather than theoretical. A built-in reader capable of reading s-exps, including Lisp code; the eval and apply functions; the ease of manipulating the list-structured code; and of course, macros, all combine to make Lisps perhaps the language with the lowest barriers to entry in writing other languages. If I wanted to knock together a little language in an afternoon, I'd use Lisp (well, Scheme actually).

Another way to look at it is how much code is required for a language to implement itself. Since the features mentioned above are part of the definition of Lisp, a very small Lisp implementation that provides these basic features is capable of implementing itself. Even if you tried to implement a version of the untyped lambda calculus in itself - which might be smaller - by the time you implement a reader and some of the other necessary capabilities, it would look a lot like Lisp. In terms of the amount of code required for a self-implementation, Lisp would likely be quite far ahead of most other languages, with the possible exception of languages like Forth and Postscript.

If I'm wrong, I'm most interested to know about other languages that would give Lisp serious competition in this area. Perhaps this would be a good candidate for a "shootout"!

Many of the benefits which Lisp provides in this area are upfront benefits. As the language being implemented becomes larger and more complex, Lisp doesn't necessarily provide more language-implementing utility than, say, the typed functional languages. Those are also excellent for implementing languages, but most of them lack at least some of the features that makes this so easy in Lisp, so the initial steps may require a bit more work.

Anton van Straaten - Re: The Roots of Lisp  blueArrow
1/6/2002; 1:02:51 PM (reads: 1158, responses: 0)
Maybe these claim can be substantiated from a historical point of view. I am not sure, but I think Lisp was designed as an attempt to find a notation useful for describing its own evaluator.

"The implementation of LISP" provides McCarthy's own perspective on the issue. A relevant quote:

"Another way to show that LISP was neater than Turing machines was to write a universal LISP function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function eval[e,a], which computes the value of a LISP expression e - the second argument a being a list of assignments of values to variables. (a is needed to make the recursion work). Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice. Logical completeness required that the notation used to express functions used as functional arguments be extended to provide for recursive functions, and the LABEL notation was invented by Nathaniel Rochester for that purpose. D.M.R. Park pointed out that LABEL was logically unnecessary since the result could be achieved using only LAMBDA - by a construction analogous to Church's Y-operator, albeit in a more complicated way.

S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.

Here's another site with some interesting historical info, including copies of the early versions of McCarthy's "universal LISP function". The first two links on the above page are most relevant, with the second link being most detailed in terms of describing where McCarthy was coming from during the development of LISP.

Finally, The Survival of LISP provides a list of ideas which McCarthy considers to characterize LISP. Almost all of these are important to allowing LISP to easily be implemented in itself. In particular, #12 is "The LISP function eval that serves both as a formal definition of the language and as an interpreter".