http://paulgraham.com/rootsoflisp.html

the_surprise.md

Seven Primitives

Quote

> (quote a)
a

Atom

> (atom 'a)
t
> (atom '(a b c))
()

Equals

> (eq 'a 'a)
t
> (eq 'a 'b)
() ; In Lisp this would be f, empty list used for functional examples

car (or first)

> (car '(a b c))
a

cdr (or rest)

> (cdr '(a b c))
(b c)

cons

> (cons 'a '(b c))
(a b c)
> (cons 'a (cons 'b (cons 'c '())))
(a b c)

cond (the only if)

> (cond ((eq 'a 'b) 'first)
        ((atom 'a) 'second))
second

Functions

> ((lambda (x) (cons x '(b))) 'a)
(a b)

> ((lambda (f) (f '(b c)))
   '(lambda (x) (cons 'a x)))
(a b c)

Secondary functional notation enabling recursive calls

> (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)))))))
>(subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)

Abreviations

> ((eq (label (lambda (p1...pn) e)) 
       (defun (p1...pn) e)))
t

Some Functions

Functions defined using the seven primitives and functions The purpose of this is to give us a shorthand to access evaluation patterns

; cxx where x is a sequence of as or ds,
; abreviating the corresponding composition
; (eq (cadr e) (car (cdr e)))
> (cadr '((a b) (c d) e))
(c d)
> (caddr '((a b) (c d) e))
e
> (cdar '((a b) (c d) e))
(b)

; Abriviation for cons pattern
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
> (list 'a 'b 'c)
(a b c)

Defining some new functions

Null

> (defun null (x)
    (eq x '()))
> (null 'a)
()
> (null '())
t

And

> (defun and (x y)
    (cond (x (cond (y 't) ('t '())))
          ('t '())))
> (and (atom 'a) (eq 'a 'a))
t
> (and (atom 'a) (eq 'a 'b))
()

Not

> (defun not (x)
    (cond (x '())
          ('t 't)))
> (not (eq 'a 'a))
()
> (not (eq 'a 'b))
t

Append

> (defun append (x y)
    (cond ((null x) y
           ('t (cons (car x (append (cdr x) y)))))))
> (append '(a b)  '(c d))
(a b c d)
> (append '() '(c d))
(c d)

Pair

> (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))))))
> (pair '(x y z) '(a b c))
((x a) (y b) (z c))

Association

> (defun assoc (x y)
    (cond ((eq (caar y) x) (cadar y))
          ('t (assoc x (cdr y)))))
> (assoc 'x '((x a) (y b)))
(a)
> (assoc 'x '((x new) (x a) (y b)))
new

The magic

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

... a remarkable elegant model of computation. Using just quote, atom, eq, car, cdr, cons, and cond, we can define any additional function we want.