Out: Tuesday, November 17, 2009
Due: Tuesday, November 24, 2009
For this problem, you will modify the interpreter in
monadic-store-passing. You will need to modify the monad. Remember that usually we have
Comp(A) = X -> Answhere
Xis the stuff a computation needs in order to run and
Ansis (roughly) what
run-compshould 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.
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.
cps-interps/monadicwith the constructs
chooseexpression first evaluates e1. A
failexpression goes back to the chronologically last
e2instead. If the chronologically last
choosewas 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 zreturns -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.
Last modified: Tue Nov 24 16:28:23 -0500 2009