Assignment 6, Due 12/06/02 1:00 p.m.

1. Imagine that your language that has try-catch statement similar to Java but does not have a "finally" clause.  Let's suppose that you need to write the following (in Java-like syntax):

   try
     B
   finally F

   B and F are code blocks.  (i) Show how you will write the above code using the try-catch assuming that only exceptions can cause a statement to terminate abruptly;  (ii) Does your transformation work if return statements may also cause a statement to terminate abruptly?  If your answer is "yes", then argue why.  If your answer is "no", then explain why not and suggest one way of making it work.

2. Consider the following code fragment:

   class E1 extends Exception {...}
   class E2 extends Exception {...}
   class E3 extends Exception {...}
   void f() throws Exception {
     try {
       try {
         B0
       }
       catch (E1 e11) {... B1 ...}
     }
     catch (E1  e12) { ... B2 ...}
   }
   void g() {
     try {
       f()
     }
     catch (Exception e) { ... B3 ...}
   }
    

   Assume that B0, B1, B2, and B3 are code blocks that may throw an exception but do not contain any try statements.

   1. Give the exception tables at the blocks B0, B1, B2, B3, and the call to f in g.
   2. Can the outer exception handler for E1 in f ever be reached?  Explain why or why not giving an example. 
   3. Work through your example in part (ii) using the exception tables you constructed in part (i)
3. In class, we considered how to use continuations to quickly report "success" and to "backtrack" in a game tree.  Imagine that you are using Java that has exceptions but no continuations.  (i) Can you use exceptions instead of the "success" continuation?  (ii) Can you use exceptions instead of the "backtrack" continuation.  For these two questions, if the answer is "yes", then give the code that uses exceptions instead of continuations.  If the answer  is "no" then explain what about the example is hard to do with exceptions but not hard with continuations.  
4. Write the following function:
          sublist: ''a list * ''a list  -> bool
        "sublist" takes a pair of lists, and returns true if the first list is a prefix of the second list (i.e., all the elements of the first list appear at the beginning of the second list in the same order).  Use continuations (callcc) in your code so that sublist exits immediately if finds that the lists are not identical.
5. What is the difference between an escaping and a non-escaping continuation?  Outline how might implement continuations if the language guarantees that all continuations are non-escaping. Outline how you might implement continuations if the language allows continuations to escape.
6. Wilson's paper "Uniprocessor garbage collection techniques" says in Section 1.3: "For a purely statically-typed language, no per-object type information is necessary, except the types of the root set variables".
   1. Explain why this statement is true
   2. Do Java programs need the "per-object type information"?  Why or why not?
7. Lackwit annotates all variables with its (refined) types.  A programmer can use Lackwit output by checking if two unrelated variables have the same Lackwit type.  If they do then there may have been a flow of values between them, which should not be the case for unrelated variables.  Give a program for which Lackwit will say that two variables have the same type even though when the program is run, there is never any flow of values between the two variables.