Before going further, let’s take a shot at understanding why the two interpreters behave differently on the same syntax. First, we will examine a case where they produce the same result:
First, the immediate substitution interpreter defined by
Each step represents one recursive call to
evals. The first step immediately substitutes
n throughout the remainder of the expression. The second does the same for
f. Finally, the
app evaluates substituting
x+1. The resulting value is
Now let’s look at the defered substitution interpreter implemented by
bind adds a binding from
1 while the second adds a binding from
f to the lambda expression. The term
app f 1 is evaluated in the context of the resulting environment.
f is first replaced by the lambda, then $\beta$-reduction adds a binding of
x in. Now the term can be evaluated.
x is replaced by
1 and we’re done. The result is again
What happens in the second example using nested binds? Again, let’s look at the immediate substitution interpreter:
Immediate substitution results in
2 again following roughly the same steps as before. The interesting step to pay attention to is the second substitution of
n. The first substitution replace
n in the
lambda, thus no
n is present for the inner
bind to replace.
Now compare to the deferred substitution evaluator:
The result is
3, but why? The second
bind is key to understanding what happens.
bind adds bindings to the environment when deferring substition while
bind substitutes immediately when using direct substitution. By the time deferred substitution occurs,
(n,2) has been added to the environment where it shadows the original
(n,1) binding. Thus, when
x+n is evaluated, we get
1+2 rather than
Where the two interpreters differ is in their implementation of scope. The immediate substitution interpreter implements static scoping while the deferred substitution interpreter implements dynamic scoping. In dynamic scoping, the environment used when evaluating a function is the environment where the function is evaluated. In the example above,
f is evaluated in the environment where it is called -
n is bound to
f to the lambda. Thus, the deferred substitution interpreter implements dynamic scoping.
Clearly dynamic scoping differs from our reference implementation. However, is that a bad thing? Most programming language researchers would say yes. Here’s a good example why that’s the case:
In this expression, every time
f 1 is evaluated, the result is different. Every time
f 1 is evaluted, the current environment must be known to determine the result. Same function, same arguments, different result. This is a debugging nightmare and generally, dynamic scoping is to be avoided.
Assuming the immediate substitution interpreter implements a reference interpreter, we need the substituting interpreter to produce the same values. Specifically, we need
f to use the environment where it is defined rather than where it is called. Unfortunately, it’s gone when
f is evaluated.
The approach we’ll use is to keep a copy of the environment where a function is defined. In effect, we’ll put a copy of the environment in the lambda value when the lambad is defined. This structure is called a closure. To implement closures we’re going to need to change several things in our interpreter.
To understand how a closure will work, lets consider the problematic
bind evaluation from earlier in the chapter. Recall that when
x + n evaluates, the environment used is the dynamic environment where
n is bound to
However, immediate substitution uses the static binding of
f is defined. We call the environment
[(n,1)] where the
f is defined the static scope of
f. In contrast, the environment:
f is called is the dynamic scope of
f. In general, the term static refers to definition time while the term dynamic refers to run time. If we could use the static scope of
f when evaluation occurs, all instances of
app f 1 generate the same value and the evaluation result matches the immediate substitution result. What we want is the following trace where the static scope gets used for evaluation:
Having information from the
lambda definition plus the static environment in one data structure is a closure. Psuedo-Haskell for the closure would be:
As we shall see, implementing the closure is a simple extension of what we already do. Remember that for now a
lambda is a value. What if somehow we tuck the static environment into the
All our interpreters thus far have taken an AST as input and produced an AST of the same type as output. For example,
eval for the
FBAE interpreter has the signature:
eval’s type is not specific. There are many elements of
FBAE that should not be returned by eval. In fact, there are far more
FBAE constructs that should not be return than should.
What we would like is for
eval to return a value. As we’ve said before, a value is a term that cannot be evaluated further. Let’s go further and define a value type that interpreters must return:
where the definition of
FBAEVal might have the form:
Now the interpreter must return a value and that value is distiguishable from traditional AST elements.
We’ve defined static and dynamic scoping and said that for static scoping the static enviornment must be included in a function value. We’ve defined the concept of a value and defined a type for values. Just put the concepts together to define a value that includes closures:
NumV definition is for number values.
NumV is structually the same as
Num, but is an element of the value type rather than the AST type. The
ClosureV definition modifies
Lambda adding an
Env element. This new element represents the static environment necessary to implement static scoping.
ClosureV adds an environment value to a lambda value without making an addition to the AST definition.
Weaving this new definition througout the
FBAE interpreter is a matter of tweaking existing code. First, the environment should contain values and not AST elements. This change is simple requiring only a change to the
Env type definition:
Walking through the interpreter reveals additional changes. The signature is updated to reflect return of an
Evaluating a number now results in a
Bind, evaluating subterms results in values rather than AST elements. Changes are minimal thanks to pattern matching:
When evaluting a
Lambda we capture the static environment. In the case for
Lambda, the environment passed into the interpreter is bound to
env. Creating the closure value takes
env and saves its value in the closure value:
Using the closure value is surprisingly simple. In the evaluation of
App in the dynamically scoped interpreter, the environment for evaluating the function body is the dynamic environment updated with the lambda argument. Specifically:
Instead of using the dynamic environment, we use the environment from the closure being applied. This value is found bound to
e in the expression. The new environment for evaluating the function body becomes
((i,a'):e) and is used as follows:
Other than updates to the environment, the evaluation of
App is completely unchanged.
Finally, the remaining cases are largely unchanged. The
If construct must be updated to use values, but otherwise is identical to the dynamically scoped iterpreter.
Putting everything together gives us the following interpreter:
To make sure we’ve implemented our statically scoped interpreter correctly, we can go back to the test case that caused our problems to begin with:
Interpreting this expression with our new inerpreter gives precisely the result hoped for.