index 52b8508..94a88e7 100644 (file)
@@ -22,7 +22,7 @@ the utility of replacing one monad with other.
First, we'll be needing a lot of trees for the remainder of the
course.  Here again is a type constructor for leaf-labeled, binary trees:

-    type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree)
+    type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree);;

[How would you adjust the type constructor to allow for labels on the
internal nodes?]
@@ -81,7 +81,7 @@ in place of `double`:

let square i = i * i;;
tree_map square t1;;
-       - : int tree =ppp
+       - : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))

Note that what `tree_map` does is take some unchanging contextual
tree that is ready to accept any `int -> int` function and produce the
updated tree.

-\tree (. (. (f 2) (f 3)) (. (f 5) (. (f 7) (f 11))))
-
\f      .
_____|____
|        |
@@ -248,6 +246,37 @@ increments the state. When we give that same operations to our
`tree_monadize` function, it then wraps an `int tree` in a box, one
that does the same state-incrementing for each of its leaves.

+We can use the state monad to replace leaves with a number
+corresponding to that leave's ordinal position.  When we do so, we
+reveal the order in which the monadic tree forces evaluation:
+
+        # tree_monadize (fun a -> fun s -> (s+1, s+1)) t1 0;;
+        - : int tree * int =
+        (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), 5)
+
+The key thing to notice is that instead of copying `a` into the
+monadic box, we throw away the `a` and put a copy of the state in
+
+Reversing the order requires reversing the order of the state_bind
+operations.  It's not obvious that this will type correctly, so think
+it through:
+
+       let rec tree_monadize_rev (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+           match t with
+           | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
+           | Node (l, r) -> state_bind (tree_monadize f r) (fun r' ->     (* R first *)
+                              state_bind (tree_monadize f l) (fun l'->    (* Then L  *)
+                                state_unit (Node (l', r'))));;
+
+        # tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 0;;
+        - : int tree * int =
+        (Node (Node (Leaf 5, Leaf 4), Node (Leaf 3, Node (Leaf 2, Leaf 1))), 5)
+
+We will need below to depend on controlling the order in which nodes
+are visited when we use the continuation monad to solve the
+same-fringe problem.
+
One more revealing example before getting down to business: replacing
`state` everywhere in `tree_monadize` with `list` gives us

@@ -261,7 +290,7 @@ Unlike the previous cases, instead of turning a tree into a function
from some input to a result, this transformer replaces each `int` with
a list of `int`'s. We might also have done this with a Reader monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List monad an operation like `fun -> [ i; [2*i; 3*i] ]`. Use small trees for your experiment.

-[Why is the argument to tree_monadize `int -> int list list` instead
+[Why is the argument to `tree_monadize` `int -> int list list` instead
of `int -> int list`?  Well, as usual, the List monad bind operation
will erase the outer list box, so if we want to replace the leaves
with lists, we have to nest the replacement lists inside a disposable
@@ -289,7 +318,18 @@ So for example, we compute:
# tree_monadize (fun a -> fun k -> a :: k a) t1 (fun t -> []);;
- : int list = [2; 3; 5; 7; 11]

-We have found a way of collapsing a tree into a list of its leaves. Can you trace how this is working? Think first about what the operation `fun a -> fun k -> a :: k a` does when you apply it to a plain `int`, and the continuation `fun _ -> []`. Then given what we've said about `tree_monadize`, what should we expect `tree_monadize (fun a -> fun k -> a :: k a` to do?
+We have found a way of collapsing a tree into a list of its
+leaves. Can you trace how this is working? Think first about what the
+operation `fun a -> fun k -> a :: k a` does when you apply it to a
+plain `int`, and the continuation `fun _ -> []`. Then given what we've
+a -> fun k -> a :: k a` to do?
+
+In a moment, we'll return to the same-fringe problem.  Since the
+simple but inefficient way to solve it is to map each tree to a list
+of its leaves, this transformation is on the path to a more efficient
+solution.  We'll just have to figure out how to postpone computing the
+tail of the list until its needed...

The Continuation monad is amazingly flexible; we can use it to
simulate some of the computations performed above.  To see how, first
@@ -327,6 +367,224 @@ generalizing the type of the Continuation monad to

If you want to see how to parameterize the definition of the `tree_monadize` function, so that you don't have to keep rewriting it for each new monad, see [this code](/code/tree_monadize.ml).

+Using continuations to solve the same fringe problem
+----------------------------------------------------
+
+We've seen two solutions to the same fringe problem so far.
+The problem, recall, is to take two trees and decide whether they have
+the same leaves in the same order.
+
+<pre>
+ ta            tb          tc
+ .             .           .
+_|__          _|__        _|__
+|  |          |  |        |  |
+1  .          .  3        1  .
+  _|__       _|__           _|__
+  |  |       |  |           |  |
+  2  3       1  2           3  2
+
+let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
+let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
+let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
+</pre>
+
+So `ta` and `tb` are different trees that have the same fringe, but
+`ta` and `tc` are not.
+
+The simplest solution is to map each tree to a list of its leaves,
+then compare the lists.  But because we will have computed the entire
+fringe before starting the comparison, if the fringes differ in an
+early position, we've wasted our time examining the rest of the trees.
+
+The second solution was to use tree zippers and mutable state to
+simulate coroutines (see [[coroutines and aborts]]).  In that
+solution, we pulled the zipper on the first tree until we found the
+next leaf, then stored the zipper structure in the mutable variable
+while we turned our attention to the other tree.  Because we stopped
+as soon as we find the first mismatched leaf, this solution does not
+have the flaw just mentioned of the solution that maps both trees to a
+list of leaves before beginning comparison.
+
+Since zippers are just continuations reified, we expect that the
+solution in terms of zippers can be reworked using continuations, and
+this is indeed the case.  Before we can arrive at a solution, however,
+we must define a data structure called a stream:
+
+    type 'a stream = End | Next of 'a * (unit -> 'a stream);;
+
+A stream is like a list in that it contains a series of objects (all
+of the same type, here, type `'a`).  The first object in the stream
+corresponds to the head of a list, which we pair with a stream
+representing the rest of a the list.  There is a special stream called
+`End` that represents a stream that contains no (more) elements,
+analogous to the empty list `[]`.
+
+Actually, we pair each element not with a stream, but with a thunked
+stream, that is, a function from the unit type to streams.  The idea
+is that the next element in the stream is not computed until we forced
+the thunk by applying it to the unit:
+
+<pre>
+# let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
+val make_int_stream : int -> int stream = <fun>
+# let int_stream = make_int_stream 1;;
+val int_stream : int stream = Next (1, <fun>)         (* First element: 1 *)
+# match int_stream with Next (i, rest) -> rest;;
+- : unit -> int stream = <fun>                        (* Rest: a thunk *)
+
+(* Force the thunk to compute the second element *)
+# (match int_stream with Next (i, rest) -> rest) ();;
+- : int stream = Next (2, <fun>)
+</pre>
+
+You can think of `int_stream` as a functional object that provides
+access to an infinite sequence of integers, one at a time.  It's as if
+we had written `[1;2;...]` where `...` meant "continue indefinitely".
+
+So, with streams in hand, we need only rewrite our continuation tree
+monadizer so that instead of mapping trees to lists, it maps them to
+
+       # tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);;
+       - : int list = [2; 3; 5; 7; 11]
+
+as above, we have
+
+        # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);;
+        - : int stream = Next (2, <fun>)
+
+We can see the first element in the stream, the first leaf (namely,
+2), but in order to see the next, we'll have to force a thunk.
+
+Then to complete the same-fringe function, we simply convert both
+trees into leaf-streams, then compare the streams element by element.
+The code is enitrely routine, but for the sake of completeness, here it is:
+
+<pre>
+let rec compare_streams stream1 stream2 =
+    match stream1, stream2 with
+    | End, End -> true (* Done!  Fringes match. *)
+    | Next (next1, rest1), Next (next2, rest2) when next1 = next2 -> compare_streams (rest1 ()) (rest2 ())
+    | _ -> false;;
+
+let same_fringe t1 t2 =
+  let stream1 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End) in
+  let stream2 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t2 (fun _ -> End) in
+  compare_streams stream1 stream2;;
+</pre>
+
+Notice the forcing of the thunks in the recursive call to
+`compare_streams`.  So indeed:
+
+<pre>
+# same_fringe ta tb;;
+- : bool = true
+# same_fringe ta tc;;
+- : bool = false
+</pre>
+
+Now, this implementation is a bit silly, since in order to convert the
+trees to leaf streams, our tree_monadizer function has to visit every
+node in the tree.  But if we needed to compare each tree to a large
+set of other trees, we could arrange to monadize each tree only once,
+and then run compare_streams on the monadized trees.
+
+By the way, what if you have reason to believe that the fringes of
+your trees are more likely to differ near the right edge than the left
+edge?  If we reverse evaluation order in the tree_monadizer function,
+as shown above when we replaced leaves with their ordinal position,
+then the resulting streams would produce leaves from the right to the
+left.
+
+The idea of using continuations to characterize natural language meaning
+------------------------------------------------------------------------
+
+We might a philosopher or a linguist be interested in continuations,
+especially if efficiency of computation is usually not an issue?
+Well, the application of continuations to the same-fringe problem
+shows that continuations can manage order of evaluation in a
+well-controlled manner.  In a series of papers, one of us (Barker) and
+Ken Shan have argued that a number of phenomena in natural langauge
+semantics are sensitive to the order of evaluation.  We can't
+reproduce all of the intricate arguments here, but we can give a sense
+of how the analyses use continuations to achieve an analysis of
+natural language meaning.
+
+**Quantification and default quantifier scope construal**.
+
+We saw in the copy-string example and in the same-fringe example that
+local properties of a tree (whether a character is `S` or not, which
+integer occurs at some leaf position) can control global properties of
+the computation (whether the preceeding string is copied or not,
+whether the computation halts or proceeds).  Local control of
+surrounding context is a reasonable description of in-situ
+quantification.
+
+    (1) John saw everyone yesterday.
+
+This sentence means (roughly)
+
+    &Forall; x . yesterday(saw x) john
+
+That is, the quantifier *everyone* contributes a variable in the
+direct object position, and a universal quantifier that takes scope
+over the whole sentence.  If we have a lexical meaning function like
+the following:
+
+<pre>
+let lex (s:string) k = match s with
+  | "everyone" -> Node (Leaf "forall x", k "x")
+  | "someone" -> Node (Leaf "exists y", k "y")
+  | _ -> k s;;
+
+let sentence1 = Node (Leaf "John",
+                      Node (Node (Leaf "saw",
+                                  Leaf "everyone"),
+                            Leaf "yesterday"));;
+</pre>
+
+Then we can crudely approximate quantification as follows:
+
+<pre>
+# tree_monadize lex sentence1 (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "forall x",
+  Node (Leaf "John", Node (Node (Leaf "saw", Leaf "x"), Leaf "yesterday")))
+</pre>
+
+In order to see the effects of evaluation order,
+observe what happens when we combine two quantifiers in the same
+sentence:
+
+<pre>
+# let sentence2 = Node (Leaf "everyone", Node (Leaf "saw", Leaf "someone"));;
+# tree_monadize lex sentence2 (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "forall x",
+  Node (Leaf "exists y", Node (Leaf "x", Node (Leaf "saw", Leaf "y"))))
+</pre>
+
+The universal takes scope over the existential.  If, however, we
+inverse scope:
+
+<pre>
+# tree_monadize_rev lex sentence2 (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "exists y",
+  Node (Leaf "forall x", Node (Leaf "x", Node (Leaf "saw", Leaf "y"))))
+</pre>
+
+There are many crucially important details about quantification that
+are being simplified here, and the continuation treatment here is not
+scalable for a number of reasons.  Nevertheless, it will serve to give
+an idea of how continuations can provide insight into the behavior of
+quantifiers.
+

