CS 7400 Machine Problem 7: Extending a Monadic Interpreter

Out: Tuesday, November 17, 2009

Due: Tuesday, November 24, 2009

For this problem, you will modify the interpreter in interps/exceptions.

1. (5 pts) Modify the language to allow an exception handler to pass a value back to the point that the error was raised, in the style of Exercise 5.40.
2. (10 pts) Modify the language to add mutable variables, in the style of monadic-store-passing. You will need to modify the monad. Remember that usually we have

   Comp(A) = X -> Ans

   where X is the stuff a computation needs in order to run and Ans is (roughly) what run-comp should return. For example, in the state monad, X is the state and Ans is A*State; for the continuation monad, X is a continuation and Ans could be anything; for the monad in the exception language, X is a pair of continuations.
3. (10 points) Extend the language with the following new kind of expression:

   Expression ::= "checkpoint" Body-Expression
                     "recover-with" "(" Identifier ")" Handler-Expression
   

   This is like a try expression, except that it checkpoints the store. That is, if an exception propagates to to the checkpoint, the Handler-Expression is evaluated with the identifier bound to the value of exception, as before, but in the store from before the evaluation of Body-Expression. As before, the Handler-Expression is evaluated only when an error propagates back to it. Unlike the situation in problem 1, we do not give the Handler-Expression the ability to return a value to the point where the error was raised.

   Be sure to construct some test cases that distinguish between "try" and "checkpoint".

   You should be able to accomplish this without changing the definition of Comp(A) from question 2; it should just be a matter of adding an additional operation to the monad.

4. Extra credit (10 points): Extend the language of cps-interps/monadic with the constructs choose(e1, e2) and fail. A choose expression first evaluates e1. A fail expression goes back to the chronologically last choose and evaluates e2 instead. If the chronologically last choose was already evaluating e2, then the failure propagates back to the chronologically preceding choose. This is called chronological backtracking. If there is no preceding choose, then the entire program fails. Note this is different from exceptions, because a choice extends beyond its scope. For example,

   let f = proc (x) -(choose(x, -(x,1)),
                     1)
   in let z = (f 1)
      in if zero?(z) then fail else z
   

   returns -1: When f is called with 1, the choose first returns 1, so f returns 0. zero?(z) becomes true, so we fail. We pick up again at the choose, which now returns 0. So now the call to f returns -1, z becomes bound to -1, and the entire computation returns -1. The call to fail is not within the call to f, yet it causes the computation to return to the choose (and the subtraction!) that was inside the call to f.

   This will require you to revise your monad again. Be sure to give a clear statement of the definition of your new Comp(A). You will have to decide what happens when the entire program fails, and how to represent this and test it.

   I've specified that you start with cps-interps/monadic here so you can concentrate on the backtracking. You may use your solution to one of the preceding problems 1, 2, or 3, if you really want to, but then you will have to think hard about how backtracking interacts with the store, exceptions, etc.

   If your solution relies on external reading, you must cite your sources.