- 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
+ ycell = ycell
+ ycell = ref !ycell (* true, 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; you just wouldn't be able to establish so.
+
+ 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