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.
-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 as 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.
+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.
type bound_value = expressed_value;;
type assignment = (char * bound_value) list;;
-Here's where we should be now:
+Here's where we should be now. We expand some of the clauses in the `eval` function for clarity, and we rename a few variables:
type term = Constant of int
| Multiplication of (term * term)
let Int value1 = eval t1 g
in let Int value2 = eval t2 g
in Int (value1 + value2)
- | 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
the result of evaluating t1 under the current assignment *)
let value1 = eval t1 g
- in let g' = (c, value1) :: g
+ in let g' = (var_to_bind, value1) :: g
in eval t2 g'
| Iszero t1 ->
(* we don't handle cases where t1 doesn't evaluate to an Int *)
| Lambda of (char * term)
| Apply of (term * term);;
-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:
let x = 1 in let f = lambda y -> y + x in let x = 2 in apply f 2
let rec eval (t : term) (g: assignment) = match t with
...
- | Lambda(c, t1) -> Closure (c, t1, g)
+ | Lambda(arg_var, t1) -> Closure (arg_var, t1, g)
| Apply(t1, t2) ->
let value2 = eval t2 g
(* we don't handle cases where t1 doesn't evaluate to a function value *)
There are different ways to include recursion in our calculator. First, let's imagine our language expanded like this:
- let x = 1 in letrec f = lambda y -> if iszero y then x else y * f (y - 1) in f 3
+ let x = 1 in letrec f = lambda y -> if iszero y then x else y * apply f (y - 1) in apply f 3
where the AST would be:
let rec eval (t : term) (g: assignment) = match t with
...
- | Letrec (c, t1, t2) ->
+ | Letrec (var_to_bind, t1, t2) ->
(* 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.
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:
- | Let (c, t1, t2) ->
+ | Let (var_to_bind, t1, t2) ->
let value1 = eval t1 g
- in let g' = fun var -> if var = c then value1 else g var
+ in let g' = fun var -> if var = var_to_bind value1 else g var
in eval t2 g'
...
- | Letrec (c, t1, t2) ->
+ | Letrec (var_to_bind, t1, t2) ->
let Closure (arg_var, body, savedg) = eval t1 g
- 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 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.
let rec eval (t : term) (g: assignment) = match t with
...
- | Variable c -> (
- (* we don't handle cases where g doesn't bind c to any value *)
- match List.assoc c g with
+ | Variable var -> (
+ (* we don't handle cases where g doesn't bind var to any value *)
+ match List.assoc var g with
| 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')
)
- | Let (c, t1, t2) ->
- (* evaluate t2 under a new assignment where c has been bound to
+ | Let (var_to_bind, t1, t2) ->
+ (* evaluate t2 under a new assignment where var_to_bind has been bound to
the result of evaluating t1 under the current assignment *)
let value1 = eval t1 g
(* we have to wrap value1 in Nonrecursive *)
- in let g' = (c, Nonrecursive value1) :: g
+ in let g' = (var_to_bind, Nonrecursive value1) :: g
in eval t2 g'
...
- | Lambda(c, t1) -> Closure (c, t1, g)
+ | Lambda(arg_var, t1) -> Closure (arg_var, t1, g)
| Apply(t1, t2) ->
let value2 = eval t2 g
(* we don't handle cases where t1 doesn't evaluate to a function value *)
(* evaluate body under savedg, except with arg_var bound to Nonrecursive value2 *)
in let savedg' = (arg_var, Nonrecursive value2) :: savedg
in eval body savedg'
- | Letrec (c, t1, t2) ->
+ | Letrec (var_to_bind, t1, t2) ->
(* 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
in eval t2 g';;