A virtual machine intended as a target for functional programming language compilers.
The SECD machine is defined with a set of transitions between its four components:
- A stack register holding a list of intermediate results.
- An environment register holding the current environment.
- A control register holding a list of control directives.
- A dump register holding a list of triples. Each triple contains snapshots of the stack, environment, and control registers.
Stacks
Like all internal data-structures, the stack is a list, with the S register pointing at the list's head or beginning. 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. Obviously, specific implementations of the SECD structure can implement the stack as a canonical stack structure, thus improving the overall efficiency of the virtual machine, provided that a strict bound be put on the dimension of the stack.
The C register points at the head of the code or instruction list that will be evaluated. Once the instruction there has been executed, the C 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 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 dump, at whose head the D 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.
- s Stack used for evaluation of expressions.
- e Environment used to store the current value list.
- c Control used to store the instructions.
- d Dump used to store suspended invocation context.
Primitives
| Basic Instructions | ||||
|---|---|---|---|---|
| NIL | pushes a nil pointer onto the stack | |||
| LD | pushes the value of a variable onto the stack. The variable is indicated by the argument, a pair. | |||
| LDC | pushes a constant argument onto the stack | |||
| Branching instructions | ||||
| 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. | |||
| 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. | |||
| Non-recursive function instructions | ||||
| 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. | |||
| 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. | |||
| 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. | |||
| Recursive function instructions | ||||
| 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 | |||
| DUM | pushes a "dummy", an empty list, in front of the environment list. | |||
A. Push Objects to Stack
Compilation Rules:
- (a) A nil is compiled to (NIL)
- (b) A number (or a constant) x is compiled to (LDC x)
- (c) An identifier is compiled to (LD (i.j)) where (i.j) is an index into stack e.
Stack Operations:
- NIL s e (NIL.c) d -> (nil.s) e c d
- LDC s e (LDC x.c) d -> (x.s) e c d
- LD s e (LD (i.j).c) d -> (locate((i.j),e).s) e c d
"Locate" is an auxiliary function. It returns the jth element of the ith sublist in e.
Note: roughly, e is a list of sublists each of which is a list of actual parameters. Thus, e corresponds to the value list in our interpreter. There will be no name list here, as each occurrence of a formal parameter will be compiled to LD (i.j) and by locate(i.j) the corresponding actual parameter is found.
"The Mechanical Evaluation of Expressions" by PeterLandin is the original paper that describes the SECD machine.