X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=advanced_topics%2Fcalculator_improvements.mdwn;h=68bd39d8b44a8886bf2d0be673b33426ed12bc3e;hp=e22afb1aa62904e601ee7ef17e774317b0335fb1;hb=2cef07bcbf221a75e0cf0da553be6566a206d68f;hpb=3ae2b6a91a7bacea08d522cb94f78b2c7b2d95c9 diff --git a/advanced_topics/calculator_improvements.mdwn b/advanced_topics/calculator_improvements.mdwn index e22afb1a..68bd39d8 100644 --- a/advanced_topics/calculator_improvements.mdwn +++ b/advanced_topics/calculator_improvements.mdwn @@ -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 @@ -145,9 +145,9 @@ Now our evaluation function needs two further clauses to interpret the two new e ... | 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 *) - 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';; @@ -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: @@ -184,7 +184,7 @@ Here is the expanded definition for our language type: | Apply of (term * term) | Letrec of (char * term * term);; -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: Closure ('y', body, savedg) @@ -197,9 +197,9 @@ but instead to: Except, this isn't quite right. It's almost what we want, but not exactly. Can you see the flaw? -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. -What we really want is for `f` to be bound to `new_closure`, something like this: +What we really want is for `'f'` to be bound to `new_closure`, something like this: let rec new_closure = Closure ('y', body, ('f', new_closure) :: savedg) in new_closure @@ -222,12 +222,12 @@ If we implemented assignments as functions rather than as lists of pairs, the co | Let (var_to_bind, t1, t2) -> let value1 = eval t1 g - in let g' = fun var -> if var = var_to_bind value1 else g var + in let g' = fun var -> if var = var_to_bind then value1 else g var in eval t2 g' ... | Letrec (var_to_bind, t1, t2) -> let Closure (arg_var, body, savedg) = eval t1 g - in let rec savedg' = fun var -> if var = var_to_bind Closure (arg_var, body, savedg') else savedg 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';; @@ -245,7 +245,7 @@ The way we'll do this is that, when we bind a value to a variable, we'll keep tr 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 | @@ -253,7 +253,7 @@ In the first case, an application of `f` to any argument should evaluate to `Int and assignment = (char * bound_value) list;; -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: let rec eval (t : term) (g: assignment) = match t with ... @@ -276,9 +276,9 @@ Since we're not permitting ourselves OCaml's ability to recursively define cycli ... | 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 *) - 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'