A detailed view of the lisp interpreter (contd...)

In the previous post, I had explained some part of the code for the interpreter. In this post I will first give an explanation for the lambda and label forms and then I will complete the explanation of the interpreter.

The lambda form

The anonymous lambda function has the form,

(lambda (x1 ... xn) expr)

All the xi's represent variables that may be used in the expression expr.

As such, the lambda function as given above is just an abstraction of a function. In order to do something useful with it, you have to execute it by providing it with arguments as,

    ((lambda (x1 ... xn) expr) a1 ... an)

The manner in which the lambda function is evaluated in lisp is by first evaluating all its arguments, i.e., all the ai's. Once all the arguments have been evaluated, the values returned are then bound to the xi's which are used as variables in the expression 'expr'.

An example of the lambda form evaluated in emacs,

    ((lambda (x y) (cons x (cdr y)))
             'a
             '(b c d))    ==> (a c d)

The label form

The label form is a special type of lambda form. While the lambda form is an anonymous function call, the label form allows one to name the expression and then use the name within the expression itself. This feature enables one to define recursive expressions.

The label expression is (label f (lambda (p1 ... pn) e)). It denotes a function that behaves like (lambda (p1 ... pn) e) with the additional property that an occurrence of f within e will evaluate to the label expression as if f were a parameter of the function. Here is an example.

    (label subst (lambda (x y z)
            (cond ((atom z) (cond ((eq z y) x) ('t z))
                   ('t (cons (subst x y (car z))
                             (subst x y (cdr z))))))))

The abbreviation for

 f = (label f (lambda (p1 ... pn) e))

is

 (defun f (p1 ... pn) e) 

Thus, we have,

    (defun subst (x y z)
        (cond ((atom z)  (cond ((eq z y) x) ('t z))
               ('t (cons (subst x y (car z))
                         (subst x y (cdr z))))))))

I have described what the subst function does and how it does it here.

Once again, the interpreter

The lines that are in bold represent the part of the code that I did not explain in the previous post.

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

The lines in bold above represent three cases :

1. (car e) is an atom but is not any of the primitive functions
2. (car e) is a list and (caar e) is 'label
3. (car e) is a list and (caar e) is 'lambda

Let's see how the interpreter handles these cases.

1. (car e) is an atom but is not any of the primitive functions

   The code for this case is given below.

       (eval. (cons (assoc. (car e) a) (cdr e)) a)
   

   In this particular case, the function is a lambda form that is defined in the environment. So, we just obtain the value of the function and evaluate it on its arguments.
   
   An example:

   
       
       (setq e '(f '(b c)))
       (setq a '((f (lambda (x) (cons 'a x)))))
       (eval. e a)        ==>  (a b c)
   
       (assoc. (car e) a) ==>  (lambda (x) (cons (quote a) x))
   
   
   

2. (car e) is a list and (caar e) is 'label

   The code for the label form:

       (eval. (cons (caddar e) (cdr e)) (cons (list (cadar e) (car e)) a))
   

   The label form is transformed into a call to a lambda form since a label is really a lambda form. An example will help you understand,

   
   
       (setq e '((label firstatom 
                   (lambda (x)
                        (cond ((atom x) x)
                        ('t (firstatom (car x))))))
                   y))
   
       (setq a '((y ((z b) (c d)))))
       
       (car e)    ==> (label firstatom (lambda (x) 
                                 (cond ((atom x) x) ((quote t) (firstatom (car x))))))
   
       (caddar e) ==> (lambda (x) (cond ((atom x) x) ((quote t) (firstatom (car x)))))        
   
       ;;The modified environment
       (cons (list (cadar e) (car e)) a)
       ==> ((firstatom 
                (label firstatom (lambda (x) (cond ((atom x) x) ((quote t) (firstatom (car x))))))) 
            (y ((z b) (c d))))
       
       (eval. e a)
   
   

3. (car e) is a list and (caar e) is 'lambda

   The code for lambda form

       (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))
   

   The expression for a lambda form is transformed into another eval. call where the expression is (caddar e) and the environment is (append. (pair. (cadar e) (evlis. (cdr e) a)) a). Let's first have a look at the evlis. function

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

   The evlis. function is used in the code for the lambda form. This function is given a list of expressions, 'm', as input and it returns a list of the results of evaluating each expression in the list.
   
   

   
       (eval. '((lambda (x y) (cons x (cdr y)))
                 'a
                 '(b c d))
              '())                           ==>     (a c d)
   
   
       (setq e '((lambda (x y) (cons x (cdr y)))  'a  '(b c d)))
   
       (setq a '())
   
       (car e)     ==>  (lambda (x y) (cons x (cdr y)))
   
       (cdar e)    ==>  ((x y) (cons x (cdr y)))
   
       (cddar e)   ==>  ((cons x (cdr y)))
   
       (caddar e)  ==>  (cons x (cdr y)) 
   
       (evlis. (cdr e) a)     ==>  (a (b c d))
   
       (pair. (cadar e) (evlis. (cdr e) a))     ==> ((x a) (y (b c d)))
   
       ;; Thus the environment has been modified
       (setq a  (append. (pair. (cadar e) (evlis. (cdr e) a)) a))     ==> ((x a) (y (b c d)))
       a     ==> ((x a) (y (b c d)))
   
       (eval. (caddar e) (append. (pair. (cadar e) (evlis. (cdr e) a)) a))     ==> (a c d)
   
   
   

References and Further reading

1. Paul Graham
2. About Lisp
3. John McCarthy's original paper on Lisp
4. Lisp history from the inventor/discoverer