AIM-514, saved from madness by a Knight
18 Sep 2015So 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.
^d