Editing SECD machine (section)

==Informal description==
When evaluation of an expression begins, the expression is loaded as the only element of control '''<code>C</code>'''. The environment '''<code>E</code>''', stack '''<code>S</code>''' and dump '''<code>D</code>''' begin empty.

During evaluation of '''<code>C</code>''' it is converted to [[reverse Polish notation]] (RPN) with <code>ap</code> (for [[apply]]) being the only operator. For example, the expression <code>F (G X)</code> (a single list element) is changed to the list <code>X:G:ap:F:ap</code>.

Evaluation of '''<code>C</code>''' proceeds similarly to other RPN expressions. If the first item in '''<code>C</code>''' is a value, it is pushed onto the stack '''<code>S</code>'''. 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 '''<code>E</code>'''. If the item is an abstraction, a [[closure (computer science)|closure]] is constructed to preserve the bindings of its free variables (which are in '''<code>E</code>'''), and it is this closure which is pushed onto the stack.

If the item is '''<code>ap</code>''', 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 '''<code>S</code>''', '''<code>E</code>''', and '''<code>C</code>''' are pushed onto the dump '''<code>D</code>''' (which is a stack of these triples), '''<code>S</code>''' is reinitialized to empty, and '''<code>C</code>''' is reinitialized to the application result with '''<code>E</code>''' 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 '''<code>C</code>''' being empty, in which case the result will be on the stack '''<code>S</code>'''. The last saved evaluation state on '''<code>D</code>''' is then popped, and the result of the completed evaluation is pushed onto the stack contents restored from '''<code>D</code>'''. Evaluation of the restored state then continues as above.

If '''<code>C</code>''' and '''<code>D</code>''' are both empty, overall evaluation has completed with the result on the stack '''<code>S</code>'''.