8.7 SECD and WAM
There are two virtual machines of historical importance – SECD for the LISP and other functional languages and Warren abstract machine (WAM) for the PROLOG and other similar logic languages. Both these machines were intended to be used in three ways – for interpreted execution, further translation into a more conventional native target language of a commercial processor and for direct execution by a specialized hardware processor.
The SECD is an abstract machine with facilities and properties well suited for functional languages like LISP. It was invented by Pete Landin (1963) as a sample target machine for LISP. It uses a linked list oriented architecture and convenient target for S-expressions. The basic memory model of SECD consists of an array of tagged memory cells of fixed size, each having a unique address. The content of a cell can be interpreted to have several formats, by dividing it into several fields. For example, a cell tagged as “Integer” will look like:
| Int | Integer Data Value |
The so-called “cons” cell, used to form the linked lists, looks like:
| cons | car cell addrss | cdr cell addrss |
where car denotes the head of a list and cdr denotes the “tail” or remaining portion of a list. A chain of such cells defines a linked list.
SECD has four basic registers for its operation – S the stack register points to a list in memory which behaves like stacks in conventional computers. E the environment register points to the current value list of function arguments. C the control register, works like the Program Counter of a conventional computer. It points to the memory cell which contains the current instruction to be executed. Instead of incrementing, it progresses through the cdr chaining. D, the dump register remembers the current states of S, E and C registers when a function calls itself recursively. It behaves very similar to call–return sequence in a conventional computer.
The origin of WAM is in the PhD thesis of David H. D. Warren (1977). The basic architecture is Von Neumann-like, though there is a strong dependence on a stack. A variety of procedure call instructions directly implement the sequencing philosophy assumed by the PROLOG inference engine as it cycles through the goal lists and the program clauses. Other instructions provide a wide variety of Unification tests.