SECD machine

The SECD machine is a virtual machine that is intended as the target architecture for compilers of functional programming languages ​​. The letters stand for Stack, Environment, Control, dump, what are the internal registers of the machine. These registers contain pointers to lists in memory.

The SECD machine was the first virtual machine that was specifically designed to evaluate expressions in the lambda calculus. It was originally described by Peter J. Landin as part of the definition of its programming ISWIM in 1963. The published description of Landin was pretty abstract and left many implementation decisions open, such as the question of an operational semantics. Therefore, the SECD machine is often presented in more detail, such as in Peter Henderson Lispkit LISP compiler which is distributed since 1980. It is also used as a target architecture for several other experimental compiler.

In 1989, researchers working at the University of Calgary on a hardware implementation of the machine.

Registers and memory

The SECD machine is a stack machine whose instructions take their main arguments from a stack. Additional parameters for an instruction can be specified after the instruction name. The stack is all other internal data structures as represented by a list of the register S is at the top of the list. This list is stored on a heap, so that the stack does not have to be necessarily included in a contiguous block of memory. As long as free memory cells are still present, is also stack space available. If all memory cells were used, a garbage collection may again get memory.

The C register points to the start of the first instruction from the program to be evaluated, which is represented as a list of instructions. After each evaluation of an instruction, the C register points to the next instruction in the list and thus behaves similar to a program counter with the exception that the following instructions do not need to be contained in the immediately succeeding memory locations.

The register E contains the current environment variables, a pointer to a list of lists. Each list contains the variable bindings of a particular level of abstraction: the first list contains the parameters of the current function; Variables that are free in the current function, but are bound in an enclosing function can be found in the following lists.

The " dump " on the top shows the D register is used as temporary storage for the contents of other registers that must be saved in the context of function calls. He plays so far about the role of the call stack at other machines.

The memory organization of the SECD machine is similar to the model that is used by the interpreter of the most functional languages ​​: the memory is a set of memory cells which in each case either an atom, that is, a primitive value or an empty or not - can contain empty list. Non - empty lists are represented by a pair of pointers that are traditionally referred to by car and cdr. More modern developments often instead use the terms head and tail. The different types of values ​​that can be contained in a cell can be distinguished by a type brand (type tag ). Often thereby also the different types of atoms ( numbers, strings, etc. ) may be labeled differently.

For example, a list containing the numbers 1, 2 and 3, and normally in the form " (1 2 3 ) ' is recorded, are shown as follows:

Address tag content ----------------------------        9 [integer | 2]        8 [integer | 3]        7 [list | 8 | 0]        6 [list | 9 | 7]        ...        2 [list | 1 | 6]        1 [integer | 1]        0 [ nil ] The memory cells 3-5 have been omitted here because they do not belong to our sample list, which can be arbitrarily distributed over the memory. The cell 2 contains the head of the list. She points to the cell 1, in which the first element of the list is to be found, and on the cell 6, in which is found the remaining list. The remaining list consists of a reference to the cell 9 in which the second element ("2" ) is the list and the cell 7, which in turn describes a remaining list. Now there is the rest of list from a reference to the cell 8 with the third element ("3" ) and a reference to an empty list (nil ) as a conclusion. In the machine SECD the cell designated by the address 0 is always implied the empty list, so that a special mark to the empty list is unnecessary.

The principle that the second pointer ( " cdr " ) must always point in a list cell to another list, is pure convention. If both "car " and " cdr " point to atoms, this can also be displayed simultaneously as a couple, which is usually listed as " ( first 2) ".

Instructions

The main instructions of the SECD machine are the following:

  • Write a nil nil pointer on the stack
  • Ldc c writes a constant c argument on the stack
  • Ld v writes the value of a variable v on the stack. Variables are here represented by pairs of ( l. P), l ' designates the abstraction level and p is the position within the parameters of this stage. As an example, referred to as " ( the first three ) ," the third parameter of the current function ( abstraction level = 1).
  • Sel l1, l2 removes a value from the stack and makes a case distinction on the value found: If the top of the stack was different from nil, the instruction sequence is executed, pointing to the l1, otherwise the one shown on the l2. Register C so it is replaced by l1 or l2; in any case, a pointer is saved on the sel the following instruction on the dump.
  • Join a list pointer away from the dump and turns it into the new value of the register C. This instruction comes at the end of the two alternatives before a sel instruction.
  • Ldf f expects an argument list that represents the code of a function. From a Closure is prepared: a pair consisting of the code of the function and the current environment E. This closure is stored on the stack.
  • Ap away a closure and a list of parameter values ​​from the stack. The closure is applied to the parameters by making their own environment to the current, the parameter list before it writes the stack empties and the C register is based on the function pointer from the closure. The previous values ​​of S and E, and the continuation address of C to be saved on the dump.
  • Ret away a return value from the stack, the register S, E and C from the dump, restore removes the top element from the dump and pushes the previously removed return value to the restored stack.
  • Dum writes a "dummy", an empty list at the top of the Environment list.
  • Rap works as AP, except that it replaces one occurrence of a dummy environments through the current environment. In this way, recursive functions are possible.

There are also a number of instructions for primitive functions such as "car ", " cdr ", list construction, addition, Ein-/Ausgabe and others. You may be required arguments these functions from the stack.

Computer memory Closure (computer programming)
720619
de