Consider the language
AFunExnExp, which is
AFunExp extended with exceptions and conditionals:
<L> := ...
| (<L> + <L>)
| (if <L> <L> <L>)
| (zero? (<L>))
| (<L> and <L>)
| (<L> or <L>)
| (try <L> handle <L>)
| (raise <L>)
The second sub-expression of a
body is not
evaluated unless evaluating the first sub-expression raises an
exception. This second sub-expression must evaluate to a
procedure, which is applied to the raised value.
must short-circuit, i.e.,
not evaluate the second sub-expression if the first one
You can assume that
AFunExnExp programs are closed.
Write an eager interpreter for
the context-based interpreter strategy presented in class.
You may not use Scheme's continuations, exceptions or other
related control constructs (other than functions) to implement
The problem with the default implementation strategy is that
it's too slow for practical use. To get to the exception
handler, the implementation must pass through all the frames
of the context until the handler which are the frames
it was trying to skip. That is, processing an exception
takes time proportional to the length of the
context between the current execution point and the
nearest exception handler. In a practical system, a
programmer would expect constant time exception
handling. Adapt the context-based implementation to provide
this feature. Justify the time-complexity of your
implementation of exceptions.
Turning It In
Turn in all the code needed to run programs in
AFunExnExp (parser, interpreter, libraries, etc).
Your code is due by 2am (note new time!) on
2000-10-13. You must also turn in the test suite you
used to validate your solution. (Each test case in a test
suite consists of an input and its expected output.)
Your grade will take into account the quality of your test
You must use
handin to turn in your homework
/cs/bin/handin -c cs173 program4 <filename(s)>
to turn them in. You must provide two functions,
for the first exercise and
for the second exercise, that each accept an unparsed program
representation and return
- a Scheme number, or
- a Scheme boolean (
- the Scheme symbol
- the Scheme symbol
Follow this interface, and turn in thoroughly tested programs.
We will use a script to test your implementation. If the script
fails, you fail!