Машина SECD: Виртуальная машина для компиляции функциональных языков программирования

Virtual and Abstract Machine target for functional programming language compiler
The SECD machine is a highly influential (see: ) 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" 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, and the SECD machine has been used as the target for other systems such as Lisp/370. In 1989 researchers at the University of Calgary worked on a hardware implementation of the machine.

D. A. Turner (2012) points out that the ALGOL 60 programming language could not return functions from other functions (rendering functions no longer first class). A function nested inside another function could refer to a variable living on the outer function's stack. If the nested function were returned from the outer function, then it would be referring to a variable in a stack frame that is no longer present. Turner notes that Landin's SECD machine solves this problem (thus allowing functions to return functions), as a function value is now represented with a closure on the heap that can store the environment of variables it should use irrespective of what happens on the stack.

When evaluation of an expression begins, the expression is loaded as the only element of control C. The environment E, stack S and dump D begin empty. During evaluation of C it is converted to reverse Polish notation (RPN) with ap (for apply) being the only operator. For example, the expression F (G X) (a single list element) is changed to the list X:G:ap:F:ap. Evaluation of C proceeds similarly to other RPN expressions. If the first item in C is a value, it is pushed onto the stack S. More exactly, if the item is an identifier, the value pushed onto the stack will be the binding for that identifier in the current environment E. If the item is an abstraction, a closure is constructed to preserve the bindings of its free variables (which are in E), and it is this closure which is pushed onto the stack. If the item is ap, two values are popped off the stack and the application done (first applied to second). If the result of the application is a value, it is pushed onto the stack. If the application is of an abstraction to a value, however, it will result in a lambda calculus expression that may itself be an application (rather than a value), and so cannot be pushed onto the stack. In this case, the current contents of S, E, and C are pushed onto the dump D (which is a stack of these triples), S is reinitialized to empty, and C is reinitialized to the application result with E containing the environment for the free variables of this expression, augmented with the binding that resulted from the application. Evaluation then proceeds as above. Completed evaluation is indicated by C being empty, in which case the result will be on the stack S. The last saved evaluation state on D is then popped, and the result of the completed evaluation is pushed onto the stack contents restored from D. Evaluation of the restored state then continues as above. If C and D are both empty, overall evaluation has completed with the result on the stack S.