What does it mean that "Lisp can be written in itself?"

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

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 2

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) actually there are two predefined syntax levels in LISP; the first is the syntax of the reader, i.e. defines rules for how source characters are translated into s-expressions, the second define rules of how s-expressions are understood by the compiler when generating actual machine code. But if there are two syntax levels in LISP then why it's correct to say that LISP has no syntax? the reason is that neither them is fixed. The first level for example is handled by the standard common lisp reader using "read tables" that can be customized to have your code executed when a certain character is found in the source code. The second level can be customized using macros, symbol macros and compiler macros and this allow the definition of new syntax constructs. In other words LISP has no fixed syntax and it's possible to write a LISP program that begins as standard LISP and after a while becomes identical to Python (I am not making this up, there is (was) a cl-python implementation that supported exactly this as mixed source mode: anything starting with an open parenthesis was considered using LISP syntax, other characters as Python syntax).

(2) 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.