Instructions:
This problem and the next will be submitted as Plait code.
Many programming languages like Java have named exceptions that let you raise and handle specific exceptions. For example, the following Java program snippet shows how to catch an ArithmeticException when a division by zero occurrs:
public static void main(String[] args) {
int n = 10;
int m = 0;
try {
// Code that may throw an exception
int ans = n / m;
System.out.println("Answer: " + ans);
}
catch (ArithmeticException e) {
// Handling the exception
System.out.println("Error: Division by zero is not allowed!");
} finally {
System.out.println( "Program continues after handling the exception.");
}
}
Your task in this problem is to implement a stack machine for a small language with named exceptions. Here is the abstract syntax of the language:
> (define-type Exn
(numE [n : Number])
(addE [e1 : Exn] [e2 : Exn])
(identE [id : Symbol])
(appE [e1 : Exn] [e2 : Exn])
(lamE [arg : Symbol] [body : Exn])
(tryE [body : Exn] [code : Symbol] [handler : Exn])
(raiseE [code : Symbol]))
The numE, addE, identE, appE, and lamE expressions behave as normal for the lambda calculus extended with numbers. Since we did not cover stack machines for STLC in class, please refer to the supplement stlc_stack_rules.pdf for an on-paper description of how your stepper should behave.
The (raiseE code) expression raises an exception with a particular code. If that code is not handled by any exception handler, then an ’unhandled-exception error should be raised.
The (tryE body code handler) runs body and jumps to the the inner-most handler expression if an exception with tag code is raised.
For this problem evaluation order is critical: for (addE e1 e2), e1 is evaluated first and then e2; for appE e1 e2, e1 is evaluated first and then e2.
You should design your own set of stack frames for this language and implement a function step : (State -> State), where states are (eval k e) or (retn k v) or (fail k c) for stacks k, values v, expressions e, and exception codes c. We have provided utility functions stepm and start as defined in class (see Lectures 14-15) which will allow you to perform end-to-end tests on your code, and which we will use in the autograder.
Example:
> (stepm (start (tryE (raiseE 'catchme)
'catchme
(numE 10))))
(retn (emp) (numV 10))
> (stepm (start
(tryE
(tryE (addE (raiseE 'catchme1) (raiseE 'catchme2))
'catchme2 (numE 10))
'catchme1 (numE 20))))
(some (retn (emp) (numV 20)))
We will autograde the multi-step function, and not the single-step function, so that you can design your own set of frames and rules, but you should thoroughly document them so we can manually check your stack-based implementation of step.
Many problems in computer science involve backtracking searching through a space of possible solutions. In this problem, we will make a small programming language for solving problems that involve backtracking search by introducing non-determinism and failure.
Here is the abstract syntax of the Amb language, introduced by John McCarthy in 1963:
> (define-type Amb
(ifA [guard : Amb] [thn : Amb] [els : Amb])
(andA [e1 : Amb] [e2 : Amb])
(notA [e : Amb])
(boolA [b : Boolean])
(identA [id : Symbol])
(chooseA [id : Symbol] [body : Amb])
(failA))
The language has some familiar constructs (conditionals, and, not, Booleans, and identifiers), and two new constructs: chooseA and failA. Their semantics are:
(failA) denotes failure: it means that this run of the program is invalid and should be rejected.(chooseA id body) tries to find a non-failing assignment to id. First, it runs body with id assigned to #t; if this fails, then it tries to run body with id assigned to #f; if this also fails, then the (chooseA id body) itself fails.If all paths in an Amb program fails, then your interpreter should raise a ’no-valid-assignment error.
Your task is to implement a definitional interpreter for Amb programs called interp-amb. Here are some examples of running Amb programs:
> (interp-amb (chooseA 'x (ifA (identA 'x) (failA) (boolA #t))))
#t
> (interp-amb (chooseA 'x (ifA (identA 'x) (failA) (failA))))
no-valid-assignment: no assignment found
> (interp-amb (chooseA 'x
(chooseA 'y
(ifA (identA 'x) (failA) (identA 'x)))))
#f
Your solution should make use of continuations to implement backtracking. You will need to use a helper function for your implementation that keeps track of the necessary continuations and other program state.