add plotkin link
[lambda.git] / assignment9.mdwn
1 Using continuations to solve the same-fringe problem
2 ----------------------------------------------------
3
4 The problem
5 -----------
6
7 The problem, recall, is to take two trees and decide whether they have
8 the same leaves in the same order.
9
10 <pre>
11  ta            tb          tc
12  .             .           .
13 _|__          _|__        _|__
14 |  |          |  |        |  |
15 1  .          .  3        1  .
16   _|__       _|__           _|__
17   |  |       |  |           |  |
18   2  3       1  2           3  2
19
20 let ta = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
21 let tb = Node (Node (Leaf 1, Leaf 2), Leaf 3);;
22 let tc = Node (Leaf 1, Node (Leaf 3, Leaf 2));;
23 </pre>
24
25 So `ta` and `tb` are different trees that have the same fringe, but
26 `ta` and `tc` are not.
27
28 We've seen two solutions to the same fringe problem so far.  
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]], and
36 [[assignment8]]).  In that solution, we pulled the zipper on the first
37 tree until we found the next leaf, then stored the zipper structure in
38 a mutable variable while we turned our attention to the other tree.
39 This solution is efficient: the zipper doesn't visit any leaves beyond
40 the first 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 The first step is to review your answer to [[assignment8]], and make
47 sure you understand what is going on.
48
49
50 Two strategies for solving the problem
51 --------------------------------------
52
53
54 1.  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 2.  Review how the continuation-flavored `tree_monadizer` managed to
60     map a tree to a list of its leaves, in [[manipulating trees with monads]].
61     Spend some time trying to understand exactly what it
62     does: compute the tree-to-list transformation for a tree with two
63     leaves, performing all beta reduction by hand using the
64     definitions for `continuation_bind`, `continuation_unit` and so on.
65     If you take this route, study the description of **streams** (a
66     particular kind of data structure) below.  The goal will be to
67     arrange for the continuation-flavored `tree_monadizer` to transform
68     a tree into a stream instead of into a list.  Once you've done
69     that, completing the 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. (In OCaml: `print_int 1` prints an `int`, `print_string "foo"` prints a `string`, `print_newline ()` prints a line break, and `print_endline "foo"` prints a string followed by a line break.) If two trees differ in the middle of their fringe, you should show that your solution prints debugging information for the first half of the fringe, but then stops.
87
88 4.  What if you had some reason to believe that the trees you were
89 going to compare were more likely to differ in the rightmost region?
90 What would you have to change in your solution so that it worked from
91 right to left?
92
93 Streams
94 -------
95
96 A stream is like a list in that it wraps a series of elements of a single type.
97 It differs from a list in that the tail of the series is left uncomputed
98 until needed.  We will turn the stream on and off by thunking it (see
99 class notes for [[week6]] on thunks, as well as [[assignment5]]).
100
101     type 'a stream = End | Next of 'a * (unit -> 'a stream);;
102
103 There is a special stream called `End` that represents a stream that
104 contains no (more) elements, analogous to the empty list `[]`.
105 Streams that are not empty contain a first object, paired with a
106 thunked stream representing the rest of the series.  In order to get
107 access to the next element in the stream, we must *force* the thunk by
108 applying it to the unit.  Watch the behavior of this stream in detail.
109 This stream delivers the natural numbers, in order: 1, 2, 3, ...
110
111 <pre>
112 # let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
113 val make_int_stream : int -> int stream = [fun]
114
115 # let int_stream = make_int_stream 1;;
116 val int_stream : int stream = Next (1, [fun])         (* First element: 1 *)
117
118 # let tail = match int_stream with Next (i, rest) -> rest;;      
119 val tail : unit -> int stream = [fun]                 (* Tail: a thunk *)
120
121 (* Force the thunk to compute the second element *)
122 # tail ();;
123 - : int stream = Next (2, [fun])                      (* Second element: 2 *)
124
125 # match tail () with Next (_, rest) -> rest ();;
126 - : int stream = Next (3, [fun])                      (* Third element: 3 *)
127 </pre>
128
129 You can think of `int_stream` as a functional object that provides
130 access to an infinite sequence of integers, one at a time.  It's as if
131 we had written `[1;2;...]` where `...` meant "continue for as long as
132 some other process needs new integers".
133
134
135 <!--
136 With streams in hand, we need only rewrite our continuation tree
137 monadizer so that instead of mapping trees to lists, it maps them to 
138 streams.  Instead of 
139
140         # tree_monadize (fun a k -> a :: k a) t1 (fun t -> []);;
141         - : int list = [2; 3; 5; 7; 11]
142
143 as above, we have 
144
145         # tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End);;
146         - : int stream = Next (2, <fun>)
147
148 We can see the first element in the stream, the first leaf (namely,
149 2), but in order to see the next, we'll have to force a thunk.
150
151 Then to complete the same-fringe function, we simply convert both
152 trees into leaf-streams, then compare the streams element by element.
153 The code is entirely routine, but for the sake of completeness, here it is:
154
155         let rec compare_streams stream1 stream2 =
156                 match stream1, stream2 with 
157                 | End, End -> true (* Done!  Fringes match. *)
158                 | Next (next1, rest1), Next (next2, rest2) when next1 = next2 -> compare_streams (rest1 ()) (rest2 ())
159                 | _ -> false;;
160
161         let same_fringe t1 t2 =
162           let stream1 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t1 (fun _ -> End) in 
163           let stream2 = tree_monadize (fun i k -> Next (i, fun () -> k ())) t2 (fun _ -> End) in 
164           compare_streams stream1 stream2;;
165
166 Notice the forcing of the thunks in the recursive call to
167 `compare_streams`.  So indeed:
168
169         # same_fringe ta tb;;
170         - : bool = true
171         # same_fringe ta tc;;
172         - : bool = false
173
174 Now, you might think that this implementation is a bit silly, since in
175 order to convert the trees to leaf streams, our `tree_monadizer`
176 function has to visit every node in the tree, so we'd have to traverse
177 the entire tree at some point.  But you'd be wrong: part of what gets
178 suspended in the thunking of the stream is the computation of the rest
179 of the monadized tree.
180
181 -->