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.

About these ads

Pages: 1 2

5 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 [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: