Steve Yegge: How many primitives does it take to build a LISP machine?

In one of Steve Yegge's awesome essays he says:

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.

So how many primitives do you need? What primitives don't you need? How do we define 'the full machine'? And How do we prove it? Let's go find out. This is going to be fun. 

Assumptions:

For this exercise we'll be working in Common LISP. 

How Many Primitives Do you Need?

How many have you got? This site reckons there are in fact ten. These being

atom, quote, eq, car, cdr, cons, cond, lambda, label, apply

So if Steve reckons we can do it in seven, some of these primitives are going to drop off the essentials list. 

What Primitives Don't You Need?

We don't want to give the game away just yet, but it looks like Paul Graham reckons that McCarthy reckons that apply is the one that drops off. 

How Do We Define 'The Full Machine'?

This is really the crux of the question. (You may even get different answers depending on how you define this.) For this question we'll say that 'the full machine' is a LISP eval function - and we'll use Paul Graham's interpretation of McCarthy's eval function for this. 

How do we Prove it?

We write an eval function - and count the primitives it implements. 

(defun null. (x)
      (eq x '()))

(defun and. (x y)
  (cond (x (cond (y 't) ('t '())))
        ('t '())))

(defun not. (x)
  (cond (x '())
        ('t 't)))

(defun append. (x y)
  (cond ((null. x) y)
        ('t (cons (car x) (append. (cdr x) y)))))

(defun list. (x y)
  (cons x (cons y '())))

(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom x)) (not. (atom y)))
         (cons (list. (car x) (car y))
               (pair. (cdr x) (cdr y))))))

(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list. (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))


(eval '(car '(a a)) )

What's the Answer?

We've already given it away - but it is looking like 9 for Common LISP. 

Are there any bugs in this?

Interestingly enough - this guy @DomQ reckons he emailed Paul Graham with notice of a bug in the code of his original article. Paul Graham's response was that it was actually a bug in McCarthy's code - but that McCarthy wasn't interested in that kind of error handling. You can see a fix for the bug here. 

Could this be improved?

To be truly LISP - you need an eval function that can eval itself. (Something for another day.)

Bibliography:

• Stack Overflow Question