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

-# let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));; -val make_int_stream : int -> int stream =- -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 -streams. Instead of - - # tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);; - - : int list = [2; 3; 5; 7; 11] +Andre Filinsky has proposed that the continuation monad is +able to simulate any other monad (Google for "mother of all monads"). -as above, we have - - # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);; - - : int stream = Next (2,-# let int_stream = make_int_stream 1;; -val int_stream : int stream = Next (1, ) (* First element: 1 *) -# match int_stream with Next (i, rest) -> rest;; -- : unit -> int stream = (* Rest: a thunk *) - -(* Force the thunk to compute the second element *) -# (match int_stream with Next (i, rest) -> rest) ();; -- : int stream = Next (2, ) -

-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;; -- -Notice the forcing of the thunks in the recursive call to -`compare_streams`. So indeed: - -

-# same_fringe ta tb;; -- : bool = true -# same_fringe ta tc;; -- : bool = false -- -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. +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 ------------------------------------------------------------------------ @@ -513,8 +391,8 @@ 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 +We saw in the copy-string example ("abSd") and in the same-fringe example that +local properties of a structure (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 @@ -525,72 +403,64 @@ quantification. This sentence means (roughly) - ∀ x . yesterday(saw x) john + 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"));; -+ let lex (s:string) k = match s with + | "everyone" -> Node (Leaf "forall x", k "x") + | "someone" -> Node (Leaf "exists y", k "y") + | _ -> k s;; 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"))) -+ # let sentence1 = Node (Leaf "John", + Node (Node (Leaf "saw", + Leaf "everyone"), + Leaf "yesterday"));; + + # 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")))) -+ # 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 +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")))) -+ # 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 +are being simplified here, and the continuation treatment used 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. +quantifiers. -The Binary Tree monad ---------------------- +The Tree monad +============== -Of course, by now you may have realized that we have discovered a new -monad, the Binary Tree monad. Just as mere lists are in fact a monad, +Of course, by now you may have realized that we are working with a new +monad, the binary, leaf-labeled Tree monad. Just as mere lists are in fact a monad, so are trees. Here is the type constructor, unit, and bind: type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);; @@ -608,20 +478,20 @@ To check the other two laws, we need to make the following observation: it is easy to prove based on `tree_bind` by a simple 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`: +except that each leaf `a` has been replaced with the tree returned by `f a`: . . __|__ __|__ - | | | | + | | /\ | a1 . f a1 . _|__ __|__ - | | | | + | | | /\ . a5 . f a5 bind _|__ f = __|__ - | | | | + | | | /\ . a4 . f a4 __|__ __|___ - | | | | + | | /\ /\ a2 a3 f a2 f a3 Given this equivalence, the right identity law @@ -659,7 +529,7 @@ Now when we bind this tree to `g`, we get At this point, it should be easy to convince yourself that using the recipe on the right hand side of the associative law will -built the exact same final tree. +build the exact same final tree. So binary trees are a monad. @@ -669,28 +539,8 @@ 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: - - type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);; - let tree_unit (a: 'a) : 'a tree = Leaf a;; - let rec tree_bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree = - match u with - | Leaf a -> f a - | Node (l, r) -> Node (tree_bind l f, tree_bind r f);; - -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 = - 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' -> - 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]]. +Our different implementations of `tree_monadize` above were different *layerings* of the Tree monad with other monads (Reader, State, List, and Continuation). We'll explore that further here: [[Monad Transformers]].