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
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
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 Turingcomplete 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 onecombinator basis by Jeroen Fokker. But using a onecombinator basis for computable functions is like reducing classical logic to NAND... interesting, but not practical.)


Ehud Lamm  Re: The Roots of Lisp
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
1/6/2002; 12:44:50 PM (reads: 1139, responses: 0)


I think the benefits of Lisps with respect to selfimplementation are practical ones, rather than theoretical. A builtin reader capable of reading sexps, including Lisp code; the eval and apply functions; the ease of manipulating the liststructured 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 selfimplementation, 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 languageimplementing 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
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 Yoperator, 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".



