edit

[lambda.git] / assignment9.mdwn

diff --git a/assignment9.mdwn b/assignment9.mdwn
index 2277a92..dfc4d47 100644 (file)
--- a/assignment9.mdwn
+++ b/assignment9.mdwn
@@ -4,7 +4,6 @@ Using continuations to solve the same-fringe problem
 The 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.
 
 The problem, recall, is to take two trees and decide whether they have
 the same leaves in the same order.
 


@@ -26,6 +25,7 @@ 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.
 
 So `ta` and `tb` are different trees that have the same fringe, but
 `ta` and `tc` are not.
 

+We've seen two solutions to the same fringe problem so far.  

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


@@ -35,10 +35,9 @@ 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
 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.
+while we turned our attention to the other tree.  This solution is
+efficient: the zipper doesn't visit any leaves beyond the first
+mismatch.

 
 Since zippers are just continuations reified, we expect that the
 solution in terms of zippers can be reworked using continuations, and
 
 Since zippers are just continuations reified, we expect that the
 solution in terms of zippers can be reworked using continuations, and


@@ -57,75 +56,79 @@ a.  Review the list-zipper/list-continuation example given in
     figure out how to re-functionalize the zippers used in the zipper
     solution.
 
     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. 
+b.  Review how the continuation-flavored tree\_monadizer managed to
+map a tree to a list of its leaves, in [[manipulating trees with
+monads]].  Spend some time trying to understand exactly what it does:
+compute the tree-to-list transformation for a tree with two leaves,
+performing all beta reduction by hand using the definitions for
+bind\_continuation, unit\_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
 
 -------------------------------------
 
 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.
+given above (`ta`, `tb`, and `tc`).

 
 2.  Make sure your function works on trees that contain only a single
 
 2.  Make sure your function works on trees that contain only a single

-leaf, and when the two trees have different numbers of leaves.
+leaf, as well as 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
+3.  Figure out a way to prove that your solution satisfies the main
+requirement 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
 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.  
+printed on the output.  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.

 
 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?
 
 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?
+What would you have to change in your solution so that it worked from
+right to left?

 
 Streams
 -------
 
 
 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]]). 
+A stream is like a list in that it contains a series of objects.  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);;
 
 
     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 `[]`.
 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:
+Streams that are not empty contain a first object paired with a
+thunked stream representing the rest of the series.  In order to get
+access to the next element in the stream, we must forced the thunk by
+applying it to the unit.  Watch the behavior of this stream in detail.
+This stream delivers the natural numbers, in order: 1, 2, 3, ...

 
 <pre>
 # let rec make_int_stream i = Next (i, fun () -> make_int_stream (i + 1));;
 val make_int_stream : int -> int stream = [fun]
 
 <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 *)
 # 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 *)
+
+# let tail = match int_stream with Next (i, rest) -> rest;;      
+val tail : unit -> int stream = <fun>                 (* Tail: a thunk *)

 
 (* Force the thunk to compute the second element *)
 
 (* Force the thunk to compute the second element *)

-# (match int_stream with Next (i, rest) -> rest) ();;
+# tail ();;

 - : int stream = Next (2, [fun])      
 - : int stream = Next (2, [fun])      

+
+# match tail () with Next (_, rest) -> rest ();;
+- : int stream = Next (3, <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
 </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".
- 
-
+we had written `[1;2;...]` where `...` meant "continue for as long as
+some other process needs new integers".