author Jim Pryor Mon, 6 Dec 2010 23:58:04 +0000 (18:58 -0500) committer Jim Pryor Mon, 6 Dec 2010 23:58:04 +0000 (18:58 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
 manipulating_trees_with_monads.mdwn patch | blob | history using_continuations_to_solve_same_fringe.mdwn [new file with mode: 0644] patch | blob

index 47fa6f0..3247ce6 100644 (file)
@@ -325,7 +325,7 @@ plain `int`, and the continuation `fun _ -> []`. Then given what we've
a -> fun k -> a :: k a` to do?

a -> fun k -> a :: k a` to do?

-In a moment, we'll return to the same-fringe problem.  Since the
+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
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
@@ -373,136 +373,6 @@ We would eventually want to generalize the continuation type 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).

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

The idea of using continuations to characterize natural language meaning
------------------------------------------------------------------------

diff --git a/using_continuations_to_solve_same_fringe.mdwn b/using_continuations_to_solve_same_fringe.mdwn
new file mode 100644 (file)
--- /dev/null
@@ -0,0 +1,130 @@
+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.
+