Home

Background

A LISP machine natively executes the LISP language. Rather than directly interpreting code in the form of list data structures, the code is usually 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 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 three basic types:

• 16-bit signed integer
• Function reference
• 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.

The only dynamically allocatable type is the pair. The advantage of having a fixed size type is that compaction is unnecessary. This simplifies the runtime. The compiler represents strings as lists of characters. Standard list operators can manipulate these. The compiler converts literal strings (surrounded by double quotes) into lists of characters built with a sequence of 'cons' calls.

The compiler expands the ` ' and , characters to (backquote expr) (quote expr) and (unquote _expr). The double quote (") character delimits strings, and parenthesis enclose lists. Integer literals (in decimal base) are also supported. Other than that, all other non-whitespace characters are valid identifier characters. It is valid to name a function %^@#&^*, for example.

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. Note that a function cannot currently use variables from its surrounding scope (closures).
• (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 is evaluated. If it is not, the optional third parameter is 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 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 simplest way to use the macro functionality is to use the backquote function (`), which copies the contents of a list verbatim except for elements preceded by a comma (which are evaluated). For example, the foreach macro is 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 does not support an interactive mode (REPL loop). Instead, code is compiled off-line into machine code and loaded into program ROM. The processor is a multi-cycle hardware stack machine with random-logic decode and next state control. When the compiler starts, it automatically 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 reference. 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.

    +--------+------------------------+
    | Opcode |        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, 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 pair structure
• 10 Function address

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

param_n

...

param_1

param_0

previous base pointer

return address

local_0

...

local_n

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 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.lisp. The garbage collector is a simple mark/sweep allocator. 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	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 and throw it away (drop)
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	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	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.