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

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.