tweak calc improvements

[lambda.git] / advanced_topics / calculator_improvements.mdwn

diff --git a/advanced_topics/calculator_improvements.mdwn b/advanced_topics/calculator_improvements.mdwn
index e22afb1..68bd39d 100644 (file)
--- 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);;
 
                | 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 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) ->
        ...
        | 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 *)
                (* 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';;
                (* 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:
 
 
 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:
 
 
 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);;
 
                | 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)
 
 
        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?
 
 
 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
 
        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
 
        | 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 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';;
 
                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')),
                ...)
 
                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 |


@@ -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;;
 
 
        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
        ...
 
        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) ->
        ...
        | 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 *)
                (* 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'
                (* evaluate body under savedg, except with arg_var bound to Nonrecursive value2 *)
                in let savedg' = (arg_var, Nonrecursive value2) :: savedg
                in eval body savedg'