LISP 1.5 Interpreters


Control Data Corporation 6600

My interest in LISP began in 1976, when I read Friedman's The Little Lisper. I was mostly programming in FORTRAN and CDC 6600 assembler at that time, so recursion was a cool new idea to me. After reading McCarthy's LISP 1.5 Programmer's Manual, I wrote an interpreter in CDC 6600 assembler. As far as I know, a line-printer listing is the only remaining copy of that program. I'm scanning that in little by litte with ABBYY FineReader, so here are jpg images of the pages done so far:

define functions - DEFINE1, DEFINE2
initialization - INITT1, INITT2, INITT3, INITT4, INITT5, INITT6

Digital Equipment Corporation VAX 11/780

At Caltech, I became friends with Stephen Wolfram, a brilliant physicist. Stephen and others were engaged in field-theory calculations that required heavy-duty symbolic computation. The physics community had developed specialized programs like Veltman's powerful Schoonschip, capable of manipulating expressions that filled disk drives! But the most flexible program was MACSYMA, which was only available on a dedicated PDP-10 at MIT. Stephen thought we needed a local solution to this problem, useable on the High-Energy Physics Deptartment's VAX.

To aid in this venture, I decided to write a LISP interpreter and compiler for the VAX. This machine was not nearly as fast as MIT's PDP-10 (a KL10 model), but my interpreter was faster on our VAX than MACLISP. We never finished the compiler, partly because Stephen decided to write the symbolic math program in C. Rob Pike was also a grad student in the Physics Dept., and his encouragement and knowledge of UNIX was very helpful. Rob suggested using memory fault to trigger garbage collection, instead testing on every call to cons. He and John Reiser at Bell Labs urged me to completely solve the tail-recursion problem in the interpreter.

I designed the data structures for fast execution, the atom flag was the quadword sign bit, some recursion was unwound in the registers, etc. Eval would return the value of an atom in four machine instructions! The calling convention used separate return stacks and frame stacks, which allowed aggressive tail recursion optimization. As far as I know, this was the first interpreter to do serious tail recursion optimization, so that an infinite recursion would loop forever without growing the stack.

data.s - initialized data segment
eval.s - the heart of the interpreter
functions.s - miscellaneous functions
init.s - run-time initialization
math.s - numerical functions
print.s - output S expressions
pure.s - basic lisp functions
read.s - parse S expressions
reclaim.s - the garbage collector


Copyright 2003 Don P. Mitchell. All rights reserved.