RIP John McCarthy
November 1, 2011
Here is our version of the functions shown above, with the function names prefixed with an asterisk to distinguish them from their Scheme homophones:
(define null null?)
(define (atom x) (not (pair? x)))
(define (*pairlis x y a)
(cond ((null x) a)
(else (cons (cons (car x) (car y))
(*pairlis (cdr x) (cdr y) a)))))
(define (*assoc x a)
(cond ((equal? (caar a) x) (car a))
(else (*assoc x (cdr a)))))
(define (*apply fn x a)
(cond ((atom fn)
(cond ((eq? fn 'car) (caar x))
((eq? fn 'cdr) (cdar x))
((eq? fn 'cons) (cons (car x) (cadr x)))
((eq? fn 'atom) (atom (car x)))
((eq? fn 'eq) (eq? (car x) (cadr x)))
((eq? fn 'null) (null (car 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) (cdr x) (cons (cons (cadr fn) (caddr fn)) a)))))
(define (*eval e a)
(cond ((atom e) (cdr (*assoc e a)))
((atom (car e))
(cond ((eq? (car e) 'quote) (cadr e))
((eq? (car e) 'cond) (*evcon (cdr e) a))
(else (*apply (car e) (*evlis (cdr e) a) a))))
(else (*apply (car e) (*evlis (cdr e) a) a))))
(define (*evcon c a)
(cond ((*eval (caar c) a) (*eval (cadar c) a))
(else (*evcon (cdr c) a))))
(define (*evlis m a)
(cond ((null m) '())
(else (cons (*eval (car m) a) (*evlis (cdr m) a)))))
(define (*evalquote fn x) (*apply fn x '()))
We made three small changes: McCarthy’s m-expressions have been translated to s-expressions, null has been added as a built-in (it is needed for the reverse example given below), and x has been changed to (cdr x) in the label clause of apply (to preserve the typing). Otherwise, the code is unchanged from McCarthy’s original, which after fifty years is a testament to the strong foundations of the language.
Here are two examples, the first due to McCarthy and the second an implementation of the list-reversing function:
> (*evalquote
'(lambda (x y)
(cons (car x) y))
'((a b) (c d)))
(a c d)
> (*evalquote
'(label reverse
(lambda (ls new)
(cond ((null ls) new)
((quote t) (reverse (cdr ls) (cons (car ls) new))))))
'(reverse (a b c d e) ()))
(e d c b a)
It helps that we used Lisp to implement Lisp. In some other language we would have to write a reader that reads input and parses it into lists and atoms and a writer that displays lists and atoms. We would also have to write the built-in functions like car and cons that Lisp provides natively. Still, implementing a simple Lisp interpreter isn’t hard; there’s even a Lisp interpreter written in Awk.
You can run the program at http://programmingpraxis.codepad.org/8cfeZ3ER. If you are interested in implementing Lisp, for real, you may be interested in Christian Quiennec’s book Lisp In Small Pieces.
Programming Praxis 
Let him be remembered, among other things, for the conditional expression. And for the art of the interpreter to describe programming language semantics, of course.
This is Python 3 to implement a Scheme-like language: variables, int constants, lexically scoped functions and calls, and the McCarthy conditional. And definitions. Primitive operations can be added to the top level environment similar to the “<" which I put there just for the signum test.
def define(var, exp, env): env[0][var] = evaluate(exp, env) def evaluate(exp, env): return ( exp if isinstance(exp, int) else lookup(exp, env) if isinstance(exp, str) else special(exp, env) if isinstance(exp[0], str) and lookup(exp[0], env) == "specop" else call(exp, env) ) def lookup(var, env): return env[0][var] if var in env[0] else undefined if env is top else lookup(var, env[1]) def special(exp, env): if exp[0] == "fun": _, params, body = exp return ("closre", params, body, env) else: for condition, consequent in zip(exp[1::2], exp[2::2]): if evaluate(condition, env): return evaluate(consequent, env) return undefined def call(exp, env): proc, *args = [ evaluate(sub, env) for sub in exp ] if proc[0] == "primop": return proc[1](*args) else: _, params, body, env = proc return evaluate(body, ( { param : arg for param, arg in zip(params, args) }, env )) top = ( { "<" : ("primop", lambda x, y : int(x < y)), "fun" : "specop", "if" : "specop" }, "not an environment" ) undefined = ("primop", lambda *x : "sorry") def test(): "Returns (1, 0, -1), defines sgn in top" define("sgn", ["fun", ["x"], ["if", ["<", "x", 0], -1, ["<", 0, "x"], +1, 1, 0]], top) return evaluate(["sgn", 3], top), evaluate(["sgn", 0], top), evaluate(["sgn", -3], top) def test2(): "Returns 41, defines cons, car, cdr in top" define("cons", ["fun", ["x", "y"], ["fun", ["c"], ["if", "c", "x", 1, "y"]]], top) define("car", ["fun", ["p"], ["p", 1]], top) define("cdr", ["fun", ["p"], ["p", 0]], top) return evaluate(["car", ["cdr", ["cons", 31, ["cons", 41, 59]]]], top)The indentations looked more or less right before I submitted the code. Where did they go?
(Thanks for the fix.)
[…] Lisp in Scheme An implementation of McCarthy’s original Lisp in Scheme. […]
[…] RIP John McCarthy « Programming Praxis […]
It’s bad coding to use return before else in Python. the code is programmed incorrectly.