- 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
+ 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