CSE 340 Homework 8

The last one!

Due Friday 23 April, 2002

This homework gives you more experience with converting programs to be tail recursive and for using exceptions to explicitly manipulate the flow of control.

The file dfs.ml contains a simple ML implementation of graphs and depth-first-search.

1. Reimplement dfs_aux and dfs_edges so that they are tail recursive (i.e. in continuation-passing style). Use the data structure representation of continuations. Start with the following definition of dfs:

   let rec dfs (start:node) (stop:name) : path option = 
     dfs_aux start stop [] Halt
   

2. Change the implementation in Part 1 so that dfs_aux and dfs_edges do not need the "visited" argument. You should be able to determine whether a node has been seen already by looking at the continuation. Start with the following definition of dfs:

   let rec dfs (start:node) (stop:name) : path option = 
     dfs_aux start stop Halt
   

3. However, instead of deleting the "visited" argument, we can use it to optimize our depth-first search. The previous implementations of dfs do not remember every node that has been visited in a traversal, only those on the current path. (That is why the continuation, which records the path, could subsume visited.) While this is good enough to ensure the termination of the algorithm, it does mean that parts of the graph may be covered multiple times. For example, consider the following graph where the node a has an edge to b and d, b has an edge to c, d has an edge to e and c has an edge to f:

      a -> d -> e 
      |    |
      V    V
      b -> c -> f 

   A depth first search of this graph, starting at a and looking for e might traverse the nodes in this order:
   

    a b c f (go back to a and do other edge) d c f (go back to d and do other edge) e. 

   It would be better to stop at c the second time and not traverse f twice. Rewrite your answer to part 1 so that the visited argument contains all of the edges ever seen in the graph. Hint: make visited an additional argument of apply_cont. (Of course, the running time of dfs won't change until we use a faster representation of the set of visited nodes than lists).
   
   
4. Now consider an implementation of dfs that finds the value of a node instead of a path to the node. Rewrite the functions dfs_aux and dfs_edges in dfs-value.ml to be tail recursive as in part 1. However, when the value is found, instead of calling apply-cont with the current continuation, we can do better. We know that the found value is what should be returned from the function, so call apply_cont with Halt to immediately return the value.  Why could we not do this trick for part 1?
    
5. Rewrite the direct-style version of dfs in dfs-value.ml to use exceptions to do a similar trick as in part 4. When you find the answer, throw an exception that is caught by dfs.