week9

[lambda.git] / week9.mdwn

[[!toc]]

The seminar is now going to begin talking about more **imperatival** or **effect**-like elements in programming languages. The only effect-like element we've encountered so far is the possibility of divergence, in languages that permit fixed point combinators and so have the full power of recursion. What it means for something to be effect-like, and why this counts as an example of such, will emerge.

Other effect-like elements in a language include: printing (recall the [[damn]] example at the start of term), continuations (also foreshadowed in the [[damn]] example) and exceptions, and **mutation**. This last notion is our first topic.


## Mutation##

What is mutation? It's helpful to build up to this in a series of fragments. For pedagogical purposes, we'll be using a made-up language that's syntactically similar to, but not quite the same as, OCaml.

This should seem entirely familiar:

        [A] let x be 1 + 2 in
                  let y be 10 in
                        (x + y, x + 20)       ==> (13, 23)

Recall from earlier discussions that the following two forms are equivalent:

        [B] let x be EXPRESSION in
                  BODY

                (lambda (x) -> BODY) (EXPRESSION)

In fragment [A], we bound the variables `x` and `y` to `int`s. We can also bind variables to function values, as here:

        [C] let f be (lambda (x, y) -> x + y + 1) in
                  (f (10, 2), f (20, 2))
                                                                  ==> (13, 23)

If the expression that evaluates to a function value has a free variable in it, like `y` in the next fragment, it's interpreted as bound to whatever value `y` has in the surrounding lexical context:

        [D] let y be 3 in
                  let f be (lambda (x) -> x + y) in
                        (f (10), f (20))
                                                                  ==> (13, 23)

Other choices about how to interpret free variables are also possible (you can read about "lexical scope" versus "dynamic scope"), but what we do here is the norm in functional programming languages, and seems to be easiest for programmers to reason about.

In our next fragement, we re-use a variable that had been bound to another value in a wider context:

        [E] let x be 4 in
                  let x be 3 in
                        (x + 10, x + 20)      ==> (13, 23)

As you can see, the narrowest assignment is what's effective. This is just like in predicate logic: consider `(exists x. Fx and (exists x. Gx))`. The computer-science terminology to describe this is that the narrower assignment of `x` to the value 3 **shadows** the wider assignment to 4.

I call attention to this because you might casually describe it as "changing the value that x is assigned to." What we'll go on to see is a more exotic phenomenon that merits that description better.

Sometimes the shadowing is merely temporary, as here:

        [F] let y be 2 in
                  let f be (lambda (x) ->
                        let y be 3 in
                          ; here the most local assignment to y applies
                          x + y
                  ) in
                        ; here the assignment of 3 to y has expired
                        (f (10), y, f (20))   ==> (13, 2, 23)

OK, now we're ready for our main event, **mutable variables.** We'll introduce new syntax to express an operation where we're not shadowing a wider assignment, but *changing* the original assignemnt:

        [G] let y be 2 in
                  let f be (lambda (x) ->
                        change y to 3 then
                          x + y
                  ) in
                        ; here the change in what value y was assigned *sticks*
                        ; we updated y's value, instead of introducing a new y
                        (f (10), y, f (19))   ==> (13, 3, 23)

In languages that have native syntax for this, there are two styles in which it can be expressed. The *implicit style* is exemplified in fragment [G] above, and also in languages like C:

        {
                int x = 1;    // this is like "let x be 1 in ..."
                x = 2;        // this is like "change x to 2 then ..."
                return x + 1; // this is like "x + 1"
        }

A different possibility is the *explicit style* for handling mutation. Here we explicitly create and refer to new "reference cells" to hold our values. When we change a variable's value, the variable stays associated with the same reference cell, but that reference cell's contents get modified. The same thing happens in the semantic machinery underlying implicit-style mutable variables, but there it's implicit. The reference cells aren't themselves explicitly referred to in the object language. In explicit-style mutation, they are. OCaml has explicit-style mutation. It looks like this:

          let xcell = ref 1         (* this creates a new reference cell *)
                        in let () = xcell := 2  (* this changes the contents of that cell to 2; the return value of doing so is () *)
                                                                    (* other return values could also be reasonable: such as the old value of xcell, the new value, an arbitrary int, and so on *)
                        in !xcell + 1;;                 (* the !xcell operation "dereferences" the cell---it retrieves the value it contains *)

When we're dealing with mutable variables (or any other kind of effect), order now matters. For example, it would make a big difference whether I evaluated "let z = !xcell" before or after evaluating "xcell := !xcell + 1". Before this point, order never mattered except with respect to sometimes avoiding divergence.

OCaml does not however guarantee what order expressions will be evaluated in arbitrary contexts. For example, in the following fragment, you cannot rely on `expression_a` being evaluated before `expression_b` before `expression_c`:

        let triple = (expression_a, expression_b, expression_c)

OCaml does however guarantee that different let-expressions are evaluated in the order they lexically appear. So in the following fragment, `expression_a` *will* be evaluated before `expression_b` and that before `expression_c`:

        let a = expression_a
                in let b = expression_b
                        in expression_c

Scheme does the same---if you use Scheme's `let*`, but not if you use its `let`. I agree this is annoying.

If `expression_a` and `expression_b` evaluate to (), for instance if they're something like `xcell := !xcell + 1`, that can also be expressed in OCaml as:

        let () = expression_a
                in let () = expression_b
                        in expression_c

And OCaml has a syntactic shorthand for this form, namely to use semi-colons:

        expression_a; expression_b; expression_c

This is not the same role that semi-colons play in list expressions, like `[1; 2; 3]`. For parsing purposes, these semi-colon'ed complexes sometimes need to be enclosed in parentheses or a `begin ... end` construction:

        (expression_a; expression_b; expression_c)

        begin expression_a; expression_b; expression_c end

Scheme has a construction similar to the latter:

        (begin (expression_a) (expression_b) (expression_c))

Though often in Scheme, the `(begin ...)` is implicit and doesn't need to be explicitly inserted, as here:

        (lambda (x) (expression_a) (expression_b) (expression_c))


##Referential opacity##

In addition to order-sensitivity, when you're dealing with mutable variables you also give up a property that computer scientists call "referential transparency." It's not obvious whether they mean exactly the same by that as philosophers and linguists do, or only something approximately the same. What they do mean is a kind of substitution principle, illustrated here:

        let x = 1
                in (x, x)

should evaluate the same as:

        let x = 1
                in (x, 1)

or:

        (1, 1)

Notice, however, that these don't evaluate the same:

        let xcell = ref 1
                in xcell := 2; !xcell
        (* evaluates to 2 *)

        (ref 1) := 2; !(ref 1)
        (* evaluates to 1 *)


NOTES NEED TO BE CLEANED UP FROM THIS POINT ONWARD...

##Aliasing##

    [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


Different grades of mutation involvement...

Five grades of mutation involvement

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



loops instead of recursion



## Side-effects and mutation ##

1.      What difference imperativity makes
2.      Side-effects in a purely functional setting, via monads
3.      [Phil/ling application]Semantics for DPL, using state monad
        Groenendijk, Stokhof, and Veltman, "Coreference and modality"
        in Shalom Lappin, ed. Handbook of Contemporary Semantic Theory (Blackwell, 1996)
4.      Passing by reference
5.      [Phil/ling application] Fine and Pryor on "coordinated contents" (see, e.g., [Hyper-Evaluativity](http://www.jimpryor.net/research/papers/Hyper-Evaluativity.txt))