Georgeff’s paper describes some schemes by which function-valued expressions under static scoping can be efficiently evaluated using a variant of SECD machines, as well as stack machines. One SECD variant transforms expressions into simple forms which can be evaluated in a stacklike runtime environment. Note that a typical SECD machine transforms expressions into tree-like environments. Another scheme of Georgeff’s describes a stack-machine that directly evaluates function-valued expressions without prior transformation of the expressions to simple form.

Transformations of expressions into simple form results in environmental structures that are stacklike. Two such compile-time transformations were developed in the paper. The author points out that transformation to simple form results in an increase in the number of transitions on the SECD machine by an arbitrary large factor. However, the evaluation of the transformed expression in a stacklike environment may still be more efficient than in the original (heap) environment. The reader is reminded that the final runtime efficiency of any evaluation scheme depends on the types of programs being run.

Georgeff also shows how the simple-form scheme and the direct-evaluation scheme could be used to extend the standard procedural languages in order to allow function-valued functions without the need for any additional runtime machinery.

The stack machines that are described and extended in this paper are variants of SECD machines. These variants exploit the notion of typed lambda expressions. Typed lambda expressions are defined using the notion of reduced reflexive types [1]. “An expression is a reducing reflexive type if it can act as a function in a (possibly) reflexive domain, but, when applied to sufficient arguments, results in a basic-valued expression.”

This paper is an extension of [2]. The extension provides some additional formalism, many examples, and more background material. Note, however, that many paragraphs, algorithms, and sections come from the author’s earlier paper.