week9 tweak

[lambda.git] / week9.mdwn

diff --git a/week9.mdwn b/week9.mdwn
index b38293d..2b80483 100644 (file)
--- a/week9.mdwn
+++ b/week9.mdwn
@@ -291,7 +291,34 @@ Now we're going to relativize our interpretations not only to the assignment fun
 
 >      \[[expression]]<sub>g s</sub> = (value, s')
 
 
 >      \[[expression]]<sub>g s</sub> = (value, s')
 

-With that kind of framework, we can interpret `newref`, `deref`, and `setref` as follows.
+For expressions we already know how to interpret, expect `s'` to just be `s`.
+An exception is complex expressions like `let var = expr1 in expr2`. Part of
+interpreting this will be to interpret the sub-expression `expr1`, and we have
+to allow that in doing that, the store may have already been updated. We want
+to use that possibly updated store when interpreting `expr2`. Like this:
+
+       let rec eval expression g s =
+               match expression with
+               ...
+               | Let (c, expr1, expr2) ->
+                       let (value, s') = eval expr1 g s
+                       (* s' may be different from s *)
+                       (* now we evaluate expr2 in a new environment where c has been associated
+                          with the result of evaluating expr1 in the current environment *)
+                       eval expr2 ((c, value) :: g) s'
+               ...
+
+Similarly:
+
+               ...
+               | Addition (expr1, expr2) ->
+                       let (value1, s') = eval expr1 g s
+                       in let (value2, s'') = eval expr2 g s'
+                       in (value1 + value2, s'')
+               ...
+
+Let's consider how to interpet our new syntactic forms `newref`, `deref`, and `setref`:
+

 
 1.     \[[newref starting_val]] should allocate a new reference cell in the store and insert `starting_val` into that cell. It should return some "key" or "index" or "pointer" to the newly created reference cell, so that we can do things like:
 
 
 1.     \[[newref starting_val]] should allocate a new reference cell in the store and insert `starting_val` into that cell. It should return some "key" or "index" or "pointer" to the newly created reference cell, so that we can do things like:
 


@@ -307,7 +334,7 @@ With that kind of framework, we can interpret `newref`, `deref`, and `setref` as
                let rec eval expression g s =
                        match expression with
                        ...
                let rec eval expression g s =
                        match expression with
                        ...

-                       | Newref expr ->
+                       | Newref (expr) ->

                                let (starting_val, s') = eval expr g s
                                (* note that s' may be different from s, if expr itself contained any mutation operations *)
                                (* now we want to retrieve the next free index in s' *)
                                let (starting_val, s') = eval expr g s
                                (* note that s' may be different from s, if expr itself contained any mutation operations *)
                                (* now we want to retrieve the next free index in s' *)


@@ -318,12 +345,12 @@ With that kind of framework, we can interpret `newref`, `deref`, and `setref` as
                                in (Index new_index, s'')
                        ... 
 
                                in (Index new_index, s'')
                        ... 
 

-2.     When `expr` evaluates to a `store_index`, then `deref expr` should evaluate to whatever value is at that index in the current store. (If `expr` evaluates to a value of another type, `deref expr` is undefined.) In this operation, we don't change the store at all; we're just reading from it. So we'll return the same store back unchanged.
+2.     When `expr` evaluates to a `store_index`, then `deref expr` should evaluate to whatever value is at that index in the current store. (If `expr` evaluates to a value of another type, `deref expr` is undefined.) In this operation, we don't change the store at all; we're just reading from it. So we'll return the same store back unchanged (assuming it wasn't changed during the evaluation of `expr`).

 
                let rec eval expression g s =
                        match expression with
                        ...
 
                let rec eval expression g s =
                        match expression with
                        ...

-                       | Deref expr ->
+                       | Deref (expr) ->

                                let (Index n, s') = eval expr g s
                                (* note that s' may be different from s, if expr itself contained any mutation operations *)
                                in (List.nth s' n, s')
                                let (Index n, s') = eval expr g s
                                (* note that s' may be different from s, if expr itself contained any mutation operations *)
                                in (List.nth s' n, s')


@@ -334,9 +361,9 @@ With that kind of framework, we can interpret `newref`, `deref`, and `setref` as
                let rec eval expression g s =
                        match expression with
                        ...
                let rec eval expression g s =
                        match expression with
                        ...

-                       | Setref expr1 expr2
+                       | Setref (expr1, expr2) ->

                                let (Index n, s') = eval expr1 g s
                                let (Index n, s') = eval expr1 g s

-                               (* note that s' may be different from s, if expr itself contained any mutation operations *)
+                               (* note that s' may be different from s, if expr1 itself contained any mutation operations *)

                                in let (new_value, s'') = eval expr2 g s'
                                (* 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 =
                                in let (new_value, s'') = eval expr2 g s'
                                (* 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 =


@@ -349,6 +376,9 @@ With that kind of framework, we can interpret `newref`, `deref`, and `setref` as
                        ...
 
 
                        ...
 
 

+
+
+

 ##How to implement implicit-style mutable variables##
 
 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.
 ##How to implement implicit-style mutable variables##
 
 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.


@@ -359,7 +389,7 @@ This brings up an interesting conceptual distinction. Formerly, we'd naturally t
 
 To handle implicit-style mutation, we'll need to re-implement the way we interpret expressions like `x` and `let x = expr1 in expr2`. We will also have just one new syntactic form, `change x to expr1 then expr2`.
 
 
 To handle implicit-style mutation, we'll need to re-implement the way we interpret expressions like `x` and `let x = expr1 in expr2`. We will also 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).
+Here's how to implement these. We'll suppose that our assignment function is list of pairs, as in [week7](/reader_monad_for_variable_binding).

 
        let rec eval expression g s =
                match expression with
 
        let rec eval expression g s =
                match expression with


@@ -370,7 +400,7 @@ Here's how to implement these. We'll suppose that our assignment function is lis
                        in let value = List.nth s index
                        in (value, s)
 
                        in let value = List.nth s index
                        in (value, s)
 

-               | Let (c : char) expr1 expr2 ->
+               | Let ((c : char), expr1, expr2) ->

                        let (starting_val, s') = eval expr1 g s
                        (* get next free index in s' *)
                        in let new_index = List.length s'
                        let (starting_val, s') = eval expr1 g s
                        (* get next free index in s' *)
                        in let new_index = List.length s'


@@ -379,7 +409,7 @@ Here's how to implement these. We'll suppose that our assignment function is lis
                        (* evaluate expr2 using a new assignment function and store *)
                        in eval expr2 ((c, new_index) :: g) s''
 
                        (* evaluate expr2 using a new assignment function and store *)
                        in eval expr2 ((c, new_index) :: g) s''
 

-               | Change (c : char) expr1 expr2 ->
+               | Change ((c : char), expr1, expr2) ->

                        let (new_value, s') = eval expr1 g s
                        (* lookup which index is associated with Var c *)
                        in let index = List.assoc c g
                        let (new_value, s') = eval expr1 g s
                        (* lookup which index is associated with Var c *)
                        in let index = List.assoc c g