X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=manipulating_trees_with_monads.mdwn;h=3247ce6232d7e3ee8d84cbb438520c723806bfac;hp=e739c997bada0d8b2c9f23fc07e4821e22574f63;hb=2dba81fca7c1d2dcfb4fdff6f55c74c8cf795470;hpb=c6912ab54f5f042930b15e63b984480c1b98e6ca
diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index e739c997..3247ce62 100644
--- a/manipulating_trees_with_monads.mdwn
+++ b/manipulating_trees_with_monads.mdwn
@@ -318,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
+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
@@ -349,36 +360,106 @@ interesting functions for the first argument of `tree_monadize`:
# tree_monadize (fun a -> fun k -> 1 + k a) t1 (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
+[To be fixed: exactly which kind of monad each of these computations simulates.]
- 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
-----------------------------------------------------
+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").
-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 would eventually want to generalize the continuation type to
-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.
-
-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:
+
+
+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"));;
+
+
+Then we can crudely approximate quantification as follows:
+
+
+# tree_monadize lex sentence1 (fun x -> x);;
+- : string tree =
+Node
+ (Leaf "forall x",
+ Node (Leaf "John", Node (Node (Leaf "saw", Leaf "x"), Leaf "yesterday")))
+
+
+In order to see the effects of evaluation order,
+observe what happens when we combine two quantifiers in the same
+sentence:
+
+
+# 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"))))
+
+
+The universal takes scope over the existential. If, however, we
+replace the usual tree_monadizer with tree_monadizer_rev, we get
+inverse scope:
+
+
+# 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"))))
+
+
+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: