- | Variable c ->
- (* we don't handle cases where g doesn't bind c to any value *)
- List.assoc c g
- | Let (c, t1, t2) ->
- (* evaluate t2 under a new assignment where c has been bound to
+ | Variable var ->
+ (* we don't handle cases where g doesn't bind var to any value *)
+ List.assoc var g
+ | Let (var_to_bind, t1, t2) ->
+ (* evaluate t2 under a new assignment where var_to_bind has been bound to
-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:
+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 declaration's lexical environment. That shouldn't get shadowed by any different value `x` may have when the function value is later applied. So:
- | Lambda(c, t1) -> Closure (c, t1, g)
+ | Lambda(arg_var, t1) -> Closure (arg_var, t1, g)
- in let Closure (arg_var, body, savedg) = eval t1 g
+ let Closure (arg_var, body, savedg) = eval t1 g
+ in let value2 = eval t2 g
(* evaluate body under savedg, except with arg_var bound to value2 *)
in let savedg' = (arg_var, value2) :: savedg
in eval body savedg';;
(* evaluate body under savedg, except with arg_var bound to value2 *)
in let savedg' = (arg_var, value2) :: savedg
in eval body savedg';;
-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:
+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 `Variable '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:
-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.
+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 applications of `Variable 'f'` which recurse more than once.
let rec new_closure = Closure ('y', body, ('f', new_closure) :: savedg)
in new_closure
let rec new_closure = Closure ('y', body, ('f', new_closure) :: savedg)
in new_closure
(* we don't handle cases where t1 doesn't evaluate to a function value *)
let Closure (arg_var, body, savedg) = eval t1 g
(* we don't handle cases where t1 doesn't evaluate to a function value *)
let Closure (arg_var, body, savedg) = eval t1 g
- in let rec new_closure = Closure (arg_var, body, (c, new_closure) :: savedg)
- in let g' = (c, new_closure) :: g
+ in let rec new_closure = Closure (arg_var, body, (var_to_bind, new_closure) :: savedg)
+ in let g' = (var_to_bind, new_closure) :: g
in eval t2 g';;
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.
in eval t2 g';;
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.
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:
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:
- in let rec savedg' = fun var -> if var = c then Closure (arg_var, body, savedg') else savedg var
- in let g' = fun var -> if var = c then Closure (arg_var, body, savedg') else g var
+ in let rec savedg' = fun var -> if var = var_to_bind then Closure (arg_var, body, savedg') else savedg var
+ in let g' = fun var -> if var = var_to_bind then Closure (arg_var, body, savedg') else g var
in eval t2 g';;
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.
in eval t2 g';;
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.
Letrec ('f', Lambda ('y', Variable 'f')),
...)
Letrec ('f', Lambda ('y', Variable 'f')),
...)
-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:
+In the first case, an application of `Variable 'f'` to any argument should evaluate to `Int 1`; in the second case, it should evaluate to the same function closure that `Variable 'f'` evaluates to. We'll keep track of which way a variable was bound by expanding our `bound_value` type:
type expressed_value = Int of int | Bool of bool | Closure of char * term * assignment
and bound_value = Nonrecursive of expressed_value |
type expressed_value = Int of int | Bool of bool | Closure of char * term * assignment
and bound_value = Nonrecursive of expressed_value |
-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:
+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 that 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* `Variable 'f'`. The result will look like this:
| Nonrecursive value -> value
| Recursive_Closure (self_var, arg_var, body, savedg) as rec_closure ->
(* we update savedg to bind self_var to rec_closure here *)
let savedg' = (self_var, rec_closure) :: savedg
in Closure (arg_var, body, savedg')
)
| Nonrecursive value -> value
| Recursive_Closure (self_var, arg_var, body, savedg) as rec_closure ->
(* we update savedg to bind self_var to rec_closure here *)
let savedg' = (self_var, rec_closure) :: savedg
in Closure (arg_var, body, savedg')
)
the result of evaluating t1 under the current assignment *)
let value1 = eval t1 g
(* we have to wrap value1 in Nonrecursive *)
the result of evaluating t1 under the current assignment *)
let value1 = eval t1 g
(* we have to wrap value1 in Nonrecursive *)
- | Lambda(c, t1) -> Closure (c, t1, g)
+ | Lambda(arg_var, t1) -> Closure (arg_var, t1, g)
- in let Closure (arg_var, body, savedg) = eval t1 g
+ let Closure (arg_var, body, savedg) = eval t1 g
+ in let value2 = eval t2 g
(* evaluate body under savedg, except with arg_var bound to Nonrecursive value2 *)
in let savedg' = (arg_var, Nonrecursive value2) :: savedg
in eval body savedg'
(* evaluate body under savedg, except with arg_var bound to Nonrecursive value2 *)
in let savedg' = (arg_var, Nonrecursive value2) :: savedg
in eval body savedg'
(* we don't handle cases where t1 doesn't evaluate to a function value *)
let Closure (arg_var, body, savedg) = eval t1 g
(* we don't handle cases where t1 doesn't evaluate to a function value *)
let Closure (arg_var, body, savedg) = eval t1 g
- (* evaluate t2 under a new assignment where c has been recursively bound to that function value *)
- in let g' = (c, Recursive_Closure(c, arg_var, body, savedg)) :: g
+ (* evaluate t2 under a new assignment where var_to_bind has been recursively bound to that function value *)
+ in let g' = (var_to_bind, Recursive_Closure(var_to_bind, arg_var, body, savedg)) :: g