X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=manipulating_trees_with_monads.mdwn;h=23abaa63ed33444ca1b3a6dd69fad974f4a8bb9d;hp=38f8ff3b178d903e55f81bf0e66e873c59357ca4;hb=0c24fa2c006d9a9c2224e6106042264d631e4a29;hpb=809878c89ac05c6114b6d205c3cf0788714c8755

diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 38f8ff3b..23abaa63 100644
--- a/manipulating_trees_with_monads.mdwn
+++ b/manipulating_trees_with_monads.mdwn
@@ -46,18 +46,18 @@ We'll be using trees where the nodes are integers, e.g.,
 
 Our first task will be to replace each leaf with its double:
 
-	let rec tree_map (leaf_modifier : 'a -> 'b) (t : 'a tree) : 'b tree =
+	let rec tree_map (t : 'a tree) (leaf_modifier : 'a -> 'b): 'b tree =
 	  match t with
 	    | Leaf i -> Leaf (leaf_modifier i)
-	    | Node (l, r) -> Node (tree_map leaf_modifier l,
-	                           tree_map leaf_modifier r);;
+	    | Node (l, r) -> Node (tree_map l leaf_modifier,
+	                           tree_map r leaf_modifier);;
 
-`tree_map` takes a function that transforms old leaves into new leaves,
-and maps that function over all the leaves in the tree, leaving the
-structure of the tree unchanged.  For instance:
+`tree_map` takes a tree and a function that transforms old leaves into
+new leaves, and maps that function over all the leaves in the tree,
+leaving the structure of the tree unchanged.  For instance:
 
 	let double i = i + i;;
-	tree_map double t1;;
+	tree_map t1 double;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
 	
@@ -80,7 +80,7 @@ each leaf instead by supplying the appropriate `int -> int` operation
 in place of `double`:
 
 	let square i = i * i;;
-	tree_map square t1;;
+	tree_map t1 square;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
@@ -114,7 +114,7 @@ with `f i`.
 
 [Application note: this kind of reader object could provide a model
 for Kaplan's characters.  It turns an ordinary tree into one that
-expects contextual information (here, the `λ f`) that can be
+expects contextual information (here, the `\f`) that can be
 used to compute the content of indexicals embedded arbitrarily deeply
 in the tree.]
 
@@ -143,11 +143,11 @@ function of type `int -> int` to.
 
 But we can do this:
 
-	let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> 'b reader) : 'b tree reader =
 	    match t with
 	    | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
-	    | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
-	                       reader_bind (tree_monadize f r) (fun r' ->
+	    | Node (l, r) -> reader_bind (tree_monadize l f) (fun l' ->
+	                       reader_bind (tree_monadize r f) (fun r' ->
 	                         reader_unit (Node (l', r'))));;
 
 This function says: give me a function `f` that knows how to turn
@@ -185,17 +185,17 @@ Then we can expect that supplying it to our `int tree reader` will double all th
 In more fanciful terms, the `tree_monadize` function builds plumbing that connects all of the leaves of a tree into one connected monadic network; it threads the
 `'b reader` monad through the original tree's leaves.
 
-	# tree_monadize int_readerize t1 double;;
+	# tree_monadize t1 int_readerize double;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
 
 Here, our environment is the doubling function (`fun i -> i + i`).  If
 we apply the very same `int tree reader` (namely, `tree_monadize
-int_readerize t1`) to a different `int -> int` function---say, the
+t1 int_readerize`) to a different `int -> int` function---say, the
 squaring function, `fun i -> i * i`---we get an entirely different
 result:
 
-	# tree_monadize int_readerize t1 square;;
+	# tree_monadize t1 int_readerize square;;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
@@ -213,16 +213,16 @@ Gratifyingly, we can use the `tree_monadize` function without any
 modification whatsoever, except for replacing the (parametric) type
 `'b reader` with `'b state`, and substituting in the appropriate unit and bind:
 
-	let rec tree_monadize (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> 'b state) : '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 l) (fun l' ->
-	                       state_bind (tree_monadize f r) (fun r' ->
+	    | Node (l, r) -> state_bind (tree_monadize l f) (fun l' ->
+	                       state_bind (tree_monadize r f) (fun r' ->
 	                         state_unit (Node (l', r'))));;
 
 Then we can count the number of leaves in the tree:
 
-	# tree_monadize (fun a -> fun s -> (a, s+1)) t1 0;;
+	# tree_monadize t1 (fun a -> fun s -> (a, s+1)) 0;;
 	- : int tree * int =
 	(Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11))), 5)
 	
@@ -250,7 +250,7 @@ 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;;
+        # tree_monadize t1 (fun a -> fun s -> (s+1, s+1)) 0;;
         - : int tree * int =
         (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), 5)
 
@@ -262,14 +262,14 @@ 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 =
+	let rec tree_monadize_rev (t : 'a tree) (f : 'a -> 'b state) : '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  *)
+	    | Node (l, r) -> state_bind (tree_monadize r f) (fun r' ->	   (* R first *)
+	                       state_bind (tree_monadize l f) (fun l'->    (* Then L  *)
 	                         state_unit (Node (l', r'))));;
 
-        # tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 0;;
+        # tree_monadize_rev t1 (fun a -> fun s -> (s+1, s+1)) 0;;
         - : int tree * int =
         (Node (Node (Leaf 5, Leaf 4), Node (Leaf 3, Node (Leaf 2, Leaf 1))), 5)
 
@@ -280,7 +280,7 @@ same-fringe problem.
 One more revealing example before getting down to business: replacing
 `state` everywhere in `tree_monadize` with `list` gives us
 
-	# tree_monadize (fun i -> [ [i; square i] ]) t1;;
+	# tree_monadize t1 (fun i -> [ [i; square i] ]);;
 	- : int list tree list =
 	[Node
 	  (Node (Leaf [2; 4], Leaf [3; 9]),
@@ -288,7 +288,7 @@ One more revealing example before getting down to business: replacing
 
 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.
+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
 of `int -> int list`?  Well, as usual, the List monad bind operation
@@ -303,11 +303,11 @@ of leaves?
 	let continuation_unit a = fun k -> k a;;
 	let continuation_bind u f = fun k -> u (fun a -> f a k);;
 	
-	let rec tree_monadize (f : 'a -> ('b, 'r) continuation) (t : 'a tree) : ('b tree, 'r) continuation =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> ('b, 'r) continuation) : ('b tree, 'r) continuation =
 	    match t with
 	    | Leaf a -> continuation_bind (f a) (fun b -> continuation_unit (Leaf b))
-	    | Node (l, r) -> continuation_bind (tree_monadize f l) (fun l' ->
-	                       continuation_bind (tree_monadize f r) (fun r' ->
+	    | Node (l, r) -> continuation_bind (tree_monadize l f) (fun l' ->
+	                       continuation_bind (tree_monadize r f) (fun r' ->
 	                         continuation_unit (Node (l', r'))));;
 
 We use the Continuation monad described above, and insert the
@@ -315,10 +315,21 @@ We use the Continuation monad described above, and insert the
 
 So for example, we compute:
 
-	# tree_monadize (fun a -> fun k -> a :: k a) t1 (fun t -> []);;
+	# tree_monadize t1 (fun a k -> a :: k ()) (fun _ -> []);;
 	- : 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 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?
+
+Soon 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 it's needed...
 
 The Continuation monad is amazingly flexible; we can use it to
 simulate some of the computations performed above.  To see how, first
@@ -326,7 +337,7 @@ note that an interestingly uninteresting thing happens if we use
 `continuation_unit` as our first argument to `tree_monadize`, and then
 apply the result to the identity function:
 
-	# tree_monadize continuation_unit t1 (fun t -> t);;
+	# tree_monadize t1 continuation_unit (fun t -> t);;
 	- : int tree =
 	Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11)))
 
@@ -334,51 +345,121 @@ That is, nothing happens.  But we can begin to substitute more
 interesting functions for the first argument of `tree_monadize`:
 
 	(* Simulating the tree reader: distributing a operation over the leaves *)
-	# tree_monadize (fun a -> fun k -> k (square a)) t1 (fun t -> t);;
+	# tree_monadize t1 (fun a -> fun k -> k (square a)) (fun t -> t);;
 	- : int tree =
 	Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
 
 	(* Simulating the int list tree list *)
-	# tree_monadize (fun a -> fun k -> k [a; square a]) t1 (fun t -> t);;
+	# tree_monadize t1 (fun a -> fun k -> k [a; square a]) (fun t -> t);;
 	- : int list tree =
 	Node
 	 (Node (Leaf [2; 4], Leaf [3; 9]),
 	  Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))
 
 	(* Counting leaves *)
-	# tree_monadize (fun a -> fun k -> 1 + k a) t1 (fun t -> 0);;
+	# tree_monadize t1 (fun a -> fun k -> 1 + k a) (fun t -> 0);;
 	- : int = 5
 
-We could simulate the tree state example too, but it would require
-generalizing the type of the Continuation monad to
-
-	type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
-
-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
-----------------------------------------------------
+[To be fixed: exactly which kind of monad each of these computations simulates.]
 
-We've seen two solutions to the same fringe problem so far.  
-The simplest is to map each tree to a list of its leaves, then compare
-the lists.  But if the fringes differ in an early position, we've
-wasted our time visiting the rest of the tree. 
+We could simulate the tree state example too by setting the relevant 
+type to `('a, 'state -> 'result) continuation`.
+In fact, Andre Filinsky has suggested that the continuation monad is
+able to simulate any other monad (Google for "mother of all monads").
 
-The second solution was to use tree zippers and mutable state to
-simulate coroutines.  We would unzip the first tree until we found the
-next leaf, then store the zipper structure in the mutable variable
-while we turned our attention to the other tree.  Because we stop 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.
+We would eventually want to generalize the continuation type to
 
-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.  To make this work in the most convenient
-way, we need to use the fully general type for continuations just mentioned.
+	type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
 
-tree_monadize (fun a k -> a, k a) t1 (fun t -> 0);;
+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).
 
+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 sentence1 lex (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 sentence2 lex (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
+replace the usual tree_monadizer with tree_monadizer_rev, we get
+inverse scope:
+
+<pre>
+# tree_monadize_rev sentence2 lex (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.  
 
 
 The Binary Tree monad
@@ -464,7 +545,7 @@ called a
 that is intended to represent non-deterministic computations as a tree.
 
 
-What's this have to do with tree\_mondadize?
+What's this have to do with tree\_monadize?
 --------------------------------------------
 
 So we've defined a Tree monad:
@@ -478,14 +559,26 @@ So we've defined a Tree monad:
 
 What's this have to do with the `tree_monadize` functions we defined earlier?
 
-	let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
+	let rec tree_monadize (t : 'a tree) (f : 'a -> 'b reader) : 'b tree reader =
 	    match t with
 	    | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
-	    | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
-	                       reader_bind (tree_monadize f r) (fun r' ->
+	    | Node (l, r) -> reader_bind (tree_monadize l f) (fun l' ->
+	                       reader_bind (tree_monadize r f) (fun r' ->
 	                         reader_unit (Node (l', r'))));;
 
 ... and so on for different monads?
 
-The answer is that each of those `tree_monadize` functions is adding a Tree monad *layer* to a pre-existing Reader (and so on) monad. We discuss that further here: [[Monad Transformers]].
+Well, notice that `tree\_monadizer` takes arguments whose types
+resemble that of a monadic `bind` function.  Here's a schematic bind
+function compared with `tree\_monadizer`:
+
+          bind             (u:'a Monad) (f: 'a -> 'b Monad): 'b Monad
+          tree\_monadizer  (u:'a Tree)  (f: 'a -> 'b Monad): 'b Tree Monad 
+
+Comparing these types makes it clear that `tree\_monadizer` provides a
+way to distribute an arbitrary monad M across the leaves of any tree to
+form a new tree inside an M box.
 
+The more general answer is that each of those `tree\_monadize`
+functions is adding a Tree monad *layer* to a pre-existing Reader (and
+so on) monad. We discuss that further here: [[Monad Transformers]].