author Chris Barker Tue, 7 Dec 2010 17:42:25 +0000 (12:42 -0500) committer Chris Barker Tue, 7 Dec 2010 17:42:25 +0000 (12:42 -0500)
 assignment9.mdwn [new file with mode: 0644] patch | blob

diff --git a/assignment9.mdwn b/assignment9.mdwn
new file mode 100644 (file)
index 0000000..2277a92
--- /dev/null
@@ -0,0 +1,131 @@
+Using continuations to solve the same-fringe problem
+----------------------------------------------------
+
+The 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.  Your assignment is to show how.
+
+TO-DO LIST for solving the problem
+----------------------------------
+
+1.  Review the simple but inefficient solution (easy).
+2.  Understand the zipper/mutable state solution in [[coroutines and aborts]] (harder).
+
+3.  Two obvious approaches:
+
+a.  Review the list-zipper/list-continuation example given in
+    class in [[from list zippers to continuations]]; then
+    figure out how to re-functionalize the zippers used in the zipper
+    solution.
+
+b.  Review the tree_monadizer application of continuations that maps a
+tree to a list of leaves in [[manipulating trees with monads]].  Spend
+some time trying to understand exactly what it does.  Suggestion:
+compute the transformation for a tree with two leaves, performing all
+beta reduction by hand using the definitions for bind_continuation and
+so on.  If you take this route, study the description of streams (a
+particular kind of data structure) below.  The goal will be to arrange
+for the continuation-flavored tree_monadizer to transform a tree into
+a stream instead of into a list.  Once you've done that, completing
+the same-fringe problem will be easy.
+
+-------------------------------------
+
+Whichever method you choose, here are some goals to consider.
+
+1.  Make sure that your solution gives the right results on the trees
+given above.
+
+2.  Make sure your function works on trees that contain only a single
+leaf, and when the two trees have different numbers of leaves.
+
+3.  Figure out a way to prove that your solution satisfies the
+requirements of the problem, in particular, that when the trees differ
+in an early position, your code does not waste time visiting the rest
+of the tree.  One way to do this is to add print statements to your
+functions so that every time you visit a leaf (say), a message is
+printed on the output.
+
+4.  What if you had some reason to believe that the trees you were
+going to compare were more likely to differ in the rightmost region?
+What would you have to change in your solution so that it compared the
+fringe from right to left?
+
+Streams
+-------
+
+A stream is like a list in that it contains a series of objects (all
+of the same type, here, type `'a`).  It differs from a list in that
+the tail of the list is left uncomputed until needed.  We will turn
+the stream on and off by thunking it (see class notes for [[week6]]
+on thunks, as well as [[assignment5]]).
+
+    type 'a stream = End | Next of 'a * (unit -> 'a stream);;
+
+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".
+