From: Jim Pryor Date: Sun, 21 Nov 2010 01:45:45 +0000 (-0500) Subject: week9 implicit-style X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=767005e3dcdd7ba33a44d51b24fe729bd01a316e week9 implicit-style Signed-off-by: Jim Pryor --- diff --git a/week9.mdwn b/week9.mdwn index 27762802..e992bf44 100644 --- a/week9.mdwn +++ b/week9.mdwn @@ -318,7 +318,46 @@ With that kind of framework, we can interpret `newref`, `deref`, and `setref` as ##How to implement implicit-style mutable variables## --- FIXME -- +With implicit-style mutation, we don't have new syntactic forms like `newref` and `deref`. Instead, we just treat ordinary variables as being mutable. You could if you wanted to have some variables be mutable and others not; perhaps the first sort are written in Greek and the second in Latin. But we will suppose all variables in our language are mutable. + +We will still need a store to keep track of reference cells and their current values, just as in the explicit-style implementation. This time, every variable will be associated with an index into the store. So this is what we'll have our assignment function keep track of. The assignment function will bind variables to indexes into the store, rather than to the variables' current values. The variables will only indirectly be associated with those values by virtue of the joint work of the assignment function and the store. + +This brings up an interesting conceptual novelty. Formerly, we'd naturally think that a variable `x` is associated with only one type, and that that's the type that the expression `x` would *evaluate to*, and also the type of value that the assignment function *bound* `x` to. However, in the current framework these two types can come apart. The assignment function binds `x` to an index into the store, and what the expression `x` evaluates to will be the value at that location in the store, which might be some other type, such as a `bool` or a `string`. + +To handle implicit-style mutation, we'll need to re-implement the way we interpret expressions like `x`, `let x = expr1 in expr2`. We will have just one new syntactic form, `change x to expr1 then expr2`. + +Here's how to implement these. We'll suppose that our assignment function is list of pairs, as in [week6](/reader_monad_for_variable_binding). + + let rec eval expression g s = + match expression with + ... + | Var (c : char) -> + let index = List.assoc c g + in List.nth s index + + | Let (c : char) expr1 expr2 -> + let (starting_value, s') = eval expr1 g s + (* get next free index in s' *) + in let new_index = List.length s' + (* insert starting_value there *) + in let s'' = List.append s' [starting_value] + (* evaluate expr2 using a new assignment function and store *) + in eval expr2 ((c, new_index) :: g) s'' + + | Change (c : char) expr1 expr2 -> + let (new_value, s') = eval expr1 g s + (* lookup which index is associated with Var c *) + in let n = List.assoc c g + (* now we create a list which is just like s' except it has new_value in index n *) + in let rec replace_nth lst m = + match lst with + | [] -> failwith "list too short" + | x::xs when m = 0 -> new_value :: xs + | x::xs -> x :: replace_nth xs (m - 1) + in let s'' = replace_nth s' n + (* evaluate expr2 using original assignment function and new store *) + in eval expr2 g s'' + ##How to implicit mutation with a State monad##