CSC302 2006S, Class 7: McCarthy's LISP

Admin:
* Math/CS lunch table today
* Questions on the homework at the end of class.  
  (Sam will attempt it tomorrow.)
* No reading for Wednesday!
* LATE: Dimitar, Alex

Overview:
* What's the point?
* Notation
* Graham's eval.
* Other comments

/What's the point?/

* Graham: You can define LISP using only six/seven/eight core
  operations.
* McCarthy: There are more natural notations for computation than
  the Turing machine.  In fact, the universal computing function
  is less than a page of relatively-clear code.
* Rebelsky: Why LISP was/is important
* Rebelsky: Small, careful definition
* Rebelsky: Even great thinkers miss key points
  * Graham: McCarthy had bugs
  * Many: Didn't need separate notations for "the language" and "the meaning of the language"
  * McCarthy: Didn't understand lambda calculus

/Notation/

* label
  * A way to define recursive functions  (letrec)
  * Ensures that right-hand-side uses the new version of the symbol, not the old one
  * Church had shown that lambdas alone (using the Y combinator) can do recursion (labels are much clearer)

* S-expressions vs. M-expressions
  * S-expressions: The language being defined (LISP)
    * Simplest form:
      * any symbol is an S-expression
      * "open-paren S-expression dot S-expression close-paren" is an S expression
    * Added notation
      * (a, b, c) is shorthand for (a . (b . (c . null)))
      * We now say "(a b c)"
  * M-expressions: The language used to define the meaning of
    S expressions

* (caar x) is shorthand for (car (car x))
* (cadar x) is shorthand for (car (cdr (car x)))

/Graham's eval./

* Some modifications by SamR.
* Some comments by SamR.

; Assumes only quote, atom, eq, cons, car, cdr, cond.

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

; Only two-parameters for making lists
; (list. '(a b) '(c d)) => ((a b) (c d))
; Longer lists require cons.
; Why?  McCarthy hadn't thought about variable parameter procedures
; yet.
(defun list. (x y)
  (cons x (cons y '())))

; Given two equal-length lists, x and y, makes a list of 
; pairs from x and y.  
; (pair. (x0 x1 ... xn) (y0 y1 ... yn)) => ((x0 y0) (x1 y1) ... (xn yn))
; If x is shorter than y?  Procedure is undefined.
;   Suppose x is (a . b) and y is null
(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))))))

; y is an association list of the form
; ((k1 v1) (k2 v2) ... (kn vn))
; x is a key
; Inefficient definition; Good for proof-of-concept
(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))

; eval. has two parameters, e and a
;   e is an expression to be evaluated (an S-expression, so
;     therefore either a symbol or a pair of S-expressions)
;   a is an association list - symbol/expression bindings
;     Idea: If the programmer defines foo as (...), we want to
;       change the environment so that whenever we see foo, we
;       subsititue (...).  The association list keeps track
;       of those bindings.
(defun eval. (e a)
  (cond
    ; Look symbols up in the association list
    ; (E.g., if we'd previously written (define foo (+ 2 4))
    ;   we should find (foo 6) in the table, and return 6.
    ((atom e) (assoc. e a))
    ; Application of a named function to arguments
    ((atom (car e))
     (cond
       ; Built-in functions
       ; Quote: Don't evaluate the parameter
       ((eq (car e) 'quote) (cadr e))
       ; Atom: Evaluate the parameter, then call builtin
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ; Eq: Evaluate the parameters, then call builtin
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ; Car: Evaluate the parameter, then call builtin
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ; Cdr: Evaluate the parameter, then call builtin
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ; Cons: Evaluate the parameters, then call builtin
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ; Cond: Use helper!
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ; Otherwise, it must be a user-defined function
       ; Look it up, and evaluate the result.
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ; Only two things that can be applied that aren't named -
    ; labels and lambdas.
    ; From of an applied label
    ; ((label f (lambda (p1 ... pn) e)) v1 ... vn) 
    ((eq (caar e) 'label)
     ; The lambda part is the caddar, apply it to the v1 ... vn
     (eval. (cons (caddar e) (cdr e))
            ; In a new environment, in which f is defined as
            ;  (label f ...)
            (cons (list. (cadar e) (car e)) a)))
    ; To evaluate a lambda, update the environment so that
    ; each formal param is mapped to the actual and then
    ; evaluate the body
    ((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)))))