-->

ap/xxxxx

__

Notes on: 20:45 (2006.09.11:4 tech_notes#262 research#69 xxxxx_at_piksel#1 lispcpu#1)

Design of LISP-Based processors ... or, LAMBDA The Ultimate Opcode

Guy Steele and Gerald Sussman (http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-514.pdf ) 1979, MIT

To quote from the opening abstract:

We present a design for a class of computers whose 'instruction sets' are based on LISP. LISP, like traditional stored-program machine languages and unlike most high-level languages, conceptually stores programs and data in the same way and explicitly allows programs to be manipulated as data. LISP is therefore a suitable language around which to design a stored-program computer architecture. LISP differs from traditional machine languages in that the program/data storage is conceptually an unordered set of linked record structures of various sizes, rather than an ordered, indexable vector of integers or bit fields of fixed size. The record structures can be organised into trees or graphs. An instruction set can be designed for programs expressed as such trees. A processor can interpret these trees in a recursive fashion, and provide automatic storage management for the record structures.

further - an architecture and an instruction set are specified, fabrication of a VLSI prototype microprocessor is described.

1) LISP as a high-level machine language. Given that "LISP reflects the structure of program expressions in the structure of the data which represents the program." and also given that data and programs are equivalent and can equally be manipulated (within the "incestuous" realm of compilers and interpreters).

2) Tree structure rather than linear vector of instructions which can be indexed using counters and the like. Evaluation by recursive tree-walk.

3) Lisp atoms and lists are described in fine detail with examples prior to the exposition of a meta-circular LISP interpreter (ie. it is written in LISP and can interpret itself).

4) APPLY within this simple interpreter... in the case of primitive procedures:

"... primitive symbols are not to be confused with the atomic symbols used as their names. The actual procedure involved in the combination (car x) is not the atomic symbol CAR, but rather some bizarre object (the value of the atomic symbol CAR) which is meaningful only to PRIMOP-APPLY."

(thus further into the appendix the magic of execution is microcoded)

5) State machine implementation:

An interpreter in the form of a state machine controller. (rendering explicit as a control mechanism that which the recursive LISP interpreter hides - state information that must be saved on each recursive invocation).

Registers and a list memory system.

The evaluator in Lisp has five global registers which simulate the registers of a machine

EXP - hold expression or parts of under evaluation
ENV - holds pointer to environment structure (context)
VAL - value developed in evaluation of expressions
ARGS - list of evaluated arguments
CLINK - pointer to top of the list structure which is the control
stack

Further LISP code such as EVAL-DISPATCH implements the simulation

6) Representing LISP data.

"Lists are normally represented by records each of which contains two pointers to other records. One pointer is the car and the other is the cdr."

(A (B C) D) becomes

 _ _      _ _      _ _
|.|.+ -> |.|.+ -> |.|.+--> NIL
 - -      - -      - -
 |        |        |
 v        |        v
 A        v        D
          _ _      _ _
         |.|.+ -> |.|.+--> NIL
          - -      - -
          |        |
          v        v
          B        C

Pointer representation is unimportant. We give pointer to memory system and it returns the context of the record pointed to. A type field is associated with each pointer.

7) The state machine implementation is combined with typed pointer dispatch to form an interpreter which can be implemented in hardware (p. 15)

8) Storage management:

The system is divided into:

a) a storage system which "provides an operator for he creation of new data objects and also other operators (such as pointer traversal) on those objects."

b) EVAL (program interpreter) which "executes programs expressed as data structures within the storage system"

in classic Von Neumann style.

The storage manager here makes a "finite vector memory appear to the evaluation mechanism to be an infinite linked-record memory". Thus a garbage collector is implemented.

9) Physical layout of the prototype processor

"The evaluator and the storage manager are each implemented in the same way as an individual processor. Each processor has a state-machine controller and a set of registers. On each clock cycle the state-machine outputs control signals for the registers and also makes transitions to a new state."

...

"The contents any register is a pointer (8 bits in the prototype) and a type field (3 bits in the prototype). The registers of a processor are connected by a common bus (E bus in the evaluator, G bus in the storage manager)

....

"Each state-machine controller consists of a read-only memory (implemented as a PLA), two half registers (?) (clocked inverters, one at each input and one at each output), and some random logic (eg. for computing the next state)... two phase non-overlapping clock signals..."

1- registers are clocked. next state is computed

2- next-state signals appear and are latched

all signals from the controllers can be multiplexed onto twelve probe lines

10) Discussion

There is no ALU.

Possible addition of complex processors/devices on the external memory bus with LISP processor serving as controller.

At the same time talks of a layered approach wherein a line can be drawn at arbitrary points within a tower of abstraction = a boundary between evaluator and storage manager

"... a hierarchy of interpreters running in [a] virtual machine. Each layer implements a virtual machine within which the next processor up operates."

such a boundary also exhibits an arbitrary distinction between hardware and software. also the overlap:

"Each of the layers in this architecture has much the same organisation: it is divided into a controller ("state machine") and a data base ("registers"). There is a reason for this. Each layer implements a memory system and so has state; this state is contained in the data base (which may be simply a small set of references into the next memory system down (own note: no operation but only a mapping)). Each layer also accepts commands from the layer above it, and transforms them into commands for the layer below it; this is the task of the controller."

also in talking of analogies between common CPU and CPU here:

"We may loosely say that there are two addressing modes in this architecture, one being immediate data (as in a variable reference), and the other being a recursive evaluation. In the latter case, merely referring to an operands automatically calls for the execution of an entire routine to compute it!"

11) History of VLSI implementation

Typed pointers treated as instructions, with the types as "opcodes" to be dispatched on by a state machine...

Rough sketch of building blocks:

PLA library array cells, simple replicated register cells assembled using (LISP-based) software

12) Conclusion

A CPU "... organised purely around linked records, especially in that the instruction set is embedded in the organisation."

Finally concludes that just as the LISP tree data representation informs this particular instruction set and thus the CPU architecture (for it is not just a question of representation but also changing the means of manipulation), so other representations (for example graphs) or storage organisations could be examined.

13) Appendix - Prototype Lisp Processor Technical Specifications

For later examination.

so far... The Instruction Set:

The 3 byte type field supplies 8 "opcodes":

from 0=constant list to 7=quoted constant

Address part of the word has different purposes dependent on type.

Procedure call (type 6) is the most complicated of all:

"It is a list of indefinite length, chained together by CDR pointers

xx_____

Also of note here is the use of transistors and resistors (in this case depletion-mode transistors) which can be used to construct logic gates.

see also GC probe mux and multiplexor p61,62 - a grid of wires with transistor across for probes

register cell p 63

FPGA research plans:: 17:26 (2006.09.11:3 tech_notes#261 research#68 fpga#1 xxxxx_at_piksel_notes#23)

further electronics: 15:58 (2006.09.11:2 tech_notes#260 electro#1)

flip-flop:

flip-flop as (bistable, in the case of counters, registers and memory) multivibrator

http://www.eelab.usyd.edu.au/digital_tutorial/part2/flip-flop01.html

inductor:

changing current in an inductor produces an EMF in the inductor which opposes the current change...

-> reactance (ohms) whuch is the ac equivalent of resistance and in case of inductor is effected by frequency (high frequency high reactance)

Notes on: 15:30 (2006.09.11:1 tech_notes#259 xxxxx_at_piksel_notes#22 research#67)

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.)

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:

http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html

)

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
       BRA BIGLUP

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).

x_______

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.

x_____

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)