What does it mean that “Lisp can be written in its

Question

Paul Graham wrote that "The unusual thing about Lisp-- in fact, the defining quality of Lisp-- is that it can be written in itself." But that doesn't seem the least bit unusual or definitive to me.

ISTM that a programming language is defined by two things: Its compiler or interpreter, which defines the syntax and the semantics for the language by fiat, and its standard library, which defines to a large degree the idioms and techniques that skilled users will use when writing code in the language.

With a few specific exceptions, (the non-C# members of the .NET family, for example,) most languages' standard libraries are written in that language for two very good reasons: because it will share the same set of syntactical definitions, function calling conventions, and the general "look and feel" of the language, and because the people who are likely to write a standard library for a programming language are its users, and particularly its designer(s). So there's nothing unique there; that's pretty standard.

And again, there's nothing unique or unusual about a language's compiler being written in itself. C compilers are written in C. Pascal compilers are written in Pascal. Mono's C# compiler is written in C#. Heck, even some scripting languages have implementations "written in itself".

So what does it mean that Lisp is unusual in being written in itself?

Answer 1

The main idea is that the language Lisp has a very small kernel of a handful functions and the main evaluation mechanism can be written down in code on a single page.

That's the core of Lisp.

To understand the basic workings of the language it is only necessary to look at that single page of code: it explains how variables work, how function calling works, how new functions can be created, etc.

Just think about how much you can remove from a language implementation to get to the basics. What is the minimum set of primitives and what is the minimum execution engine. To write a Lisp in a Lisp you get down to almost nothing.

If you look at a PASCAL implementation (as an example), it is not implemented in PASCAL, but in PASCAL + a larger amount of code that provides the necessary data structures to represent language entities, a parser, a compiler, a runtime, ... - out of the box PASCAL does not offer much - one has to build these (or use a library).

Wirth (the creator of Pascal) has written a book that explains the implementation of a very small Pascal-like language - you still have to write substantial code to implement that language - parser, code generator, runtime, loader, ...

In contrast, in a Lisp, the Lisp source code has a natural representation and the core routine that evaluates Lisp code is just one Lisp function. This may not a real or practical Lisp implementation, still it is different from the PASCAL situation, where the source code has no useful representation (other than a string or a file) and the execution engine is much more code.

So in Lisp we have:

• a simple representation for source code (lists of symbols)

• a simple implementation of the evaluator in a single small function

Beyond that, nothing is needed to implement a Lisp evaluator in Lisp.

Answer 2

Well, the link you provided does go on to say that, if you continue reading, he will answer your question in detail.

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.

Answer 3

He isn't saying that Lisp can be used to write a Lisp compiler. He's saying that the language is made up from its own data structures. So while you can't build up a C function out of C data structures, you can do that in Lisp. A program is made up of lists that are executed by your computer, and the effect of those lists can be to create other lists that are then executed, and the effect of those lists can be to create still more lists to be executed. C doesn't have this property. C code can't, for example, manipulate its own AST.

Answer 4

Probably what Paul means is that the representation of Lisp syntax as a Lisp value is standardized and pervasive. That is, a Lisp program is just a special kind of S-expression, and it's exceptionally easy to write Lisp code that manipulates Lisp code. Writing a Lisp interpreter in Lisp is a special case, and is not so exciting as the general ability to have a unified representation for both code and data.

Answer 5

I just deleted a very long reply that is probably inappropriate here.

However consider that:

1. LISP has no "syntax" if you mean it with the meaning it has for languages like C/Java/Pascal... there is an (initial but customizable) syntax for the Common LISP reader, but that's a different thing (LISP that Graham is talking about is not Common LISP, and a (the) reader is not the LISP language, but just a procedure). Something like "(lambda (x) (* x 2))" is not LISP code, but text that for example the CL standard reader can convert to LISP code.

2. LISP not only can be written in LISP (if you mean the "bootstrap" ability) but it actually got into existence that way. The very first implementation of eval in late 1950's was written in LISP on paper, and then converted manually into machine language⁽¹⁾: LISP started as a purely theoric idea not meant to be implemented. I know no other computer language that followed that path. For example C++ was conceived as a pre-processor for a C compiler and was written in C, it wasn't a C++ program later converted to C to be able to run it.

There are many other aspects in which LISP is quite different, and I think that the best way to get a grasp of it is to actually implement a toy LISP interpreter (it's a job smaller than one would think especially if your "machine language" is an high-level dynamically typed language like Python).

(1) in http://www-formal.stanford.edu/jmc/history/lisp/node3.html you can find how McCarthy describes that eval[e, a] was found on paper first as an interesting theoretical result (a "universal function" implementation neater than an universal Turing machine) when only the data structures and elementary native functions had been laid out for the Lisp language the group was building. This hand-written function was implemented by hand by S.R. Russell in machine code and started serving them as the first Lisp interpreter.