Maxwell’s Equations of Software
On December 27, 2004 ACM Queue published an interview with Alan Kay, the creator of Smalltalk. In this interview, he pronounced the famous words:
That was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were "Maxwell’s Equations of Software!" This is the whole world of programming in a few lines that I can put my hand over.
– Alan Kay
So, what is on the bottom of page 13 of the LISP 1.5 Programmers Manual?
This small piece of code is a universal LISP function. In other
words, evalquote can compute the value of any given function applied
to its arguments when given a description of that function. A LISP
interpreter written in LISP itself that fits in a flashcard!
The syntax might look quite different to what we expect from LISP. The reason is the usage of M-expressions instead of S-expressions. The Lisp 1.5 programmers manual explains why on page 1:
The second important part of the LISP language is the source language itself which specifies in what way the S-expressions are to be processed. This consists of recursive functions of S-expressions. Since the notation for the writing of recursive functions of S-expressions is itself outside the S-expression notation, it will be called the meta language. These expressions will therefore be called M-expressions.
The manual also explains how to translate an M-expression to its equivalent S-expression:
As you can imagine, I could not resist to write my own implementation. The following is the complete Racket implementation (evalquote.rkt):
1: #lang racket
2:
3: (define (atom e)
4: (not (cons? e)))
5:
6: (define (pairlis x y a)
7: (cond [(null? x) a]
8: [else (cons (cons (car x) (car y)) (pairlis (cdr x) (cdr y) a))]))
9:
10: (define (evcon c a)
11: (cond [(eval (caar c) a) (eval (cadar c) a)]
12: [else (evcon (cdr c) a)]))
13:
14: (define (evlis m a)
15: (cond [(null? m) null]
16: [else (cons (eval (car m) a) (evlis (cdr m) a))]))
17:
18: (define (eval e a)
19: (cond [(atom e) (cdr (assoc e a))]
20: [(atom (car e)) (cond [(eq? (car e) 'QUOTE) (cadr e)]
21: [(eq? (car e) 'COND) (evcon (cdr e) a)]
22: [else (apply (car e) (evlis (cdr e) a) a)])]
23: [else (apply (car e) (evlis (cdr e) a) a)]))
24:
25: (define (apply fn x a)
26: (cond [(atom fn) (cond [(eq? fn 'CAR) (caar x)]
27: [(eq? fn 'CDR) (cdar x)]
28: [(eq? fn 'CONS) (cons (car x) (cadr x))]
29: [(eq? fn 'ATOM) (atom (car x))]
30: [(eq? fn 'EQ) (eq? (car x) (cadr x))]
31: [else (apply (eval fn a) x a)])]
32: [(eq? (car fn) 'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a))]
33: [(eq? (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn) (caddr fn)) a))]))
34:
35: (define (evalquote fn x) (apply fn x null))
And the following is the same Racket code after commenting every single bit (evalquote-commented.rkt):
1: #lang racket
2:
3: ;; Distinction between forms and functions.
4: ;;
5: ;; It is usual to use the word "function" imprecisely, and to apply it
6: ;; to forms such as y*2+x. Because we shall compute with expressions
7: ;; that stand for functions, we need a notation that expresses the
8: ;; distinction between functions and forms. The notation that we
9: ;; shall use is the lambda notation of Alonzo Church.
10: ;;
11: ;; Let f be an expression that stands for a function of two integer
12: ;; variables. It should make sense to write f[3;4] and to be able to
13: ;; determine the value of this expression. For example, sum[3;4]=7.
14: ;; The expression y*2+x does not meet this requirement. It is not at
15: ;; all clear whether the value of y*2+x[3;4] is 10 or 11. An
16: ;; expression such as y*2+x will be called a form rather than a
17: ;; function. A form can be converted to a function by specifying the
18: ;; correspondence between the variables in the form and the arguments
19: ;; of the desired function.
20:
21: ;; cons returns #t if e is an atomic symbol, #f otherwise.
22: (define (atom e)
23: (not (cons? e)))
24:
25: ;; pairlis gives the list of pairs of corresponding elements of the
26: ;; lists x and y, and appends this to the list a. The resultant list
27: ;; of pairs, which is like a table with two columns, is called an
28: ;; association list.
29: (define (pairlis x y a)
30: (cond [(null? x) a]
31: [else (cons (cons (car x) (car y)) (pairlis (cdr x) (cdr y) a))]))
32:
33: ;; evcon handles the COND form. It evaluates the list of
34: ;; propositional terms c in order, and chooses the form following the
35: ;; first true predicate. a is an association list of names and
36: ;; definitions.
37: (define (evcon c a)
38: ;; Given the conditional expression
39: ;; (COND ((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C)))
40: ;; c is
41: ;; '(((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C)))
42: ;; Thus,
43: ;; (caar c) returns '(ATOM (QUOTE A))
44: ;; (cadar c) returns '(QUOTE B)
45: ;; (cdr c) returns '(((QUOTE T) (QUOTE C)))
46: (cond [(eval (caar c) a) (eval (cadar c) a)]
47: [else (evcon (cdr c) a)]))
48:
49: ;; evlis evaluates the list of arguments m of a function. a is an
50: ;; association list of names and definitions.
51: (define (evlis m a)
52: ;; Given the function call
53: ;; (CONS (QUOTE A) (QUOTE B))
54: ;; m is
55: ;; '((QUOTE B) (QUOTE C))
56: ;; Thus,
57: ;; (car m) returns '(QUOTE B)
58: ;; (cdr m) returns '((QUOTE C))
59: (cond [(null? m) null]
60: [else (cons (eval (car m) a) (evlis (cdr m) a))]))
61:
62: ;; eval handles a form. a is an association list of names and
63: ;; definitions.
64: (define (eval e a)
65: (cond
66: ;; If e is an atomic, then it must be a variable, and its value is
67: ;; looked up on the association list.
68: [(atom e) (cdr (assoc e a))]
69: ;; If e is a list that begins with an atomic symbol, then it can be
70: ;; a quote expressions, a conditional expression or a function
71: ;; call.
72: [(atom (car e))
73: (cond
74: ;; If car of the form is QUOTE, then it is a constant.
75: ;; Given the expression
76: ;; (QUOTE A)
77: ;; Then,
78: ;; (cadr e) returns 'A
79: [(eq? (car e) 'QUOTE) (cadr e)]
80: ;; If car of the form is COND, then it is a conditional
81: ;; expression, and evcon handles it.
82: ;; Given the expression
83: ;; (COND ((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C)))
84: ;; Then,
85: ;; (cdr e) returns '(((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C)))
86: [(eq? (car e) 'COND) (evcon (cdr e) a)]
87: ;; Otherwise, the form must be a function followed by its
88: ;; arguments. The arguments are then evaluated, and the function
89: ;; is given to apply.
90: [else (apply (car e) (evlis (cdr e) a) a)])]
91: [else (apply (car e) (evlis (cdr e) a) a)]))
92:
93: ;; apply handles a function and its arguments.
94: ;;
95: ;; fn is a function. If it is an atomic symbol, there are two
96: ;; possibilities:
97: ;;
98: ;; - fn is an elementary function: CAR, CDR, CONS, ATOM or EQ.
99: ;; - fn is an atom.
100: ;;
101: ;; In each case, the appropriate function is applied to the arguments.
102: ;;
103: ;; x is a list of S-expressions used as arguments. a is an
104: ;; association list of names and definitions.
105: (define (apply fn x a)
106: (cond
107: ;; fn is an atomic symbol.
108: [(atom fn)
109: (cond
110: ;; fn is the elementary function CAR.
111: ;; Given the arguments
112: ;; '((A B C))
113: ;; Then,
114: ;; (caar x) returns 'A
115: [(eq? fn 'CAR) (caar x)]
116: ;; fn is the elementary function CDR.
117: ;; Given the arguments
118: ;; '((A B C))
119: ;; Then,
120: ;; (cdar x) returns '(B C)
121: [(eq? fn 'CDR) (cdar x)]
122: ;; fn is the elementary function CONS.
123: ;; Given the arguments
124: ;; '(A B)
125: ;; Then,
126: ;; (car x) returns 'A
127: ;; (cadr x) returns 'B
128: [(eq? fn 'CONS) (cons (car x) (cadr x))]
129: ;; fn is the elementary function ATOM.
130: ;; Given the arguments
131: ;; '((A . B))
132: ;; Then,
133: ;; (car x) returns '(A . B)
134: [(eq? fn 'ATOM) (atom (car x))]
135: ;; fn is the elementary function EQ.
136: ;; Given the arguments
137: ;; '(A B)
138: ;; Then,
139: ;; (car x) returns 'A
140: ;; (cadr x) returns 'B
141: [(eq? fn 'EQ) (eq? (car x) (cadr x))]
142: ;; Otherwise, fn must be looked up in the association list.
143: [else (apply (eval fn a) x a)])]
144:
145: ;; If fn begins with LAMBDA, then the arguments are paired with the
146: ;; bound variables and the form is given to eval to evaluate.
147: ;; Given the expression
148: ;; (LAMBDA (X) (CDR X))
149: ;; Then,
150: ;; (caddr fn) returns '(CDR X)
151: ;; (cadr fn) returns '(X)
152: [(eq? (car fn) 'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a))]
153:
154: ;; If fn begins with LABEL, then the function name and definition are
155: ;; added to the association list, and the inside function is evaluated
156: ;; by apply.
157: ;; Given the expresion
158: ;; (LABEL FF (LAMBDA (X) (FF (CONS (QUOTE A) X))))
159: ;; Then,
160: ;; (caddr fn) returns '(LAMBDA (X) (FF (CONS (QUOTE A) X)))
161: ;; (cadr fn) returns 'FF
162: [(eq? (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn) (caddr fn)) a))]))
163:
164: ;; evalquote is a universal LISP function. In other words, it can
165: ;; compute the value of any given function applied to its arguments
166: ;; when given a description of that function.
167: ;;
168: ;; fn is the function to be applied represented as a S-expression. x
169: ;; is a list of S-expressions used as arguments.
170: (define (evalquote fn x) (apply fn x null))
So, let's run it!
racket@maxwell-equations/evalquote> (evalquote 'CAR '((A B C))) 'A racket@maxwell-equations/evalquote> (evalquote '(LAMBDA (X) (CDR X)) '((A B C))) '(B C) racket@maxwell-equations/evalquote> (evalquote '(LAMBDA (X) (CONS (QUOTE FIRST) (CDR X))) '((A B C))) '(FIRST B C)
The code is so short and simple that extending it is trivial. For example, the following two lines patch allows to call procedures passed from the environment (evalquote-proc.rkt):
--- evalquote.rkt 2024-06-11 16:56:44.247229249 +0200
+++ evalquote-proc.rkt 2024-06-11 17:14:09.789565784 +0200
@@ -1,5 +1,7 @@
#lang racket
+(require (only-in racket/base [apply rapply]))
+
(define (atom e)
(not (cons? e)))
@@ -28,6 +30,7 @@
[(eq? fn 'CONS) (cons (car x) (cadr x))]
[(eq? fn 'ATOM) (atom (car x))]
[(eq? fn 'EQ) (eq? (car x) (cadr x))]
+ [(and (assoc fn a) (procedure? (cdr (assoc fn a)))) (rapply (cdr (assoc fn a)) x)]
[else (apply (eval fn a) x a)])]
[(eq? (car fn) 'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a))]
[(eq? (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn) (caddr fn)) a))]))
We can add, for instance, the * operator into the context of the
LISP interpreter:
racket@maxwell-equations/evalquote-proc> (apply '(LAMBDA (X Y) (* X Y)) '(2 21) `((* . ,*))) 42
If you like this topic, then stop everything you are doing and go watch the wonderful talk "The Most Beautiful Program Ever Written" by William Byrd.