1 [[!toc]]
5 ##Original Calculator##
7 In a real programming application, one would usually start with a string that needs to be parsed and interpreted, such as:
9         let x = 1 in let y = x + 2 in x * y
11 The parsing phase converts this to an "abstract syntax tree" (AST), which in this case might be:
13         Let ('x', Constant 1,
14                  Let ('y', Addition (Variable 'x', Constant 2),
15                           Multiplication (Variable 'x', Variable 'y')))
17 Then the interpreter (or "evaluator") would convert that AST into an "expressed value": in this case, to the integer 3. We're not concerning ourselves with the parsing phase here, so we're just thinking about how to interpret expressions that are already in AST form.
19 The language we had in week 7 looked like this:
21         type term = Constant of int
22                 | Multiplication of (term * term)
23                 | Addition of (term * term)
24                 | Variable of char
25                 | Let of (char * term * term);;
27 and the evaluation function looked like this:
29         let rec eval (t : term) (e: (char * int) list) = match t with
30           Constant x -> x
31         | Multiplication (t1,t2) -> (eval t1 e) * (eval t2 e)
32         | Addition (t1,t2) -> (eval t1 e) + (eval t2 e)
33         | Variable c ->
34                 (* lookup the value of c in the current environment
35                    This will fail if c isn't assigned anything by e *)
36                 List.assoc c e
37         | Let (c,t1,t2) ->
38                 (* evaluate t2 in a new environment where c has been associated
39                    with the result of evaluating t1 in the current environment *)
40                 eval t2 ((c, eval t1 e) :: e);;
45 Let's tweak this a bit.
47 First, let's abstract away from the assumption that our terms always evaluate to `int`s. Let's suppose they evaluate to a more general type, which might have an `int` payload, or might have, for example, a `bool` payload.
49         type expressed_value = Int of int | Bool of bool;;
51 We'll add one boolean predicate, `Iszero`, and an `If...` construction.
53 We won't try here to catch any type errors, such as attempts to add a `bool` to an `int`, or attempts to check whether a `bool` iszero. Neither will we try here to monadize anything: these will be implementations of a calculator with all the plumbing exposed. What we will do is add more and more features to the calculator.
55 We'll switch over to using variable `g` for assignment functions, which is a convention many of you seem familiar with. As we mentioned a few times in week 9, for some purposes it's easier to implement environment or assignment functions as functions from `char`s to `int`s (or whatever variables are bound to), rather than as lists of pairs. However, we'll stick with this implementation for now. We will however abstract out the type that the variables are bound to. For now, we'll suppose that they're bound to the same types that terms can express.
57         type bound_value = expressed_value;;
58         type assignment = (char * bound_value) list;;
60 Here's where we should be now. We expand some of the clauses in the `eval` function for clarity:
62         type term = Constant of int
63                 | Multiplication of (term * term)
64                 | Addition of (term * term)
65                 | Variable of char
66                 | Let of (char * term * term)
67                 | Iszero of term
68                 | If of (term * term * term);;
70         let rec eval (t : term) (g: assignment) = match t with
71           Constant x -> Int x
72         | Multiplication (t1, t2) ->
73                 (* we don't handle cases where the subterms don't evaluate to Ints *)
74                 let Int value1 = eval t1 g
75                 in let Int value2 = eval t2 g
76                 (* Multiplication (t1, t2) should evaluate to an Int *)
77                 in Int (value1 * value2)
78         | Addition (t1, t2) ->
79                 let Int value1 = eval t1 g
80                 in let Int value2 = eval t2 g
81                 in Int (value1 + value2)
82         | Variable c ->
83                 (* we don't handle cases where g doesn't bind c to any value *)
84                 List.assoc c g
85         | Let (c, t1, t2) ->
86                 (* evaluate t2 under a new assignment where c has been bound to
87                    the result of evaluating t1 under the current assignment *)
88                 let value1 = eval t1 g
89                 in let g' = (c, value1) :: g
90                 in eval t2 g'
91         | Iszero t1 ->
92                 (* we don't handle cases where t1 doesn't evaluate to an Int *)
93                 let Int value1 = eval t1 g
94                 (* Iszero t1 should evaluate to a Bool *)
95                 in Bool (value1 = 0)
96         | If (t1, t2, t3) ->
97                 (* we don't handle cases where t1 doesn't evaluate to a boolean *)
98                 let Bool value1 = eval t1 g
99                 in if value1 then eval t2 g
100                 else eval t3 g;;
105 Now we want to add function values to our language, so that we can interpret (the abstract syntax trees of) expressions like this:
107         let x = 1 in let f = lambda y -> y + x in apply f 2
109 What changes do we need to handle this?
111 We can begin with our language:
113         type term = Constant of int
114                 | Multiplication of (term * term)
115                 | Addition of (term * term)
116                 | Variable of char
117                 | Let of (char * term * term)
118                 | Iszero of term
119                 | If of (term * term * term)
120                 | Lambda of (char * term)
121                 | Apply of (term * term);;
123 Next, we need to expand our stock of `expressed_value`s to include function values as well. How should we think of these? We've several times mentioned the issue of how to handle free variables in a function's body, like the `x` in `lambda y -> y + x`. We'll follow the usual functional programming standard for these (known as "lexical scoping"), which keeps track of what value `x` has in the function expression's lexical environment. That shouldn't get shadowed by any different value `x` may have when the function value is later applied. So:
125         let x = 1 in let f = lambda y -> y + x in let x = 2 in apply f 2
127 should evaluate to `3` not to `4`. To handle this, the function values we construct need to keep track of the present values of all free variables in the function's body. The combination of the function's body and the values of its free variables is called a "function closure." We'll implement these closures in a straightforward though inefficient way: we'll just stash away a copy of the assignment in effect when the function value is being constructed. Our function values also need to keep track of which of their variables are to be bound to the arguments they get applied to. All together, then, we need three pieces of information: which variables are to be bound to arguments, what the function's body is, and something that keeps track of the right values for the free variables in the function body. We'll pack this all together into an additional variant for our `expressed_value` type:
129         type expressed_value = Int of int | Bool of bool | Closure of char * term * assignment;;
131 We'd like to define `bound_value`s and `assignment`s just as before:
133         type bound_value = expressed_value;;
134         type assignment = (char * bound_value) list;;
136 However, note that we have a recursive relation between these types: `expressed_value` is defined partly in terms of `assignment`, which is defined partly in terms of `bound_value`, which is equivalent to `expressed_value`. In OCaml one has to define such types using the following form:
138         type expressed_value = Int of int | Bool of bool | Closure of char * term * assignment
139         and bound_value = expressed_value
140         and assignment = (char * bound_value) list;;
142 Now our evaluation function needs two further clauses to interpret the two new expression forms `Lambda(...)` and `Apply(...)`:
144         let rec eval (t : term) (g: assignment) = match t with
145         ...
146         | Lambda(c, t1) -> Closure (c, t1, g)
147         | Apply(t1, t2) ->
148                 let value2 = eval t2 g
149                 (* we don't handle cases where t1 doesn't evaluate to a function value *)
150                 in let Closure (arg_var, body, savedg) = eval t1 g
151                 (* evaluate body under savedg, except with arg_var bound to value2 *)
152                 in let savedg' = (arg_var, value2) :: savedg
153                 in eval body savedg';;
158 There are different ways to include recursion in our calculator. First, let's imagine our language expanded like this:
160         let x = 1 in letrec f = lambda y -> if iszero y then x else y * f (y - 1) in f 3
162 where the AST would be:
164         Let('x', Constant 1,
165                 Letrec ('f',
166                         Lambda ('y',
167                                 If (Iszero (Variable 'y'),
168                                         Variable 'x',
169                                         Multiplication (Variable 'y',
170                                                 Apply (Variable 'f',
171                                                         Addition (Variable 'y', Constant (-1)))))),
172                         Apply (Variable 'f', Constant 3)))
174 Here is the expanded definition for our language type:
176         type term = Constant of int
177                 | Multiplication of (term * term)
178                 | Addition of (term * term)
179                 | Variable of char
180                 | Let of (char * term * term)
181                 | Iszero of term
182                 | If of (term * term * term)
183                 | Lambda of (char * term)
184                 | Apply of (term * term)
185                 | Letrec of (char * term * term);;
187 Now consider what we'll need to do when evaluating a term like `Letrec ('f', Lambda (...), t2)`. The subterm `Lambda (...)` will evaluate to something of the form `Closure ('y', body, savedg)`, where `f` may occur free in `body`. What we'll want to do is to ensure that when `body` is applied, it's applied using not the assignment `savedg` but a modified assignment `savedg'` which binds `f` to this very function value. That is, we want to bind `f` not to:
189         Closure ('y', body, savedg)
193         let orig_closure = Closure ('y', body, savedg)
194         in let savedg' = ('f', orig_closure) :: savedg
195         in let new_closure = Closure ('y', body, savedg')
196         in new_closure
198 Except, this isn't quite right. It's almost what we want, but not exactly. Can you see the flaw?
200 The flaw is this: inside `new_closure`, what is `f` bound to? It's bound by `savedg'` to `orig_closure`, which in turn leaves `f` free (or bound to whatever existing value it had according to `savedg`). This isn't what we want. It'll break if we need to make recursive calls to `f` which go more than two levels deep.
202 What we really want is for `f` to be bound to `new_closure`, something like this:
204         let rec new_closure = Closure ('y', body, ('f', new_closure) :: savedg)
205         in new_closure
207 And as a matter of fact, OCaml *does* permit us to recursively define cyclical lists in this way. So a minimal change to our evaluation function would suffice:
209         let rec eval (t : term) (g: assignment) = match t with
210         ...
211         | Letrec (c, t1, t2) ->
212                 (* we don't handle cases where t1 doesn't evaluate to a function value *)
213                 let Closure (arg_var, body, savedg) = eval t1 g
214         in let rec new_closure = Closure (arg_var, body, (c, new_closure) :: savedg)
215         in let g' = (c, new_closure) :: g
216                 in eval t2 g';;
218 However, this is a somewhat exotic ability in a programming language, so it would be good to work out how to interpret `Letrec(...)` forms without relying on it.
220 If we implemented assignments as functions rather than as lists of pairs, the corresponding move would be less exotic. In that case, our `Let(...)` and `Letrec(...)` clauses would look something like this:
223         | Let (c, t1, t2) ->
224                 let value1 = eval t1 g
225                 in let g' = fun var -> if var = c then value1 else g var
226                 in eval t2 g'
227         ...
228         | Letrec (c, t1, t2) ->
229                 let Closure (arg_var, body, savedg) = eval t1 g
230                 in let rec savedg' = fun var -> if var = c then Closure (arg_var, body, savedg') else savedg var
231                 in let g' = fun var -> if var = c then Closure (arg_var, body, savedg') else g var
232                 in eval t2 g';;
234 and this is just a run-of-the-mill use of recursive functions. However, for this exercise we'll continue using lists of pairs, and work out how to interpret `Letrec(...)` forms using them.
236 The way we'll do this is that, when we bind a value to a variable, we'll keep track of whether the term was bound via `let` or `letrec`. We'll rely on that to interpret pairs of terms like these differently:
238         Let ('f',
239                 Constant 1,
240                 Let ('f', Lambda ('y', Variable 'f')),
241                 ...)
243         Let ('f',
244                 Constant 1,
245                 Letrec ('f', Lambda ('y', Variable 'f')),
246                 ...)
248 In the first case, an application of `f` to any argument should evaluate to `Int 1`; in the second case, it should evaluate to the same function closure that `f` evaluates to. We'll keep track of which way a variable was bound by expanding our `bound_value` type:
250         type expressed_value = Int of int | Bool of bool | Closure of char * term * assignment
251         and bound_value = Nonrecursive of expressed_value |
252                 Recursive_Closure of char * char * term * assignment
253         and assignment = (char * bound_value) list;;
256 Since we're not permitting ourselves OCaml's ability to recursively define cyclical lists, we're not going to be able to update the saved assignment in a closure when that closure is recursively bound to a variable. Instead, we'll just make a note of what variable `f` is supposed to be the recursively bound one---by binding it not to `Nonrecursive (Closure (arg_var, body, savedg))` but rather to `Recursive_Closure ('f', arg_var, body, savedg)`. We'll do the work to make the saved assignment recursive in the right way *later*, when we *evaluate* `f`. The result will look like this:
258         let rec eval (t : term) (g: assignment) = match t with
259         ...
260         | Variable c -> (
261                 (* we don't handle cases where g doesn't bind c to any value *)
262                 match List.assoc c g with
263           | Nonrecursive value -> value
264           | Recursive_Closure (self_var, arg_var, body, savedg) as rec_closure ->
265                           (* we update savedg to bind self_var to rec_closure here *)
266               let savedg' = (self_var, rec_closure) :: savedg
267               in Closure (arg_var, body, savedg')
268         )
269         | Let (c, t1, t2) ->
270                 (* evaluate t2 under a new assignment where c has been bound to
271            the result of evaluating t1 under the current assignment *)
272                 let value1 = eval t1 g
273                 (* we have to wrap value1 in Nonrecursive *)
274                 in let g' = (c, Nonrecursive value1) :: g
275                 in eval t2 g'
276         ...
277         | Lambda(c, t1) -> Closure (c, t1, g)
278         | Apply(t1, t2) ->
279                 let value2 = eval t2 g
280                 (* we don't handle cases where t1 doesn't evaluate to a function value *)
281                 in let Closure (arg_var, body, savedg) = eval t1 g
282                 (* evaluate body under savedg, except with arg_var bound to Nonrecursive value2 *)
283                 in let savedg' = (arg_var, Nonrecursive value2) :: savedg
284                 in eval body savedg'
285         | Letrec (c, t1, t2) ->
286                 (* we don't handle cases where t1 doesn't evaluate to a function value *)
287                 let Closure (arg_var, body, savedg) = eval t1 g
288         (* evaluate t2 under a new assignment where c has been recursively bound to that function value *)
289                 in let g' = (c, Recursive_Closure(c, arg_var, body, savedg)) :: g
290                 in eval t2 g';;