AIM-514, saved from madness by a Knight

So last time I just brain dumped a bunch of notes on the subject of the AI Memo 514. This time I’ll attempt to offer an analysis of the paper, and compare it to the Knight thesis.

The critical thing to understand about AIM-514 and the thing to which the authors hint repeatedly in the paper although it took me several reads to catch on is that by no means is the chip presented intended for actual use. As noted in the last few pages (Starting with the history section, Pg. 26), Sussman and Steele confess quite openly that the architecture of this chip was entirely an exercise in “because we can”. The transformation of a recursive Lisp interpreter into a non recursive state machine presented in the introduction was already well understood, this project was just an exercise of putting it on a chip. In fact at the bottom of Pg. 28, the reader is warned

The processor described here is not to be confused with the “LISP Machine” designed and built at MIT by Greenblatt and Knight … [which] is organized as a very general-purpose microprogrammed processor of the traditional kind. … The processor described here is instead intended as an illustration of the abstracted essence of a single technique with as little additional context or irrelevant detail as possible.

Thanks to the “storage manager” unit (Pg. 18) the AIM-514 design is indeed elegant. The state machine which Steele and Sussman present only strictly needs cons, car, cdr and some form of setq. As the entire state of the machine is coded in terms of a series of linked lists representing bindings, the evaluation stack and the program itself. This creates a uniformity of access which allows the machine to be reduced to operating on an abstraction of a list which (Pg. 13) need never be specified because the processor itself isn’t responsible for the structure of vector memory. Instead as noted last time, the memory manager seems to act instead as a small state machine (Pg. 19) which is itself a microcoded processor implementing the abstract memory operations in terms of what appears to be a finite (two element) stack with signaling mechanisms for blocking the “processor” until logical memory operations have completed (Pg. 21, “FREEZE” state).

While elegant this machine makes no sense, nor was it intended to make any. Every state transition of this machine is bound by one or more memory access operations. Most of the state transitions involve three memory reads or writes in order to manipulate the bindings and the clink list. In the worst case of the binding lookup operation however arbitrarily many reads could be required in order to complete a single logical instruction. Furthermore this machine requires another whole (much more traditional) processor to implement the memory operations which were reduced out of the “kernel” interpreter.

A far more reasonable approach to machine design, and the one pursued by Knight et all, is to have but one fairly traditional processor which consumes a more regular instruction stream and maintains far less state and if an interpreter is truly needed provide a software implementation thereof rather than attempting to rely entirely upon interpretation and tolerate the performance penalties thereof.

Next time will be more on the Knight machine, and probably an argument against microcode.