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.

Pages: 1 2

6 Responses to “RIP John McCarthy”

1. Jussi Piitulainen said

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)
```
2. Jussi Piitulainen said

The indentations looked more or less right before I submitted the code. Where did they go?

3. Jussi Piitulainen said

(Thanks for the fix.)

4. […] Lisp in Scheme An implementation of McCarthy’s original Lisp in Scheme. […]

5. […] RIP John McCarthy « Programming Praxis […]

6. Commander Klag said

It’s bad coding to use return before else in Python. the code is programmed incorrectly.