Program 4

Consider the language AFunExnExp, which is AFunExp extended with exceptions and conditionals: <L> := ... | (<L> + <L>) | (if <L> <L> <L>) | true | false | (zero? (<L>)) | (<L> and <L>) | (<L> or <L>) | (try <L> handle <L>) | (raise <L>) The second sub-expression of a try 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. and and or must short-circuit, i.e., not evaluate the second sub-expression if the first one evaluates to false or true, respectively. You can assume that AFunExnExp programs are closed. Exercises Write an eager interpreter for AFunExnExp using 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 exceptions. 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 cases! You must use handin to turn in your homework program(s). Run /cs/bin/handin -c cs173 program4 <filename(s)> to turn them in. You must provide two functions, main1 for the first exercise and main2 for the second exercise, that each accept an unparsed program representation and return a Scheme number, or a Scheme boolean (#t or #f), or the Scheme symbol <closure> (i.e., '<closure>), or the Scheme symbol <exception> (i.e., '<exception>) as appropriate. Follow this interface, and turn in thoroughly tested programs. We will use a script to test your implementation. If the script fails, you fail!