Home

Background

A LISP machine is designed to directly execute the LISP language. Rather than interpreting code in the form of list data structures, the code is compiled to an intermediate instruction set that it optimized for LISP execution. In the mid 70s, a group of computer scientists built a LISP machine called 'CONS' at MIT. A few companies commercialized the technology in the 80s, but it rather quickly faded into obscurity.

http://www.textfiles.com/bitsavers/pdf/mit/cadr/Greenblatt-The_LISP_Machine-1975.pdf

The implementation of this core bears little resemblance to the original CONS machine, but has the same basic design philosophy.

Language

The language is a lexically scoped LISP dialect. Three basic types are supported:

• List nodes
• Integers (16 bits)
• Functions

The only allocatable type is a list node, which has two entries (a datum and next pointer). Actually, it can be a pair of any two types, but it is used as a list most commonly. The advantage of having a fixed size type is that compaction is unnecessary, which greatly simplifies the runtime. As a consequence of this, strings are not natively supported. However, the compiler will convert literal strings (surrounded by double quotes) automatically into lists of characters. This isn't especially space efficient, but is convenient to deal with, since standard list manipulation operations can be applied to them.

The ` ' and , characters are reserved and are expanded by the compiler to (backquote expr) (quote expr) and (unquote _expr) respectively. The double quote (") character is used to delimit strings, and parenthesis are obviously used to enclose lists. Integer literals (in decimal base) start with a number. Other than that, all other non-whitespace characters are valid identifier characters. It is perfectly valid to name a function %^@#&^*, for example.

The compiler supports a simple LISP macro processor, which is actually a small LISP interpreter. When a macro is invoked, the LISP expression is evaluated and the return value of the expression is inserted into the code. The simplest way to use the macro functionality is to use the backquote form (`), which will copy the contents of a list verbatim except for elements that are preceded by a comma (which are evaluated). For example, the if macro is implemented as follows:

