The Idea of Lisp
This article has many misstatements in its first half.<p>&gt; John McCarthy wrote 6 easy things in machine code, then combined them to make a programming language.<p>John McCarthy didn&#x27;t implement Lisp in machine code. Steve Russell did. Implementing Lisp properly in machine code is not easy; you have to write a garbage collector. To do that in the early 60s, you had to first <i>invent garbage collection</i>. Lisp was and is brilliant, but not as easily bootstrappable as this makes it out to be.<p>&gt; It&#x27;s not obvious that these six things are computationally complete (AKA Turing Complete).<p>`lambda` and function application alone are Turing-complete, as McCarthy would have known. The credit here belongs with Turing and Church, not McCarthy. `atom`, `cons`, `car` and all the rest are just icing on the cake of the lambda calculus when it comes to computability.<p>&gt; All other meaning can be defined in terms of them.<p>Yes, and you can build everything on top of the SK combinator calculus if you like, but that doesn&#x27;t make it a good idea. Lisp is <i>surprisingly practical</i> given how few core constructs it has, but real Lisp implementations have always added more primitives (eg. <i>numbers</i> and <i>addition</i>) for reasons of practicality.<p>&gt; The language was defined in terms of itself as an interpreter. This is a proof by construction that the language is computationally complete.<p>No, it isn&#x27;t. To prove Turing-completeness you need to show that you are as powerful as Turing machines. To do this it suffices to show that you can interpret a language already known to be Turing-complete. Showing you can interpret yourself does not suffice. It&#x27;s easy to define a language which can do nothing useful <i>except</i> interpret itself, for example. (See also wyager&#x27;s comment.)<p>&gt; Well, Lisp is defined as an interpreter in terms of itself from the get-go, just like a Universal Turing Machine.<p>No. Defining a language <i>only</i> in itself is nonsense, for exactly the reason given above: it means nothing yet! It&#x27;s like writing in a dictionary:<p><pre><code>   qyzzyghlm, v. intr. To qyzzyghlm.
</code></pre>
It explains nothing unless you already understand it!<p>&gt; Lisp is a universal language because it can interpret its own code. While you can certainly write a JavaScript interpreter in JavaScript, none of the work is done for you.<p>Almost none of the work is done for you in Lisp either. The core of Lisp is just a relatively easy language to implement, while Javascript is a difficult one. Lisp is easy to implement because it has simple syntax (s-expressions) and few core constructs. The only thing that is special about implementing Lisp in Lisp is that Lisp uses s-expressions as its core data structure, so you don&#x27;t have to invent an AST representation. The article, to its credit, explores this idea later.