XXIIVV

An abstract machine intended as a target for functional programming language compilers.

The SECD is a stack-based runtime with a core of 10 opcodes defined with a set of transitions between its four components. Functions take their arguments from the stack. The arguments to built-in instructions are encoded immediately after them in the instruction stream. If C and D are both empty, overall evaluation has completed with the result on S.

The .secd representation of a program encodes the various parts of a functional programming language into the abstract machine code, where each opcode is represented as a number. For example, if we compile the Pure Lisp program below:

Pure Lisp: (LAMBDA (X) (ADD (QUOTE 1) X))
SECD(opcodes): ( 3 ( 2 1 1 ( 0 . 0 ) 15 5 ) 4 21 )
SECD(mnemonics): ( LDF ( LDC 1 LD ( 0 . X ) ADD RTN ) AP BRK )
Basic Instructions
0NILCreates an empty list on the top of the stack register.
A nil is compiled to ( NIL ).
1LDPushes the value of a variable onto the stack. The variable is indicated by the argument, a pair.
An identifier is compiled to ( LD ( i . j ) ). where ( i . j ) is an index the jth element of the ith sublist in the Environment stack.
2LDCLoads a constant on the stack.
A number, or a constant, x is compiled to ( LDC x ).

Here are a few compilation examples:

(QUOTE A) ; (LDC A AP STOP)
(LAMBDA (X) X) ; (LDF (LD (0.0) RTN) AP STOP)
Stack Instructions
3LDFTakes one list argument representing a function. It constructs a closure (a pair containing the function and the current environment) and pushes that onto the stack.
4APPops a closure and a list of parameter values from the stack. The closure is applied to the parameters by installing its environment as the current one, pushing the parameter list in front of that, clearing the stack, and setting C to the closure's function pointer. The previous values of S, E, and the next value of C are saved on the dump.
5RTNPops one return value from the stack, restores S, E, and C from the dump, and pushes the return value onto the now-current stack.
((lambda (x y) (+ x y)) 2 3) ; (NIL LDC 3 CONS LDC 2 CONS LDF (LD (1.2) LD (1.1) + RTN) AP)
Recursive function instructions
7RAPWorks like a p ap, only that it replaces an occurrence of a dummy environment with the current one, thus making recursive functions possible
6DUMPushes a "dummy", an empty list, in front of the environment list.
Branching instructions
8SELExpects two list arguments, and pops a value from the stack. The first list is executed if the popped value was non-nil, the second list otherwise. Before one of these list pointers is made the new C, a pointer to the instruction following s e l sel is saved on the dump.
9JOINPops a list reference from the dump and makes this the new value of C. This instruction occurs at the end of both alternatives of a sel.
(if (atom 5) 9 7) ; (LDC 5 ATOM SEL (LDC 9 JOIN) (LDC 7 JOIN))
(lambda (x y) (+ x y)) ; (LDF (LD (1.2) LD (1.1) + RTN))
Builtin Extensions
10CAR(HEAD)Returns a pair's first value.
11CDR(TAIL)Returns a pair's second value.
12ATOMReturns T if its value is atomic.
13CONSReturns a value pair consisting of two expressions.
Builtin Arithmetic
14EQReturns T if two expressions are equal.
15ADDReturns the sum of two numeric values.
16SUBReturns the difference of two numeric values.
17MULReturns the product of two numeric values.
18DIVReturns the quotient of two numeric values.
19REMReturns the remainder of two numeric values.
20LEQReturns T if the first value is less or equal to the second.
Lispkit Extensions
21STOPEnd execution.
25READAssign expression to a device event.
26WRITESends expression to a device.
27IMPLODETransform a list into a symbol.
28EXPLODETransform a symbol into a list of numbers which are the ASCII code for each character.

The compilation notation for builtins is reverse polish notation. To perform an operation is to pop up the front element(s) from s, perform the operation, and put the result back to s.

(ADD (QUOTE 123) (QUOTE 456)) ; ( LDC 123 LDC 456 ADD AP STOP )
(MUL (ADD (QUOTE 12) (QUOTE 34)) (QUOTE 56)) ; ( LDC 12 LDC 34 ADD LDC 56 MUL AP STOP )

Summary

Like all internal data-structures, the stack is a list, with the S register pointing at the list's head. Due to the list structure, the stack need not be a continuous block of memory, so stack space is available as long as there is a single free memory cell. Even when all cells have been used, garbage collection may yield additional free memory.

The current variable environment is managed by the E register, which points at a list of lists. Each individual list represents one environment level: the parameters of the current function are in the head of the list, variables that are free in the current function, but bound by a surrounding function, are in other elements of E.

The C register points at the head of the instruction list that will be evaluated. Once the instruction there has been executed, the pointer is pointed at the next instruction in the list. It is similar to an instruction pointer (or program counter) in conventional machines, except that subsequent instructions are always specified during execution and are not by default contained in subsequent memory locations, as is the case with the conventional machines.

The D register, at whose head the register points, is used as temporary storage for values of the other registers, for example during function calls. It can be likened to the return stack of other machines.

Reference

Here is a minimal emulator for the SECD runtime in ANSI C:

cc lispkit.c -o lispkit view raw

incoming lisp lisp lisp lispkit compiler