X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week9.mdwn;h=c01890e44525d0495bbdfa9f8a52aa9ad8bf2044;hp=79ebf40b3fc77dd4f719e868e292c8cf3a75ee6b;hb=3ce7cd6b143bb54387ec6b16a4a4aa5774a9baf1;hpb=a9f00c3696342d92815872a48dbb352bea71698a diff --git a/week9.mdwn b/week9.mdwn index 79ebf40b..c01890e4 100644 --- a/week9.mdwn +++ b/week9.mdwn @@ -500,62 +500,73 @@ To get the whole process started, the complex computation so defined will need t -- FIXME -- - [H] ; *** aliasing *** - let y be 2 in - let x be y in - let w alias y in - (y, x, w) ==> (2, 2, 2) - - [I] ; mutation plus aliasing - let y be 2 in - let x be y in - let w alias y in - change y to 3 then - (y, x, w) ==> (3, 2, 3) - - [J] let f be (lambda (y) -> BODY) in ; a - ... f (EXPRESSION) ... - - (lambda (y) -> BODY) EXPRESSION - - let y be EXPRESSION in ; b - ... BODY ... - - [K] ; *** passing "by reference" *** - let f be (lambda (alias w) -> ; ? - BODY - ) in - ... f (y) ... - - let w alias y in ; d - ... BODY ... - - [L] let f be (lambda (alias w) -> - change w to 2 then - w + 2 - ) in - let y be 1 in - let z be f (y) in - ; y is now 2, not 1 - (z, y) ==> (4, 2) - - [M] ; hyper-evaluativity - let h be 1 in - let p be 1 in - let f be (lambda (alias x, alias y) -> - ; contrast here: "let z be x + y + 1" - change y to y + 1 then - let z be x + y in - change y to y - 1 then - z - ) in - (f (h, p), f (h, h)) - ==> (3, 4) - - Notice: h, p have same value (1), but f (h, p) and f (h, h) differ - - -Fine and Pryor on "coordinated contents" (see, e.g., [Hyper-Evaluativity](http://www.jimpryor.net/research/papers/Hyper-Evaluativity.txt)) + [H] ; *** aliasing *** + let y be 2 in + let x be y in + let w alias y in + (y, x, w) + ; evaluates to (2, 2, 2) + + [I] ; mutation plus aliasing + let y be 2 in + let x be y in + let w alias y in + change y to 3 then + (y, x, w) + ; evaluates to (3, 2, 3) + + [J] ; as we already know, these are all equivalent: + + let f be (lambda (y) -> BODY) in ; #1 + ... f (EXPRESSION) ... + + (lambda (y) -> BODY) EXPRESSION ; #2 + + let y be EXPRESSION in ; #3 + ... BODY ... + + [K] ; *** passing by reference *** + ; now think: "[J#1] is to [J#3] as [K#1] is to [K#2]" + + ? ; #1 + + let w alias y in ; #2 + ... BODY ... + + ; We introduce a special syntactic form to supply + ; the missing ? + + let f be (lambda (alias w) -> ; #1 + BODY + ) in + ... f (y) ... + + [L] let f be (lambda (alias w) -> + change w to 2 then + w + 2 + ) in + let y be 1 in + let z be f (y) in + ; y is now 2, not 1 + (z, y) + ; evaluates to (4, 2) + + [M] ; hyper-evaluativity + let h be 1 in + let p be 1 in + let f be (lambda (alias x, alias y) -> + ; contrast here: "let z be x + y + 1" + change y to y + 1 then + let z be x + y in + change y to y - 1 then + z + ) in + (f (h, p), f (h, h)) + ; evaluates to (3, 4) + +Notice: in [M], `h` and `p` have same value (1), but `f (h, p)` and `f (h, h)` differ. + +See Pryor's "[Hyper-Evaluativity](http://www.jimpryor.net/research/papers/Hyper-Evaluativity.txt)". ##Four grades of mutation involvement## @@ -602,7 +613,7 @@ Programming languages tend to provide a bunch of mutation-related capabilities a 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 identical, but numerically distinct. However, arguably they're not *fully* qualitatively identical. 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. + 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 non-identity is `/=`) and Lua (physical (non)identity is `==` and `~=`). @@ -625,7 +636,7 @@ Programming languages tend to provide a bunch of mutation-related capabilities a xcell == wcell xcell == zcell - If we express qualitative identity using `=`, as OCaml does, then all of the salient comparisons would be true: + If we express qualitative indiscernibility using `=`, as OCaml does, then all of the salient comparisons would be true: ycell = wcell ycell = zcell @@ -664,13 +675,14 @@ Programming languages tend to provide a bunch of mutation-related capabilities a -* A fourth grade of mutation involvement... +* A fourth grade of mutation involvement: (--- FIXME ---) structured references (a) if `a` and `b` are mutable variables that uncoordinatedly refer to numerically the same value then mutating `b` won't affect `a` or its value (b) if however their value has a mutable field `f`, then mutating `b.f` does affect their shared value; will see a difference in what `a.f` now evaluates to + (c) examples: Scheme mutable pairs, OCaml mutable arrays or records