SECD machine

The SECD machine is a highly influential (see: § Landin's contribution) virtual machine and abstract machine intended as a target for functional programming language compilers. The letters stand for Stack, Environment, Control, Dump—the internal registers of the machine. The registers Stack, Control, and Dump point to (some realizations of) stacks, and Environment points to (some realization of) an associative array.

The machine was the first to be specifically designed to evaluate lambda calculus expressions. It was originally described by Peter J. Landin in "The Mechanical Evaluation of Expressions"[1] in 1964. The description published by Landin was fairly abstract, and left many implementation choices open (like an operational semantics).

Lispkit Lisp was an influential compiler based on the SECD machine,[2] and the SECD machine has been used as the target for other systems such as Lisp/370.[3] In 1989 researchers at the University of Calgary worked on a hardware implementation of the machine.[4]

  1. ^ Landin, P. J. (January 1964). "The Mechanical Evaluation of Expressions". Comput. J. 6 (4): 308–320. doi:10.1093/comjnl/6.4.308.
  2. ^ Henderson, Peter (1980). Functional programming: application and implementation. Englewood Cliffs, N.J.: Prentice-Hall International. ISBN 0-13-331579-7.
  3. ^ Padget, Julian. "Three uncommon Lisps". CiteSeerX 10.1.1.99.1028. {{cite journal}}: Cite journal requires |journal= (help)
  4. ^ A paper on the design, SECD: DESIGN ISSUES is available.