(* evaluate expr2 using original assignment function and new store *)
in eval expr2 g s''
-Note: Chris uses this kind of machinery on the third page of the Nov 22 handout. Except he doesn't implement `Change`, and he adds an implementation of `Alias` (see below). Some minor differences: on his handout (and following Groenendijk, Stockhof and Veltman), he uses `r` and `g` where we use `g` and `s` respectively. Also, he implements his `r` with a function from `char` to `int`, instead of a `(char * int) list`, as we do here. It should be obvious how to translate between these. Finally, and this is somewhat more substantial: he implements `Let(c, expr1, expr2)` not by allocating a new peg for `c` as we do above, but rather by changing the value stored at the peg that his `r` already associates with `c`. Without aliases, it doesn't matter which way you go. With aliases, his method is the way to go, because then all other variables aliased to the same peg will automatically inherit the new value. However, his solution requires that variables always already have an associated peg. So that when we call `Let(c, expr1, expr2)` for the first time with `c`, there's a peg whose value is to be updated. That's easier to ensure when you implement the assignment as a function than as a `(char * int) list`.
+Note: Chris uses this kind of machinery on the third page of the Nov 22 handout. Except he implements `Let` the way we here implement `Change`. And he adds an implementation of `Alias` (see below). Some minor differences: on his handout (and following Groenendijk, Stockhof and Veltman), he uses `r` and `g` where we use `g` and `s` respectively. Also, he implements his `r` with a function from `char` to `int`, instead of a `(char * int) list`, as we do here. It should be obvious how to translate between these. His implementation requires that variables always already have an associated peg. So that when we call `Let(c, expr1, expr2)` for the first time with `c`, there's a peg whose value is to be updated. That's easier to ensure when you implement the assignment as a function than as a `(char * int) list`.
##How to implement mutation with a State monad##
Terminological note: in OCaml, `=` and `<>` express the qualitative (in)discernibility relations, also expressed in Scheme with `equal?`. In OCaml, `==` and `!=` express the numerical (non)identity relations, also expressed in Scheme with `eq?`. `=` also has other syntactic roles in OCaml, such as in the form `let x = value in ...`. In other languages, like C and Python, `=` is commonly used just for assignment (of either of the sorts we've now seen: `let x = value in ...` or `change x to value in ...`). The symbols `==` and `!=` are commonly used to express qualitative (in)discernibility in these languages. Python expresses numerical (non)identity with `is` and `is not`. What an unattractive mess. Don't get me started on Haskell (qualitative discernibility is `/=`) and Lua (physical (non)identity is `==` and `~=`).
- Note that neither of the equality predicates here being considered are the same as the "hyperequals" predicate mentioned above. For example, in the following (fictional) language:
+ The `=` and `==` predicates in OCaml do not between them cover all the natural cases you may want to test for. For instance, if `ycell` is a reference cell, then `ref !ycell` will always be a numerically distinct reference cell containing the same value. We get this pattern of comparisons:
+
+ ycell == ycell
+ ycell != ref !ycell
+
+ ycell = ycell
+ ycell = ref !ycell
+
+ But now what about?
+
+ (0, 1, ycell) ? (0, 1, ycell)
+ (0, 1. ycell) ? (0, 1. ref !ycell)
+
+ You might expect that there'd be an equality predicate that counts the first pair as equal, but not the second. But there isn't. OCaml's physical identity predicate `==` counts each pair as non-equal, even though the first of them involves the same structure containing only physically identical components. OCaml's structural equality preficate `=` counts both pairs as equal; it's insensitive to the lack of physical identity between `ycell` and `ref !ycell`.
+
+ Additionally, note that none of the equality predicates so far considered is the same as the "hyperequals" predicate mentioned above. For example, in the following (fictional) language:
let ycell = ref 1
in let xcell = ref 1