+ The simplest such predicate we might call "hyperequals": `y hyperequals w` should evaluate to true when and only when the arguments `y` and `w` are aliased.
+
+
+* Another increment would be to add implicit-style mutable variables, as we explained above. You could do this with or without also adding passing-by-reference.
+
+ The semantic machinery for implicit-style mutable variables will have something playing the role of a reference cell. However these won't be **first-class values** in the language. For something to be a first-class value, it has to be possible to assign that value to variables, to pass it as an argument to functions, and to return it as the result of a function call. Now for some of these criteria it's debatable that they are already here satisfied. For example, in some sense the introduction of a new implicitly mutable variable (`let x = 1 in ...`) will associate a reference cell with `x`. That won't be what `x` evaluates to, but it will be what the assignment function *binds* `x` to, behind the scenes. Similarly, if we bring in passing by reference, then again in some sense we are passing reference cells as arguments to functions. Not explicitly---in a context like:
+
+ let f = (lambda (alias w) -> ...)
+ in let x = 1
+ in f (x)
+
+ the expression `w` won't evaluate to a reference cell anywhere inside the `...`. But it will be associated with a reference cell, in the same way that `x` is (and indeed, with the same reference cell).
+
+ However, in language with implicit-style mutation, even when combined with passing by reference, what you're clearly not able to do is to return a reference cell as the result of a function call, or indeed of any expression. This is connected to---perhaps it's the same point as---the fact that `x` and `w` don't evalute to reference cells, but rather to the values that the reference cell they're implicitly associated with contains, at that stage in the computation.
+
+* A third grade of mutation involvement is to have explicit-style mutation. Here we might say we have not just mutable variables but also first-class values whose contents can be altered. That is, we have not just mutable variables but **mutable values**.
+
+ This introduces some interesting new conceptual possibilities. For example, what should be the result of the following fragment?
+
+ let ycell = ref 1
+ in let xcell = ref 1
+ in ycell = xcell
+
+ Are the two reference cell values equal or aren't they? Well, at this stage in the computation, they're qualitatively indiscernible. They're both `int ref`s containing the same `int`. And that is in fact the relation that `=` expresses in OCaml. In Scheme the analogous relation is spelled `equal?` Computer scientists sometimes call this relation "structural equality."
+
+ On the other hand, these are numerically *two* reference cells. If we mutate one of them, the other one doesn't change. For example:
+
+ let ycell = ref 1
+ in let xcell = ref 1
+ in ycell := 2
+ in !xcell;;
+ (* evaluates to 1, not to 2 *)
+
+ So we have here the basis for introducing a new kind of equality predicate into our language, which tests not for qualitative indiscernibility but for numerical equality. In OCaml this relation is expressed by the double equals `==`. In Scheme it's spelled `eq?` Computer scientists sometimes call this relation "physical equality". Using this equality predicate, our comparison of `ycell` and `xcell` will be `false`, even if they then happen to contain the same `int`.
+
+ Isn't this interesting? Intuitively, elsewhere in math, you might think that qualitative indicernibility always suffices for numerical identity. Well, perhaps this needs discussion. In some sense the imaginary numbers ι and -ι are qualitatively indiscernible, but numerically distinct. However, arguably they're not *fully* qualitatively indiscernible. They don't both bear all the same relations to ι for instance. But then, if we include numerical identity as a relation, then `ycell` and `xcell` don't both bear all the same relations to `ycell`, either. Yet there is still a useful sense in which they can be understood to be qualitatively equal---at least, at a given stage in a computation.
+
+ 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 `~=`).
+
+ Because of the particular way the numerical identity predicates are implemented in all of these languages, it doesn't quite match our conceptual expectations. For instance, 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 in OCaml:
+
+ ycell == ycell
+ ycell != ref !ycell (* these aren't numerically identical *)
+
+ ycell = ycell
+ ycell = ref !ycell (* they are qualitatively indiscernible *)
+
+ But now what about?
+
+ (0, 1, ycell) ? (0, 1, ycell)
+ (0, 1. ycell) ? (0, 1. ref !ycell)
+
+ You might expect the first pair to be numerically identical too---after all, they involve the same structure (an immutable triple) each of whose components is numerically identical. But OCaml's "physical identity" predicate `==` does not detect that identity. It counts both of these comparisons as false. OCaml's `=` predicate does count the first pair as equal, but only because it's insensitive to numerical identity; it also counts the second pair as equal. This shows up in all the other languages I know, as well. In Python, `y = []; (0, 1, y) is (0, 1, y)` evaluates to false. In Racket, `(define y (box 1)) (eq? (cons 0 y) (cons 0 y))` also evaluates to false (and in Racket, unlike traditional Schemes, `cons` is creating immutable pairs). They chose an implementation for their numerical identity predicates that is especially efficient and does the right thing in the common cases, but doesn't quite match our mathematical expectations.
+
+ 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
+ in let wcell alias ycell
+ in let zcell = ycell
+ in ...
+
+ at the end, `hyperequals ycell wcell` (and the converse) would be true, but no other non-reflexive hyperequality would be true. `hyperequals ycell zcell` for instance would be false. If we express numerical identity using `==`, as OCaml does, then both of these (and their converses) would be true:
+
+ ycell == wcell
+ ycell == zcell
+
+ but these would be false:
+
+ xcell == ycell
+ xcell == wcell
+ xcell == zcell
+
+ If we express qualitative indiscernibility using `=`, as OCaml does, then all of the salient comparisons would be true:
+
+ ycell = wcell
+ ycell = zcell
+ xcell = ycell
+ ...
+
+ Another interesting example of "mutable values" that illustrate the coming apart of qualitative indiscernibility and numerical identity are the `getter`/`setter` pairs we discussed earlier. Recall:
+
+ let factory (starting_val : int) =
+ let free_var = ref starting_value
+ in let getter () =
+ !free_var
+ in let setter (new_value : int) =
+ free_var := new_value
+ in (getter, setter)
+ in let (getter, setter) = factory 1
+ in let (getter', setter') = factory 1
+ in ...
+
+ After this, `getter` and `getter'` would (at least, temporarily) be qualitatively indiscernible. They'd return the same value whenever called with the same argument (`()`). So too would `adder` and `adder'` in the following example:
+
+ let factory (starting_val : int) =
+ let free_var = ref starting_value
+ in let adder x =
+ x + !free_var
+ in let setter (new_value : int) =
+ free_var := new_value
+ in (adder, setter)
+ in let (adder, setter) = factory 1
+ in let (adder', setter') = factory 1
+ in ...
+
+ Of course, in most languages you wouldn't be able to evaluate a comparison like `getter = getter'`, because in general the question whether two functions always return the same values for the same arguments is not decidable. So typically languages don't even try to answer that question. However, it would still be true that `getter` and `getter'` (and `adder` and `adder'`) were extensionally equivalent.
+
+ However, they're not numerically identical, because by calling `setter 2` (but not calling `setter' 2`) we can mutate the function value `getter` (and `adder`) so that it's *no longer* qualitatively indiscernible from `getter'` (or `adder'`).
+
+
+
+* A fourth grade of mutation involvement: (--- FIXME ---)
+
+ structured references