assignment9.mdwn

   1 Using continuations to solve the same-fringe problem
   2 ----------------------------------------------------
   3
   4 The problem
   5 -----------
   6
   7 We've seen two solutions to the same fringe problem so far.
   8 The problem, recall, is to take two trees and decide whether they have
   9 the same leaves in the same order.
  10
  11 <pre>
  12  ta            tb          tc
  13  .             .           .
  14 _|__          _|__        _|__
  15 |  |          |  |        |  |
  16 1  .          .  3        1  .
  17   _|__       _|__           _|__
  18   |  |       |  |           |  |
  19   2  3       1  2           3  2
  20
  21 let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
  22 let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
  23 let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
  24 </pre>
  25
  26 So `ta` and `tb` are different trees that have the same fringe, but
  27 `ta` and `tc` are not.
  28
  29 The simplest solution is to map each tree to a list of its leaves,
  30 then compare the lists.  But because we will have computed the entire
  31 fringe before starting the comparison, if the fringes differ in an
  32 early position, we've wasted our time examining the rest of the trees.
  33
  34 The second solution was to use tree zippers and mutable state to
  35 simulate coroutines (see [[coroutines and aborts]]).  In that
  36 solution, we pulled the zipper on the first tree until we found the
  37 next leaf, then stored the zipper structure in the mutable variable
  38 while we turned our attention to the other tree.  This solution is
  39 efficient: the zipper doesn't visit any leaves beyond the first
  40 mismatch.
  41
  42 Since zippers are just continuations reified, we expect that the
  43 solution in terms of zippers can be reworked using continuations, and
  44 this is indeed the case.  Your assignment is to show how.
  45
  46 TO-DO LIST for solving the problem
  47 ----------------------------------
  48
  49 1.  Review the simple but inefficient solution (easy).
  50 2.  Understand the zipper/mutable state solution in [[coroutines and aborts]] (harder).
  51
  52 3.  Two obvious approaches:
  53
  54 a.  Review the list-zipper/list-continuation example given in
  55     class in [[from list zippers to continuations]]; then
  56     figure out how to re-functionalize the zippers used in the zipper
  57     solution.
  58
  59 b.  Review how the continuation-flavored tree\_monadizer managed to
  60 map a tree to a list of its leaves, in [[manipulating trees with
  61 monads]].  Spend some time trying to understand exactly what it does:
  62 compute the tree-to-list transformation for a tree with two leaves,
  63 performing all beta reduction by hand using the definitions for
  64 bind\_continuation, unit\_continuation and so on.  If you take this
  65 route, study the description of streams (a particular kind of data
  66 structure) below.  The goal will be to arrange for the
  67 continuation-flavored tree_monadizer to transform a tree into a stream
  68 instead of into a list.  Once you've done that, completing the
  69 same-fringe problem will be easy.
  70
  71 -------------------------------------
  72
  73 Whichever method you choose, here are some goals to consider.
  74
  75 1.  Make sure that your solution gives the right results on the trees
  76 given above (`ta`, `tb`, and `tc`).
  77
  78 2.  Make sure your function works on trees that contain only a single
  79 leaf, as well as when the two trees have different numbers of leaves.
  80
  81 3.  Figure out a way to prove that your solution satisfies the main
  82 requirement of the problem; in particular, that when the trees differ
  83 in an early position, your code does not waste time visiting the rest
  84 of the tree.  One way to do this is to add print statements to your
  85 functions so that every time you visit a leaf (say), a message is
  86 printed on the output.  If two trees differ in the middle of their
  87 fringe, you should show that your solution prints debugging
  88 information for the first half of the fringe, but then stops.
  89
  90 4.  What if you had some reason to believe that the trees you were
  91 going to compare were more likely to differ in the rightmost region?
  92 What would you have to change in your solution so that it worked from
  93 right to left?
  94
  95 Streams
  96 -------
  97
  98 A stream is like a list in that it contains a series of objects.  It
  99 differs from a list in that the tail of the list is left uncomputed
 100 until needed.  We will turn the stream on and off by thunking it (see
 101 class notes for [[week6]] on thunks, as well as [[assignment5]]).
 102
 103     type 'a stream = End | Next of 'a * (unit -> 'a stream);;
 104
 105 There is a special stream called `End` that represents a stream that
 106 contains no (more) elements, analogous to the empty list `[]`.
 107 Streams that are not empty contain a first object paired with a
 108 thunked stream representing the rest of the series.  In order to get
 109 access to the next element in the stream, we must forced the thunk by
 110 applying it to the unit.  Watch the behavior of this stream in detail.
 111 This stream delivers the natural numbers, in order: 1, 2, 3, ...
 112
 113 <pre>
 114 # let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
 115 val make_int_stream : int -> int stream = [fun]
 116
 117 # let int_stream = make_int_stream 1;;
 118 val int_stream : int stream = Next (1, [fun])         (* First element: 1 *)
 119
 120 # let tail = match int_stream with Next (i, rest) -> rest;;
 121 val tail : unit -> int stream = <fun>                 (* Tail: a thunk *)
 122
 123 (* Force the thunk to compute the second element *)
 124 # tail ();;
 125 - : int stream = Next (2, [fun])
 126
 127 # match tail () with Next (_, rest) -> rest ();;
 128 - : int stream = Next (3, <fun>)
 129 </pre>
 130
 131 You can think of `int_stream` as a functional object that provides
 132 access to an infinite sequence of integers, one at a time.  It's as if
 133 we had written `[1;2;...]` where `...` meant "continue for as long as
 134 some other process needs new integers".