X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=advanced_topics%2Fcalculator_improvements.mdwn;h=4f24f877c52e21ab64439e2d39e6f53add7946fc;hp=4ddff2797d5d33c48ee4c5e21e2e6e3af79e0ab6;hb=88f7b0444146d9379521cc31ad9ef87b909e0b3b;hpb=bd2c74b88855aafb6a4685591eb4e401751edd60;ds=sidebyside diff --git a/advanced_topics/calculator_improvements.mdwn b/advanced_topics/calculator_improvements.mdwn index 4ddff279..4f24f877 100644 --- a/advanced_topics/calculator_improvements.mdwn +++ b/advanced_topics/calculator_improvements.mdwn @@ -57,7 +57,7 @@ We'll switch over to using variable `g` for assignment functions, which is a con type bound_value = expressed_value;; type assignment = (char * bound_value) list;; -Here's where we should be now. We expand some of the clauses in the `eval` function for clarity: +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) @@ -79,14 +79,14 @@ Here's where we should be now. We expand some of the clauses in the `eval` funct 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 *) @@ -120,7 +120,7 @@ We can begin with our language: | 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 @@ -143,7 +143,7 @@ Now our evaluation function needs two further clauses to interpret the two new e 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 *) @@ -157,7 +157,7 @@ Now our evaluation function needs two further clauses to interpret the two new e 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: @@ -208,11 +208,11 @@ And as a matter of fact, OCaml *does* permit us to recursively define cyclical l 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. @@ -220,15 +220,15 @@ However, this is a somewhat exotic ability in a programming language, so it woul 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. @@ -257,24 +257,24 @@ Since we're not permitting ourselves OCaml's ability to recursively define cycli 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 *) @@ -282,11 +282,11 @@ Since we're not permitting ourselves OCaml's ability to recursively define cycli (* 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';;