CSE 341 - Homework 7 - Continuations and Continuation Passing Style

Deliverable: submit two files: your source code, and a transcript showing the code in operation.

1. The traditional range function in Scheme takes two integer arguments m and n, and returns a list of all integers between m and n inclusive. For example

   (range 3 6) => (3 4 5 6)
   (range 4 4) => (4)
   (range 10 0) => ()
   

   Write a version of range in the Continuation Passing Style. For example

   (range 3 6 print)
   

   should cause the list (3 4 5 6) to be printed (where "print" above is the continuation argument).
2. Write an intersect function that finds the intersection of several sets represented as lists. This version of intersect should take a variable number of arguments, but at least one (zero arguments isn't enough). For example:

    (intersect '(1 2 3 4) '(3 4 5) '(1 2 3 4 5 6)) => (3 4)
    (intersect '(1 2 3)) => (1 2 3)
    (intersect '(1 2 3 4) '(3 4 5) '() '(1 2 3 4 5 6)) => ()
    (intersect) => error procedure intersect: expects at least 1 argument, given 0
   

   Hints: you can assume that the lists represent proper sets (no duplicate elements). You shouldn't write any error handling code for the case of feeding 0 arguments to intersect -- just write your function to expect at least one argument. You can have a helper function intersect2 that intersects two sets (which you might copy from HW 6 and rename).
3. Now write a function fast-intersect that is similar to the intersect function from the previous question, but that uses continuations to exit immediately if it encounters an empty set in the sets it is intersecting. (In this case there is no need to do any intersections at all, since once you throw an empty set in, the result will be the empty set.)

   Hint: study the list-product example from the lecture notes, which does a similar escape if it detects a 0 in the list of numbers being multiplied. You can put in extra print statements to show that indeed you are escaping without doing any intersecting if you encounter an empty set. (This is optional but recommended.)

Extra credit problems (10% max extra)

1. Write a version of the map function in the Continuation Passing Style:

   (map f lst k)
   

   This function should apply f to every element of the list lst, and feed the result to the continuation k. But wait! There's more. Just to make life interesting, f itself is also written in the Continuation Passing Style.
2. Consider the coroutine macro and same-fringe? function in the chapter from Teach Yourself Scheme in Fixnum Days. Define a Scheme struct to represent binary trees. Now define a coroutine to produce the values in the tree in preorder traversal, and another coroutine to print out those values. Hook them together and use this to print out the results of traversing some trees. Finally, also define coroutines to do inorder and postorder traversal, and show these in operation as well by printing out the tree in inorder and then in postorder. ("How can this be worth only 10% extra!!" I hear you cry ...)