Home

Background

A LISP machine natively executes the LISP language. Rather than directly interpreting code in the form of list data structures, they usually compile the code to an intermediate instruction set that is 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 has since 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 with dynamic types.
It supports four basic types:

• 16-bit signed integer
• Pointer to a "Pair" structure (sometimes called a "cons cell" in traditional LISP implementations). This is can containing any two typed values, but is usually used to represent linked list nodes, with the second element containing the 'next' pointer.
• Function pointer
• Closure pointer. A closure is a pair that contains an anonymous function pointer bundled and a linked list of variables captured from the environment it was created in.

The only dynamically allocatable type is the pair. The advantage of having a fixed size type is that compaction is unnecessary, which simplifies the runtime.

Unlike most Lisp interpreters, this processor doesn’t support a REPL (read/evaluate/print loop). The compiler builds the program on a host machine and preloads into instruction memory on the device.

The compiler represents strings as lists of characters. Programs can manipulate these using standard list operators. The compiler converts literal strings (surrounded by double quotes) into lists of characters built with a sequence of 'cons' calls.

Here is a list of basic forms that the compiler supports:

• (first expr) Returns the first element of a pair. If the operand is a pointer to a list, this returns the first element of the list. Same as car function in other LISP implementations.
• (rest expr) Returns the second element of a pair. If the operand is a pointer to a list, this is the rest of list without first element. Same as cdr function in other LISP implementations.
• (cons first rest) Allocates a new pair. 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 (either as a function argument or created using the 'let' construct), it is a global variable.
• (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.
• (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 processor will evaluate the second parameter, otherwise it will evaluate the third parameter (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 after expr.
• (begin expr expr...) Evaluate a sequence of expressions in order. The value of this expression is 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 evaluate all subsequent arguments in the list.
• (break [expr]) Break out of the current loop, with an optional value. If the value is specified, the while expression is set to that value. Otherwise, it is set to 0.

Other operators:

• (bitwise-and x y)
• (bitwise-or x y)
• (bitwise-xor x y)
• (+ x y)
• (- x y)
• (* x y)
• (/ x y)
• (mod x y)
• (and x y) Boolean, short circuit and
• (or x y) Boolean, short circuit or
• (not x) Boolean not

The compiler supports a simple LISP macro processor, which is actually a small LISP interpreter. When a macro is invoked, the compiler evaluates the LISP expression inserts the return value into the code. The compiler expands the ' character into the form (quote expr).

The simplest way to use the macro functionality is to use the backquote function, which copies the contents of a list verbatim except for elements that are in a 'unquote' form. As a shorthand, the compiler expands ` and , prefixes to (backquote expr) and (unquote _expr).

For example, the foreach macro is be implemented as follows:

(defmacro foreach (var list expr)
    `(let ((,var 0)(nodePtr ,list))
        (while nodePtr
            (assign ,var (first nodePtr))
            ,expr
            (assign nodePtr (rest nodePtr)))))

Implementation

The processor is a multi-cycle hardware stack machine with random-logic decode and next state control. When the compiler starts, it reads the file 'runtime.lisp'. This contains fundamental primitives written in LISP such as memory allocation and garbage collection.

The processor caches the top stack element in an internal register. This allows binary operations to execute with a single memory access. For example, when the processor executes an add, it fetches the next-on-stack value from RAM in the first cycle. During the second cycle, it adds the value to the top-of-stack register and stores the result back into the top-of-stack register. The stack pointer is also updated in this cycle to reflect popping the other operand off the stack.

The processor uses a Harvard architecture. Program ROM is 21 bits wide. The top 5 bits store the opcode and the bottom 16 bits are the operand.

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

Type may be one of:

• 00 Integer
• 01 Pointer to pair structure
• 10 Function address
• 11 Pointer to closure structure

The stack grows downwards. When a function is called, the caller pushes the parameters on the stack from right to left. Upon entry into the called function, the stack frame looks like this (top of stack is bottom entry):

The call instruction pushes the current base pointer on the stack and adjusts the base pointer register to point to the current stack location. It then pushes the return address. If the compiler detects a tail recursive call, it inserts code to copy the parameter values back into the original frame, then jumps back to the beginning of a function, looping without allocating a new stack frame.

A called function may 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 access local variables and positive offsets access parameters passed into the function from the caller.

The called function pushes its return value onto the stack. The RETURN instruction restores the frame pointer and moves the stack back to the address before the CALL instruction was invoked. Because the top-of-stack is cached in a register, the return value remains there. The calling function then uses the CLEANUP instruction to remove its parameters, once again preserving the return value in the top-of-stack register.

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

The garbage collector and allocator are written in LISP and are in runtime.lisp. The garbage collector uses a mark/sweep algorithm. It walks entries in the global variable space and stack (several built-in variables that the compiler creates encode the memory range of global variables). 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 it has marked this yet. This bit is associated with the memory location, where other tag bits are associated with the pointer. If the bit is marked, the garbage collector skips the cell, both as an optimization and to avoid going into an infinite loop if there is a cycle in the pointers. Otherwise it marks it. The sweep phase walks all heap blocks and puts any that do not have this bit set into the global free list.

The processor supports the following instructions:

Name	Operand	Opcode	Cycles	Stack Before	Stack After	Description
Function Invocation
call	None	1	1	param_n ... param0 function	param_n ... param0 basePointer returnAddress	Transfer control to a function (save return information)
return	None	2	3	retval	retval	Return execution to function that called the current one.
reserve	num locals	24	1		...	Move the stack pointer down by n slots to make space for local variables.
cleanup	num params	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	absolute address	26	1			Unconditional branch to operand
branch if false	absolute address	27	3	testval		Pop the top value off stack and branch to operand if the value is zero
Memory Access
load	None	4	2	ptr	value	Load a value from memory
store	None	5	2	value ptr	value	Store a value to memory
rest	None	8	2	ptr	rest	Given a list element, return the next pointer (rest of list)
Stack
push	Immediate Value	25	1		val	Push integer immediate value onto top of stack.
pop	None	3	2	value		Remove the top element from the stack and throw it away (drop)
dup	None	13	1	val	val val	Push another copy of the value on the top of the stack onto the stack.
get local	Index	29	3		val	Get a local variable from the current stack frame (specified by parameter) and push onto top of stack
set local	Index	30	1	val	val	Save value at the top of the stack into stack frame variable specified by parameter (top of stack is left alone).
Arithmetic
add	None	6	2	augend addend	sum	Add top two values on stack and push result back on stack
sub	None	7	2	subtrahend minuend	difference	As above, but subtract
and	None	16	2	val1 val2	result	As add, except bitwise logical AND of two elements on stack
or	None	17	2	val1 val2	result	As add, except bitwise logical OR of two elements on stack
xor	None	18	2	val1 val2	result	As add, except bitwise logical exclusive-OR of two elements on stack
lshift	None	19	2	val1 val2	result	As add, except logical shift left of two elements on stack
rshift	None	20	2	val1 val2	result	As add, except logical shift right (not sign extended) of two elements on stack
greater	None	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	None	11	2	val2 val1	result	As above, except test equality
not equal	None	12	2	val2 val1	result	As above, except test inequality
Misc
get bp	None	21	1		bpval	Push current base pointer value onto stack
get tag	None	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	None	14	2	newtag val	val	Update the tag field of a value on the stack without modifying the data portion.
nop	None	0	1			Do nothing.