X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=advanced_topics%2Fcalculator_improvements.mdwn;h=7576b22e2df86a69b8c44f1aceaddd120944513c;hp=3e51c95b992d90170d8a87044b860312fc382fd1;hb=8851b9a8232b479f166c711beae3cc6a665b047c;hpb=1fd1fc4930f5d25e7de28532cdefbe103d4b3a1b diff --git a/advanced_topics/calculator_improvements.mdwn b/advanced_topics/calculator_improvements.mdwn index 3e51c95b..7576b22e 100644 --- a/advanced_topics/calculator_improvements.mdwn +++ b/advanced_topics/calculator_improvements.mdwn @@ -369,7 +369,7 @@ Our evaluation function will now expect a `store` argument as well as an `assign let rec eval (t : term) (g : assignment) (s : store) = match t with Intconstant x -> (Int x, s) ... - | Variable (var) -> ( + | 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 @@ -377,7 +377,7 @@ Our evaluation function will now expect a `store` argument as well as an `assign (* we update savedg to bind self_var to rec_closure here *) let savedg' = (self_var, rec_closure) :: savedg in Closure (arg_var, body, savedg') - ), s + ), s) ... | Lambda (arg_var, t2) -> (Closure (arg_var, t2, g), s) ... @@ -448,12 +448,12 @@ Now we need to formulate the clauses for evaluating the new forms `Newref (...)` ... | Newref (t1) -> - let (starting_val, s') = eval t1 g s + let (value1, s') = eval t1 g s (* note that s' may be different from s, if t1 itself contained any mutation operations *) (* now we want to retrieve the next free index in s' *) in let new_index = List.length s' - (* now we want to insert starting_val there; the following is an easy but inefficient way to do it *) - in let s'' = List.append s' [starting_val] + (* now we want to insert value1 there; the following is an easy but inefficient way to do it *) + in let s'' = List.append s' [value1] (* now we return a pair of a wrapped new_index, and the new store *) in (Mutcell new_index, s'') | Deref (t1) -> @@ -465,12 +465,12 @@ Now we need to formulate the clauses for evaluating the new forms `Newref (...)` (* we don't handle cases where t1 doesn't evaluate to a Mutcell *) let (Mutcell index1, s') = eval t1 g s (* note that s' may be different from s, if t1 itself contained any mutation operations *) - in let (new_value, s'') = eval t2 g s' - (* now we create a list which is just like s'' except it has new_value in index1 *) + in let (value2, s'') = eval t2 g s' + (* now we create a list which is just like s'' except it has value2 in index1 *) in let rec replace_nth lst m = match lst with | [] -> failwith "list too short" - | x::xs when m = 0 -> new_value :: xs + | x::xs when m = 0 -> value2 :: xs | x::xs -> x :: replace_nth xs (m - 1) in let s''' = replace_nth s'' index1 (* we'll arbitrarily return Int 42 as the expressed_value of a Setref operation *) @@ -538,12 +538,12 @@ Finally, here are the changed or added clauses to the evaluation function: (* we don't handle cases where t1 doesn't evaluate to a Pair *) let (Pair (index1, index2), s') = eval t1 g s (* note that s' may be different from s, if t1 itself contained any mutation operations *) - in let (new_value, s'') = eval t2 g s' - (* now we create a list which is just like s'' except it has new_value in index1 *) + in let (value2, s'') = eval t2 g s' + (* now we create a list which is just like s'' except it has value2 in index1 *) in let rec replace_nth lst m = match lst with | [] -> failwith "list too short" - | x::xs when m = 0 -> new_value :: xs + | x::xs when m = 0 -> value2 :: xs | x::xs -> x :: replace_nth xs (m - 1) in let s''' = replace_nth s'' index1 in (Int 42, s''') @@ -585,7 +585,7 @@ In the present implementation, we separate the roles of the `bound_value` and `e type store = expressed_value list;; -Our evaluation function still interacts with a `store` argument in much the same way it did with explicit-style mutation. The clause for `Variable ...` works differently, because all `expressed_value`s now need to be retrieved from the `store`: +Our evaluation function still interacts with a `store` argument in much the same way it did with explicit-style mutation. The clause for `Variable (...)` works differently, because all `expressed_value`s now need to be retrieved from the `store`: let rec eval (t : term) (g : assignment) (s : store) = match t with ... @@ -655,12 +655,51 @@ Finally, here is the clause for `Change (...)`, which takes over the role earlie in eval t3 g s'' ;; -Note that because the `savedg` component of a `Closure` keeps track of which `index`es in the store free variables were bound to, the values at those `index`es can later be changed, and later applications of the `Closure` will use the changed values. +Note that because the `savedg` component of a `Closure` keeps track of which `index`es in the store---rather than which values---free variables were bound to, the values at those `index`es can later be changed, and later applications of the `Closure` will use the changed values. The complete code is available [here](/code/calculator/calc6.ml). ##Adding Aliasing and Passing by Reference## +Next we'll add aliasing as described at the end of [[week9]]. We'll also add the ability to pass (implicit) reference cells as arguments to a function, which lets changes made within the function body to be effective in the outside environment. When we discussed this in [[week9]], we proposed a different syntactic form for the function values that get called in this way. Instead of: + + let f = lambda (y) -> ... + ... + in f x + +one would write: + + let f = lambda (alias y) -> ... + ... + in f x + +Real programming languages that have this ability, such as C++, do something analagous. Here the function is declared so that *all* of its applications are expected to alias the supplied argument. You can always work around that in a particular case, though, like this: + + let f = lambda (alias y) -> ... + ... + in let y = x ; creates new (implicit) reference cell with x's value + in f y + +In our present framework, it will be easier to do things differently. We will +introduce a new syntactic forms at the location where a function value is +applied, rather than in the function's declaration. So we will say instead: + + Let ('f', + Lambda ('y', ...), + ... + Apply(Variable 'f', Variable 'x')...) + +for the familiar, passing-by-value behavior, and: + + Let ('f', + Lambda ('y', ...), + ... + Applyalias(Variable 'f', 'x')...) + +for the proposed new, passing-by-reference behavior. (Besides being easier to implement here, this strategy also has the advantage of more closely aligning with the formal system Jim discusses in his "Hyper-evaluativity" paper.) Note that the second parameter to the `Applyalias` form is just `'x'`, not `Variable 'x'`. This is because (1) only variables are acceptable there, not arbitrary expressions, and (2) we don't need at that point to compute the variable's present value. + +Here is our expanded language: + type term = Intconstant of int | Multiplication of (term * term) @@ -679,6 +718,8 @@ The complete code is available [here](/code/calculator/calc6.ml). | Applyalias of (term * char) ;; +The definitions of `index`, `bound_value`, `assignment`, `expressed_value`, and `store` can remain as they were in the implementation of implicit-style mutation. Here are the changes to our evaluation function: + let rec eval (t : term) (g : assignment) (s : store) = match t with ... | Alias (var_to_bind, orig_var, t3) ->