macros - Given the following LISP eval function - what is required to add defmacro?

Question

Given the following definition of the LISP eval function - what is required to add the defmacro function? (Or even just evaluate a macro)

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

Answer 1

The representation of an anonymous macro is by convention a list of the form (macro lambda ...). Try evaling these in your favorite Lisp interpreter (tested in Emacs):

> (defmacro triple (x) `(+ ,x ,x ,x))

triple

> (symbol-function 'triple)

(macro lambda (x) (` (+ (, x) (, x) (, x))))

Although things don't work that way in Emacs, the only thing left to do is to give the adequate semantics to such a form. That is, when eval. sees ((macro lambda (x) EXPR) FORM), it must

1. Replace every occurence of x in FORM with EXPR without evaluating EXPR first (as opposed to what happens in a function call);
2. eval. the result of above.

You can achieve this by adding a clause to the outermost cond in eval. that deals with the ((macro lambda ...) ...) case. Here is a crude prototype:

((eq (caar e) 'macro)
     (cond
      ((eq (cadar e) 'lambda)
       (eval. (eval. (car (cdddar e))
                     (cons (list. (car (caddar e)) (cadr e)) a))
              a))))

This code only works for single-argument macros. Fixing that involves writing an auxiliary function substlis. that works like evlis. but without looping to eval.; that is left as an exercise to the reader :-)

To test, define cadr. as a macro thusly:

(defmacro cadr. (x)
  (list. 'car (list. 'cdr x)))

After this you would have

> (symbol-function 'cadr.)

(macro lambda (x) (list. (quote car) (list. (quote cdr) x)))

You can construct a form that applies this (macro lambda ...) to an expression, and eval that construction within a context that contains a definition for list. (because it is not considered primitive by the eval. interpreter). For instance,

(let ((e '((macro lambda (x) (list (quote car) (list (quote cdr) x)))
           (cons (quote x) (cons (quote y) nil))))
      (bindings `((list ,(symbol-function 'list.)))))
  (eval. e bindings))

y

Tada!