XXIIVV — secd

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.

Stack S register points to a list of intermediate results.
Environment E register points to the current environment.
Control C register points a location in the program.
Dump D register points to a list of triples. Each triple contains snapshots of the stack, environment, and control registers.

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
0	NIL	Creates an empty list on the top of the stack register.
0	NIL	A nil is compiled to ( NIL ).
1	LD	Pushes the value of a variable onto the stack. The variable is indicated by the argument, a pair.
1	LD	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.
2	LDC	Loads a constant on the stack.
2	LDC	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
3	LDF	Takes 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.
4	AP	Pops 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.
5	RTN	Pops 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
7	RAP	Works like a p ap, only that it replaces an occurrence of a dummy environment with the current one, thus making recursive functions possible
6	DUM	Pushes a "dummy", an empty list, in front of the environment list.
Branching instructions
8	SEL	Expects 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.
9	JOIN	Pops 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
10	CAR(HEAD)	Returns a pair's first value.
11	CDR(TAIL)	Returns a pair's second value.
12	ATOM	Returns T if its value is atomic.
13	CONS	Returns a value pair consisting of two expressions.
Builtin Arithmetic
14	EQ	Returns T if two expressions are equal.
15	ADD	Returns the sum of two numeric values.
16	SUB	Returns the difference of two numeric values.
17	MUL	Returns the product of two numeric values.
18	DIV	Returns the quotient of two numeric values.
19	REM	Returns the remainder of two numeric values.
20	LEQ	Returns T if the first value is less or equal to the second.
Lispkit Extensions
21	STOP	End execution.
25	READ	Assign expression to a device event.
26	WRITE	Sends expression to a device.
27	IMPLODE	Transform a list into a symbol.
28	EXPLODE	Transform 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

Pure Lisp, SECD virtual machine in ANSI C.

incoming lisp lispkit compiler uxn devlog 2023