My journey in the land of Lisp has just started. I think there’s still a long road to “enlightenment”, but the following “revelations” have already blown my mind…
A few years ago, I read Paul Graham’s The Roots of Lisp article. In it, he showed how one could start with a set of programming primitives and build any function based on them, leading to a full-fledged programming language. He wrote his text in PostScript format which I’ve converted to PDF below:
PG showed that only the following primitives are needed to create a programming language (I’m intentionally changing the Scheme/Common Lisp syntax by adding a Haskell-esque syntax):
1. QUOTE
quote :: Any → Any
(quote x) ; often abbreviated as 'x
2. CONS
cons :: (Any, List) → List
(cons x y)
3. ATOM
atom? :: Any → Bool
(atom? x)
4. CAR
car :: List[Any] → Any
(car x)
5. CDR
cdr :: List[Any] → List[Any]
(cdr x)
6. COND
cond :: (Bool, Any), ... → Any
(cond (p1 e1) ... (pn en))
7. EQ?
eq? :: (Any, Any) → Bool
(eq? x y)
'x or by appending data to old data using cons).We also need a way to define functions (so I guess we can count them as yet another primitive feature) using lambda expressions, and denote them with labels:
lambda :: Any, ... → Any
(lambda (x1 x2 ... xn)
(<something>))
; label notation
(label f (lambda (x) (cons x '(5))))
This was my first encounter with lambdas, but more was about to come as you’ll see in the rest of this post.
PG provided the following function definitions based on the above primitives (it is legit Common Lisp code, you can try it out in SBCL).
evcon. and evlis. should come before eval..; The Lisp defined in McCarthy's 1960 paper, translated into CL.
; Assumes only quote, atom, eq, cons, car, cdr, cond.
; Bug reports to [email protected].
(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 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)))))
**(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)))))**
I recommend reading his article for more information. The last function defined is eval. which evaluates valid Lisp code inside Lisp! This meta aspect of Lisp was also mentioned in the SICP course by referring to the following Escher drawing—as if eval and apply write each other:
https://www.youtube.com/watch?v=OyfBQmvr2Hc
The fact that you can start with a few building blocks and make a whole programming language that allows you to run any computation there ever will be is in itself mind blowing. But did McCarthy design those primitives, or as PG puts it, he discovered them? As it turns out, those building blocks could themselves be broken down into smaller pieces. Think of it like atoms in the universe that can be broken into sub-atomic particles. Surprisingly, these particles were found decades ago by Alonzo Church, the inventor of [Lambda calculus](https://en.wikipedia.org/wiki/Lambda_calculus#:~:text=Lambda calculus (also written as,to simulate any Turing machine.) long before electronic computers even existed!!