How many primitives does it take to build a LISP machine? Ten, seven or five?

Question

On this site they say there are 10 LISP primitives. The primitives are: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Stevey reckons there are seven (or five):

Its part of the purity of the idea of LISP: you only need the seven (or is it five?) primitives to build the full machine. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

What is the minimum number of primitives to build a LISP machine (ie something that can run an eval/value function on LISP code)? (And which ones are they?)

(I can understand you could live without atom, label and apply)

Answer 1

Basic Predicates/F-functions

McCarthy's Elementary S-functions and Predicates were:

1. atom

   Which was necessary because car and cdr are defined for lists only, which means you cannot count on any sort of answer to indicate what was happening if you gave car an atom.

2. eq

   For testing equality between atoms.

3. car

   For returning the first half (address) of the cons cell. (Contents of address register).

4. cdr

   For returning the second half (decrement) of the cons cell. (Contents of decrement register).

5. cons

   For making a new cons cell, with the address half containing the first argument to cons, and the decrement half containing the second argument.

Tying it together: S-Functions

He then went on to add to his basic notation, to enable writing what he called S-functions:

1. quote

   To represent an expression without evaluating it.

2. cond

   The basic conditional to be used with the previously described predicates.

3. lambda

   To denote a function.

4. label

   Though he didn't need this for recursion, he might not have known about the Y-Combinator (according to Paul Graham), he added this for convenience and to enable easy recursion.

---

So you can see he actually defined 9 basic "operators" for his Lisp machine. In a previous answer to another one of your questions, I explained how you could represent and operate on numbers with this system.

But the answer to this question really depends on what you want out of your Lisp machine. You could implement one without the label function, as you could simply functionally compose everything, and obtain recursion through applying the Y-Combinator.

atom could be discarded if you defined the car operation on atoms to return NIL.

You could essentially have McCarthy's LISP machine with 7 of these 9 defined primitives, but you could ostensibly define a more concise version depending on how much inconvenience you'd want to inflict on yourself. I like his machine quite fine, or the many primitives in the newer languages like Clojure.

Answer 2

The best way to actually know this for sure is if you implement it. I used 3 summers to create Zozotez which is a McCarty-ish LISP running on Brainfuck.

I tried to find out what I needed and on a forum you'll find a thread that says You only need lambda. Thus, you can make a whole LISP in lambda calculus I you'd like. I found it interesting, but it's hardly the way to go if you want something that eventually has side effects and works in the real world.

For a Turing complete LISP I used Paul Grahams explanation of McCarthy's paper and all you really need is:

• symbol-evaluation
• special form quote
• special form if (or cond)
• special form lambda (similar to quote)
• function eq
• function atom
• function cons
• function car
• function cdr
• function-dispatch (list-lambda)

Thats 10. In addition to this, to have a implementation that you can test and not just on a drawing board:

• function read
• function write

Thats 12. In my Zozotez I implemeted set and flambda (anonymous macroes, like lambda) as well. I could feed it a library implementing any dynamic bound lisp (Elisp, picoLisp) with the exception of file I/O (because the underlying BF does not support it other than stdin/stdout).

I recommend anyone to implement a LISP1-interpreter in both LISP and (not LISP) to fully understand how a language is implemented. LISP has a very simple syntax so it's a good starting point for a parser. I'm currently working on a scheme compiler written in scheme with different targets (like Stalin is for target C), hopefully BF as one of them.