- 0. Purely functional languages
- 1. Passing by reference
- need primitive hyper-evaluative predicates for it to make a difference
- 2. mutable variables
- 3. mutable values
- - numerically distinct but indiscernible values
- - two equality predicates
- - examples: closures with currently-indiscernible but numerically distinct
- environments, mutable lists
- 4. "references" as first-class values
- - x not the same as !x, explicit deref operation
- - can not only be assigned and passed as arguments, also returned (and manipulated?)
- - can be compared for qualitative equality
- 5. structured references
+* 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 `~=`).
+
+ 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:
+
+ 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