---------------------
@@ -352,8 +610,6 @@ induction on the structure of the first argument that the tree
resulting from `bind u f` is a tree with the same strucure as `u`,
except that each leaf `a` has been replaced with `f a`:

-\tree (. (f a1) (. (. (. (f a2) (f a3)) (f a4)) (f a5)))
-
.                         .
__|__                     __|__
|   |                     |   |
@@ -383,9 +639,6 @@ As for the associative law,
we'll give an example that will show how an inductive proof would
proceed.  Let `f a = Node (Leaf a, Leaf a)`.  Then

-\tree (. (. (. (. (a1) (a2)))))
-\tree (. (. (. (. (a1) (a1)) (. (a1) (a1)))))
-
.
____|____
.               .            |       |
@@ -439,113 +692,5 @@ What's this have to do with the `tree_monadize` functions we defined earlier?

... and so on for different monads?

-
-
-               env -> 'a;;
-       let unit (a : 'a) : 'a reader =
-               fun e -> a;;
-               fun e -> (fun v -> f v e) (u e);;
-
-We've just beta-expanded the familiar `f (u e) e` into `(fun v -> f v e) (u e)`, in order to factor out the parts where any Reader monad is being supplied as an argument to another function. Then if we want instead to add a Reader layer to some arbitrary other monad M, with its own M.unit and M.bind, here's how we do it:
-
-
-       (* We're not giving valid OCaml code, but rather something
-        * that's conceptually easier to digest.
-        * How you really need to write this in OCaml is more circuitous...
-        * see http://lambda.jimpryor.net/code/tree_monadize.ml for some details. *)
-
-       type ('a, M) readerT =
-               env -> 'a M;;
-       (* this is just an 'a M reader; but don't rely on that pattern to generalize *)
-
-       let unit (a : 'a) : ('a, M) readerT =
-               fun e -> M.unit a;;
-
-       let bind (u : ('a, M) readerT) (f : 'a -> ('b, M) readerT) : ('b, M) readerT =
-               fun e -> M.bind (u e) (fun v -> f v e);;
-
-Notice the key differences: where before we just returned `a`, now we instead return `M.unit a`. Where before we just supplied value `u e` of type `'a reader` as an argument to a function, now we instead `M.bind` the `'a reader` to that function. Notice also the differences in the types.
-
-
-       type 'a identity = 'a;;
-       let unit (a : 'a) : 'a = a;;
-       let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
-
-
-The relations between the State monad and the StateT monadic transformer are parallel:
-
-
-       type 'a state =
-               store -> ('a * store);;
-
-       let unit (a : 'a) : 'a state =
-               fun s -> (a, s);;
-
-       let bind (u : 'a state) (f : 'a -> 'b state) : 'b state =
-               fun s -> (fun (a, s') -> f a s') (u s);;
-
-We've used `(fun (a, s') -> f a s') (u s)` instead of the more familiar `let (a, s') = u s in f a s'` in order to factor out the part where a value of type `'a state` is supplied as an argument to a function. Now StateT will be:
-
-
-       type ('a, M) stateT =
-               store -> ('a * store) M;;
-       (* notice this is not an 'a M state *)
-
-       let unit (a : 'a) : ('a, M) stateT =
-               fun s -> M.unit (a, s);;
-
-       let bind (u : ('a, M) stateT) (f : 'a -> ('b, M) stateT) : ('b, M) stateT =
-               fun s -> M.bind (u s) (fun (a, s') -> f a s');;
-
-Do you see the pattern? Where ordinarily we'd return an `'a` value, now we instead return an `'a M` value. Where ordinarily we'd supply a `'a state` value as an argument to a function, now we instead `M.bind` it to that function.
-
-Okay, now let's do the same thing for our Tree monad.
-
-
-       type 'a tree =
-               Leaf of 'a | Node of ('a tree) * ('a tree);;
-
-       let unit (a: 'a) : 'a tree =
-               Leaf a;;
-
-       let rec bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree =
-           match u with
-           | Leaf a -> f a;;
-           | Node (l, r) -> (fun l' r' -> Node (l', r')) (bind l f) (bind r f);;
-
-       (* NOTE THIS IS NOT YET WORKING --- STILL REFINING *)
-
-       type ('a, M) treeT =
-               'a tree M;;
-
-       let unit (a: 'a) : ('a, M) tree =
-               M.unit (Leaf a);;
-
-       let rec bind (u : ('a, M) tree) (f : 'a -> ('b, M) tree) : ('b, M) tree =
-           match u with
-           | Leaf a -> M.bind (f a) (fun b -> M.unit (Leaf b))
-           | Node (l, r) -> M.bind (bind l f) (fun l' ->
-                                                       M.bind (bind r f) (fun r' ->
-                                                               M.unit (Node (l', r'));;
-