(defmacro if (a b c)
    `(cond 
        (,a ,b)
        (1 ,c)
    )
)

Here is a list of basic forms that are supported:

• (first expr) Returns the first element of a list. Same as car function in other LISP implementations.
• (rest expr) Returns remainder of list without first element. Same as cdr function in other LISP implementations.
• (cons first rest) Allocates a new list element. Takes two arguments, which are the first and rest pointers respectively.
• (assign variablename expr) Assign a value to a variable. If the variable is not in a local scope (created either as a function argument or by using the 'let' construct), it is assumed to be global.
• (function (arg1 arg2...) expr) Creates a new anonymous function object. The second parameter is a list of argument names, and the third is an expression to evaluate. Note that a function cannot currently use variables from its surrounding scope.
• (function name (_arg1 arg2...) expr) Can only be used at the outermost scope level. Creates a function in the global namespace. Roughly equivalent to (assign name (function (arg1 arg2 ...) expr), but the compiler can do some extra optimizations because it knows the name is constant.
• (if test_expr eval_if_true [eval_if_false]) Conditional. If the test expression is true, the second parameter will be evaluated. If it is not, the optional third parameter will be evaluated (else clause).
• (let ((var1 initial_value1) (var2 initial_value2)...) expr...) Creates local variables in a new scope. Note that, unlike some other forms, this one allows a sequence of multiple expressions.
• (begin expr expr...) Evaluate a sequence of expressions in order. The value of this expression will be the value of the last expression in the block.
• (while loopcond expr expr...) Basic loop construct. Execute until a condition is false. Note that this implicitly creates a (begin) and will eval all subsequent arguments in the list.
• (break [expr]) Break out of the current loop, with an optional value
• Arithmetic expressions like +, -, rshift, lshift, and, or, xor (operation operand1 operand2_)

Implementation

The compiler converts the LISP code into machine code, which is then executed by a multi-cycle hardware stack machine with random-logic decode and next state control. When the compiler starts, it automatically reads the file 'runtime.l', which has a number of fundamental primitives that are written in LISP (for example, cons).

The top stack element is cached in an internal register, which allows binary operations to execute with a single memory reference. For example, when an add is performed, the first cycle fetches the next-on-stack value from RAM. In the second cycle, the values is added to the top-of-stack register and the result is placed back into the register. The stack pointer is also updated in this cycle to reflect the other operand being popped off the stack.

Internally, the processor uses a harvard architecture. Program ROM is 21 bits wide, where the top 5 bits are the opcode and the low 16 bits are the operand.

    +--------+------------------------+
    | Opcode |        Operand         |
    +--------+------------------------+

Data RAM is 19 bits wide, where the top bit is a flag used during garbage collection, the next 2 bits denote the type of an element, and the bottom 16 bits hold the value. The top-of-stack register is also 19 bits and retains the tag.

    +--+----+------------------------+
    |GC|Type|        Value           |
    +--+----+------------------------+

Type may be one of:

• 00 Integer
• 01 Pointer to list node
• 10 Function address

The stack grows downwards. When a function call is made, the caller pushes the parameters on the stack from right to left. After the call instruction executes (and upon entry into the called function), the stack frame looks like this (stack grows down, top of stack is bottom entry):

param_n

...

param_1

param_0

previous base pointer

return address

local_0

...

local_n

When the function call is made, the processor will automatically push the current base pointer on the stack and set the base pointer register to point to the stack location where it is saved. It then pushes the return address. A called function may then use the 'reserve' instruction to allocate space for local variables.

The getlocal/setlocal functions use a signed offset from the base pointer register. Negative offsets are used to access local variables and positive offsets are used to access parameters passed into the function from the caller.

The data memory map looks like the following (lowest address on bottom):

Hardware control registers (GPIOs, etc)

Stack

Heap

Global Variables

The garbage collector and allocator are written in LISP and are in runtime.l. The garbage collector is a simple mark/sweep allocator. It begins walking entries in the global variable space and stack (the size and location of global variables are encoded in several built-in variables that the compiler creates). The garbage collector checks the tag field to determine which pointers refer to list cells. For each list cell, the highest bit in the tag field of the first entry of the list cell indicates whether this has been marked yet (it should be noted that this bit is associated with the memory location, where other tag bits are associated with the pointer). If the bit is marked, the cell is skipped, both as an optimization and to avoid going into an infinite loop if there is a cycle in the pointers. Otherwise it is marked. The sweep phase simply walks all heap blocks and puts any that do not have this bit set into the global free list.

The following instructions are supported:

Name	Operand	Opcode	Cycles	Stack Before	Stack After	Description
Function Invocation
call	No	1	1	param_n ... param0 function	param_n ... param0 basePointer returnAddress	Transfer control to a function (save return information)
return	No	2	3	retval	retval	Return execution to function that called the current one.
reserve	Yes	24	1		...	Move the stack pointer down by n slots to make space for local variables.
cleanup	Yes	31	1	param param param retval	retval	Remove param values from stack,leaving top of stack intact. Used to remove parameters after return from a function call.
Branch
goto	Yes	26	1			Unconditional branch to _operand_
branch if false	Yes	27	3	testval		Pop the top value off stack and branch to _operand_ if the value is zero
Memory Access
load	No	4	2	ptr	value	Load a value from memory
store	No	5	2	value ptr	value	Store a value to memory
rest	No	8	2	ptr	rest	Given a list element, return the next pointer (rest of list)
Stack
push	Yes	25	1		val	Push integer immediate value onto top of stack.
pop	No	3	2	value		Remove the top element from the stack
dup	No	13	1	val	val val	Push another copy of the value on the top of the stack onto the stack.
get local	Yes	29	3		val	Get a local variable from the current stack frame (specified by parameter) and push onto top of stack
set local	Yes	30	3	val		Pop the value off the stop of the stack and save into stack frame variable specified by parameter.
Arithmetic
add	No	6	2	augend addend	sum	Add top two values on stack and push result back on stack
sub	No	7	2	subtrahend minuend	difference	As above, but subtract
and	No	16	2	val1 val2	result	As add, except bitwise logical AND of two elements on stack
or	No	17	2	val1 val2	result	As add, except bitwise logical OR of two elements on stack
xor	No	18	2	val1 val2	result	As add, except bitwise logical exclusive-OR of two elements on stack
lshift	No	19	2	val1 val2	result	As add, except logical shift left of two elements on stack
rshift	No	20	2	val1 val2	result	As add, except logical shift right (not sign extended) of two elements on stack
greater	No	9	2	val2 val1	result	Compare the top two stack values and set the top of stack to 1 if val1 is greater than val2 (otherwise set top of stack to zero)
greater or equal	No	10	2	val2 val1	result	As above, except set value to 1 if greater or equal.
equal	No	11	2	val2 val1	result	As above, except test equality
not equal	No	12	2	val2 val1	result	As above, except test inequality
Misc
get bp	No	21	1		bpval	Push current base pointer value onto stack
get tag	No	13	1	val	tag	Copy the tag bits from the value on the top of the stack into the data portion of the entry
set tag	No	14	2	newtag val	val'	Update the tag field of a value on the stack without modifying the data portion.
nop	No	0	1			Do nothing.