The Design of an M6800 LISP Interpreter, S Tucker Taft, BYTE August 1979

(notes for piksel, instruction sets as steps towards Lisp CPU or any kind of artistic CPU - an examination of hardware-based means of representation. At what point the necessary reduction (or why it is considered as such) into hardware makes sense. Or to keep all levels as a simultaneity. Comparison of high-level with instruction sets. At the same time some way - borrowing from the Lisp CPU - that we can eavesdrop in audio fashion on all internals of the CPU, not just registers a la self.c (own code see software) but also data paths. Indeed if such paths ans such an exposure are implied through a parallel switching architecture. The FPGA is attractive precisely as RECONFIGURABLE architecture or matrix rather than as RECONFIGURED.)

Also towards a Z80 Lisp implementation.

1) Underlying representation of lists using dotted pairs (two address cells). The left cell points to the first element of a list, and the right cell to the rest of the list. NIL is used to signify end of the chain. CONSing two atoms gives a dotted pair with CDR of final dotted pair as non-NIL atom.

(see also diagrams on:



2) READ, EVAL and PRINT loop

Internal representation of the list (the program) is called a form here - the form is evaluated according to the convention that the first element of such a list specifies a function, with the rest of the list as arguments.

3) Into implementation:

BIGLUP LDX PRMPAT  get prompt atom
       JSR PATOM   print the atom
       JSR READ    read the form - result is in x reg
       JSR EVAL    eval the form - result is in x reg
       JSR PRINT

PATOM is a subroutine, also used by PRINT when a form is tested as an atom.

M6800 index (X) register - 16 bits long use for all object representations/forms

Dotted pairs must hold two forms - thus 32 bits (4 consecutive memory bytes)

Internal representation for atoms:

For symbolic atoms two items of information are needed:

thus 4 bytes chosen with first 2 as memory address of print name and third of fourth holding value (form) of the atom

A way to distinguish dotted pairs from atoms is needed:

In this instance all dotted pairs and atoms are aligned on 4 byte boundaries which means that we can use the lowest two bits 00 01 to encode type and garbage collection (GC) information.

With numeric atoms name determines value and hence only name (or value) needs to be specified. Representation was chosen with high order bit set, 14 bits numeric value and 1 for GC (seeing as only 0000 through 7FFF is used for atoms and dotted pairs storage bit so when forms specify this high order bit is free.

Special representation for the NIL atom High order byte is zero (which rules out 256 byte page starting at zero).


A linked list (called OBLIST) of all defined symbolic atoms is used for example by READ and also the EQ function. READ checks prior to allocating 4 byte cell for atome of given print name. If found, returns form specifying the pre-existing atom. Otherwise, copies name into name storage area, allocates 4 byte cell, inits left cell to point to name and right to NIL and returns form.


READ function

Builds up internal representation - allocating dotted pairs and atoms. If expression is a list READ returns the first dotted pair.

RATOM does the work of allocating new cells as above. Deals with parentheses with recursive calls to READ.

(code p143)

PRINT function

Takes a single form as argument, and types the value as fully parenthesised LISP expression.

EVAL function

The heart of the matter.

EVAL accepts one form as argument and evaluates it according to the convention:

"the value of NIL is NIL, the value of a numeric atom is itself, the value of a symbolic atom is the form associated with the atom, and the value of a list is determined by applying the function specified by the CAR of the list to the list of arguments which make up the CDR of the list."

SUBRs and LAMBDAs: SUBRs as built in functions written in machine code (eg. CAR< CDR< PATOM). LAMBDAs are user defined.

The system here treats the bytes which make up the machine code of the SUBR as the print name of the atom. SUBR specified with dotted pair and car as atom SUBR. Machine code is also prefixed with a special string.

(p147 code listing)