7dc3cd4def17e6fcb793764104f9381af181c4d4
1 One strategy for evaluating or interpreting terms avoids the tedious and inefficient _substituting_
2 we've become familiar with. Instead, when a variable becomes bound to a result value, we'll
3 keep track of that binding in a separate scorecard, that we'll call an "environment."
5 This strategy has to introduce a new kind of structure, called a `Closure`, to handle
6 binding to terms that have locally free variables in them. Let's
7 see how this works. For exposition, I'll pretend that the code you're working with has
8 primitive numbers in it, though [[the homework assignment|/exercises/assignment7]] doesn't.
9 (But [[the fuller code|/topics/week7_untyped_evaluator]] it's simplified from does.)
11 Now consider:
13     term                             environment
14     ----                             -----------
15     (\w.(\y.y) w) 2                  []
16     (\y.y) w                         [w->2]
17     y                                [y->w, w->2]
19 In the first step, we bind `w` to the term `2`, by saving this association in our environment. In the second step, we bind `y` to the term `w`. In the third step, we would like to replace `y` with whatever its current value is according to our scorecard/environment. But a naive handling of this would replace `y` with `w`; and that's not the right result, because `w` should itself be mapped to `2`. On the other hand, in:
21     term                             environment
22     ----                             -----------
23     (\x w. x) w 2                    []
24     (\w. x) 2                        [x->w]
25     x                                [w->2, x->w]
27 Now our final term _should_ be replaced with `w`, not with `2`. So evidently it's not so simple as just recursively re-looking up variables in the environment.
29 A good strategy for handling these cases would be not to bind `y` to the term `w`, but rather to bind it to _what the term `w` then fully evaluates to_. Then in the first case we'd get:
31 <pre>
32 term                             environment
33 ----                             -----------
34 (\w.(\y.y) w) 2                  []
35 (\y.y) w                         [w->2]
36 y                                [<b>y->2</b>, w->2]
37 </pre>
39 And at the next step, `y` will evaluate directly to `2`, as desired. In the other example, though, `x` gets bound to `w` when `w` is already free. (In fact the code skeleton we gave you won't permit that to happen; it refuses to perform any applications except when the arguments are "result values", and it doesn't count free variables as such. As a result, other variables can never get bound to free variables.)
41 So far, so good.
43 But now consider the term:
45     (\f. x) ((\x y. y x) 0)
47 Since the outermost head `(\f. x)` is already a `Lambda`, we begin by evaluating the argument `((\x y. y x) 0)`. This results in:
49     term                             environment
50     ----                             -----------
51     (\f. x) (\y. y x)                [x->0]
53 But that's not right, since it will result in the variable `x` in the head also being associated with the argument `0`. Instead, we want the binding of `x` to `0` to be local to the argument term `(\y. y x)`. For the moment, let's notate that like this:
55 <pre>
56 term                             environment
57 ----                             -----------
58 (\f. x)<sub>1</sub> (\y. y x)<sub>2</sub>              []<sub>1</sub>   [x->0]<sub>2</sub>
59 </pre>
61 Now, let's suppose the head is more complex, like so:
63     (\f. (\x. f x) I) ((\x y. y x) 0)
65 That might be easier to understand if you transform it to:
67     let f = (let x = 0 in \y. y x) in
68     let x = I in
69     f x
71 Since the outermost head `(\f. (\x. f x) I)` is already a `Lambda`, we begin by evaluating the argument `((\x y. y x) 0)`. This results in:
73 <pre>
74 term                             environment
75 ----                             -----------
76 (\f. (\x. f x) I)<sub>1</sub> (\y. y x)<sub>2</sub>    []<sub>1</sub> [x->0]<sub>2</sub>
77 </pre>
79 Now the argument is not itself any longer an `App`, and so we are ready to evaluate the outermost application, binding `f` to the argument term. So we get:
81 <pre>
82 term                             environment
83 ----                             -----------
84 ((\x. f x) I)<sub>1</sub>                   [f->(\y. y x)<sub>2</sub>]<sub>1</sub> [x->0]<sub>2</sub>
85 </pre>
87 Next we bind `x` to the argument `I`, getting:
89 <pre>
90 term                             environment
91 ----                             -----------
92 (f x)<sub>1</sub>                           [x->I, f->(\y. y x)<sub>2</sub>]<sub>1</sub> [x->0]<sub>2</sub>
93 </pre>
95 Now we have to apply the value that `f` is bound to to the value that `x` is bound to. But notice there is a free variable `x` in the term that `f` is bound to. How should we interpret that term? Should the evaluation proceed:
97 <pre>
98 (\y. y <b>x<sub>1</sub></b>) x<sub>1</sub>                    [x->I, ...]<sub>1</sub> [x->0]<sub>2</sub>
99 y <b>x<sub>1</sub></b>                             [y->I, x->I, ...]<sub>1</sub> [x->0]<sub>2</sub>
100 I I
101 I
102 </pre>
104 using the value that `x` is bound to in context<sub>1</sub>, _where the `f` value is applied_? Or should it proceed:
106 <pre>
107 (\y. y <b>x<sub>2</sub></b>) x<sub>1</sub>                    [x->I, ...]<sub>1</sub> [x->0]<sub>2</sub>
108 y <b>x<sub>2</sub></b>                             [y->I, x->I, ...]<sub>1</sub> [x->0]<sub>2</sub>
109 I 0
110 0
111 </pre>
113 using the value that `x` was bound to in context<sub>2</sub>, _where `f` was bound_?
115 In fact, when we specified rules for the Lambda Calculus, we committed ourselves to taking the second of these strategies. But both of the kinds of binding described here are perfectly coherent. The first is called "dynamic binding" or "dynamic scoping" and the second is called "lexical or static binding/scoping". Neither is intrinsically more correct or appropriate than the other. The first is somewhat easier for the people who write implementations of programming languages to handle; so historically it used to predominate. But the second is easier for programmers to reason about.
117 > In Scheme, variables are bound in the lexical/static way by default, just as in the Lambda Calculus; but there is special vocabulary for dealing with dynamic binding too, which is useful in some situations. As far as I'm aware, Haskell and OCaml only provide the lexical/static binding. <em>Shell scripts</em>, on the other hand, only use dynamic binding. If you type this at a shell prompt: `( x=0; foo() { echo \$x; }; bar() { local x=1; foo; }; bar )`, it will print `1` not `0`.
119 In any case, if we're going to have the same semantics as the untyped Lambda Calculus, we're going to have to make sure that when we bind the variable `f` to the value `\y. y x`, that (locally) free variable `x` remains associated with the value `0` that `x` was bound to in the context where `f` is bound, not the possibly different value that `x` may be bound to later, when `f` is applied. One thing we might consider doing is _evaluating the body_ of the abstract that we want to bind `f` to, using the then-current environment to evaluate the variables that the abstract doesn't itself bind. But that's not a good idea. What if the body of that abstract never terminates? The whole program might be OK, because it might never go on to apply `f`. But we'll be stuck trying to evaluate `f`'s body anyway, and will never get to the rest of the program. Another thing we could consider doing is to substitute the `2` in for the variable `x`, and then bind `f` to `\y. y 2`. That would work, but the whole point of this evaluation strategy is to avoid doing those complicated (and inefficient) substitutions. Can you think of a third idea?
121 What we will do is have our environment associate `f` not just with a `Lambda` term, but also with the environment that was in place _when_ `f` was bound. Then later, if we ever do use `f`, we have that saved environment around to look up any free variables in. More specifically, we'll associate `f` not with the _term_:
123     Lambda("y", BODY)
125 but instead with the `Closure` structure:
127     Closure("y", BODY, SAVED_ENV)
129 where `BODY` is the term that constituted the body of the corresponding `Lambda`, and `SAVED_ENV` is the environment in place when `f` is being bound. (In this simple implementation, we will just save the _whole environment_ then in place. But in a more efficient implementation, we'd sift through it and only keep those bindings for variables that are free in `BODY`. That would take up less space.)