| Sussman and Steele | December 22, 1975 | 21 | Some Implementation Issues |
Section 4: Some Implementation Issues
The key problem is efficiency. Although it is easy to build an inefficient interpreter which straightforwardly performs expression substitutions; such an interpreter performs much unnecessary copying of intermediate expressions. The standard solution to this problem is to use an auxiliary structure, called the environment, which represents a set of virtual substitutions. Thus, when evaluating an expression of the form
in environment
instead of reducing it by performing
Subst[<args> <vars> <body>]
we reduce it to
<body>in environment
where pairlis creates a new environment E' in which the <vars> are logically paired with (i.e. "bound to") the corresponding <args>* (the precise meaning of <args>* will be explained presently), and in which any variables not in <vars> are bound as they were in E.
When using environments, it is necessary to keep them straight. For example, the following expression should manage to evaluate to 7:
(((LAMBDA (X) (LAMBDA (Y) (+ X Y))) 3) 4)
A substitution interpreter would cause the free occurrence of x in the inner lambda expression to be replaced by 3 before applying that lambda expression to 4. An interpreter which uses environments must arrange for the expression (+ x y) to be evaluated in an environment such that x is bound to 3 and y is bound to 4. This implies that when the inner lambda expression is applied to 4, there must be associated with it an environment in which x is bound to 3. In order to solve this problem we introduce the notion of a closure [McCarthy] [Moses] which is a data structure containing a lambda expression, and an environment to be used when that lambda expression is applied to arguments. We will notate a closure using the beta construct (our own notation, but isomorphic to the LISP funarg construct) as follows:
(BETA (LAMBDA <vars> <body>) <environment>)
When a lambda expression is to be evaluated, because it was passed as an argument, it evaluates to a closure of that lambda expression in the environment it is evaluated in (i.e., the environment it was passed from):
in environment
