Assignment 9: Exceptions
Due: Thursday, July 9, 11:59PM
Starter code: loot-exceptions.zip
The goal of this assignment is to add an exception handling mechanism to the Loot compiler.
An exception handler consists of a predicate and a function. When a value is raised to a handler, the predicate is applied and if it produces a true value, the raised value is handled by applying the function to it. If the predicate returns #f, the value is raised to the next exception handler. An error is signalled if a raised value is never handled by an exception handler.
Use the starter code in loot-exceptions.zip, which is like Loot, but the parser, AST, and interpreter have been extended to include these new features. You have to extend the compiler to match the specification of the interpreter.
The key features that need to be added are:
(raise e) evaluates e and then raises the value to the most recently installed exception handler, thereby abandoning whatever computation surrounds the (raise e) expression up to the next exception handler. If there is no exception handler installed, an error is signalled.
(with-handlers ([e1 e2]) e) evaluates e1, then e2. The values of e1 and e2 are installed as the current exception handler predicate and function, respectively, while e is evaluated.
Should e produce a value v, the exception handler is removed and the with-handlers expression evaluates to v. But if in evaluating e, a value is raised that reaches this exception handler, the predicate is applied. If the predicate returns a true value, the result of the with-handlers expression is computed by applying the handler function to the raised value. If the predicate returns false, the value continues being raised, thereby abandoning whatever computation surrounds the with-handlers expression up to the next exception handler.
Examples
Examples
> (interp (parse '(raise 1))) 'err
This signals an error because there is no exception handler installed that handles the raised value 1.
Examples
> (interp (parse '(with-handlers ([(lambda (x) #t) (lambda (x) 0)]) 1))) 1
This evaluates to 1 because even though an exception handler is installed, the body of the with-handlers expression never raises.
Examples
> (interp (parse '(with-handlers ([(lambda (x) #t) (lambda (x) 0)]) (raise 1)))) 0
This evaluates to 0 because the predicate returns #t when applied to 1, so the result of the with-handlers expression is computed by applying the handler function to 1.
Examples
> (interp (parse '(with-handlers ([(lambda (x) #f) (lambda (x) 0)]) (raise 1)))) 'err
This signals an error because although there is an exception handler installed when 1 is raised, the predicate returns #f, so the value continues to be raised to the enclosing exception handler, but there is no such handler.
Examples
> (interp (parse '(with-handlers ([(lambda (x) #t) (lambda (x) 2)]) (with-handlers ([(lambda (x) #f) (lambda (x) 0)]) (raise 1))))) 2
This evaluates to 2 because 1 is raised to the most recent handler, which does not handle it, and then to the next handler, which does handle it.
Note that when a value is raised, it abandons the computation at the point of the raise.
Examples
> (interp (parse '(with-handlers ([(lambda (x) #t) (lambda (x) x)]) (+ (raise 1) (add1 #f))))) 1
Here the addition computation is abandoned when 1 is raised. Consequently, the expression (add1 #f) is never evaluated and the whole expression evaluates to 1.
Since the handler predicate and function are arbitrary functions, they too can raise exceptions, which will be handled by the surrounding exception handlers.
Examples
> (interp (parse '(with-handlers ([(lambda (x) (if (zero? x) #t (raise 0))) (lambda (x) x)]) (raise 1)))) 'err
This signals an error because in applying the predicate to 1, the value 0 is raised, and there is no enclosing handler.
It’s important to note that the most recently installed handler is a dynamic property; it is not a lexical property. A raise expression may occur lexically outside of the with-handlers form that ends up handling it.
Examples
> (interp (parse '(define (f x) (raise x)) '(with-handlers ([(lambda (x) #t) (lambda (x) x)]) (f 3)))) 3
Here, calling f triggers the raising of 3, which is handled by the with-handlers expression, producing 3.
Differences with Racket’s exception system
There are important differences between Loot exceptions and Racket’s exception system.
In Loot, errors are distinct from exceptions. For example, (add1 #f) signals an error. It does not raise an exception and therefore it cannot be handled with an exception handler:
Examples
> (interp (parse '(with-handlers ([(lambda (x) #t) (lambda (x) 1)]) (add1 #f)))) 'err
Racket, on the other hand, uses its exception mechanism to signal errors:
Examples
> (with-handlers ([(lambda (x) #t) (lambda (x) 1)]) (add1 #f)) 1
Consequently, Racket evaluates this expression to 1 for this example.
This simplifies things in Loot because the only way something can be raised is an explicit raise expression and anything that used to be an error continues to be an error.
Since there are subtle differences between Loot exceptions and Racket exceptions, use the interpreter for guidance on what a particular example should do.
Another difference is syntactic: Racket allows each with-handlers form to have any number of predicate and function clauses, but for our purposes, each with-handlers has exactly one predicate and function.
Implementation hints
An implementation of exception handling for Loot can be fairly succinct, but tricky.
The basic idea is that a handler is installed by with-handlers by pushing some information on the stack before executing the code for the body expression. This information will include the predicate value and function value for the handler.
If execution of the body makes it through to the end, a value is being returned normally, and the handler information can be popped off the stack. However, if at some point during execution of the body there is a raise, then the compiler needs to start the process of handling the raised value, applying the predicate, and so on. A basic problem is that there may be an arbitrary amount of stuff pushed on to the stack between the handler information and the point where the raise occurs.
For example:
Examples
> (define (f x) (if (zero? x) (raise x) (+ x (f (sub1 x)))))
> (with-handlers ([(lambda (x) #t) (lambda (x) 1)]) (f 100)) 1
The handler is pushed on the stack. As the recursion unfolds, return pointers, arguments, and intermediate results will be pushed on the stack. This continues until reaching the base case, at which point the raise occurs.
Everything on the stack up to the handler should be discarded because the raise discards the computation that has built up to this point: all those pending function calls will never be returned to. Instead, control needs to transfer back to the with-handlers expression and execute the code that follows it.
A simple approach is to designate a register to hold a pointer to the current handler on the stack. When executing a raise, the stack can be popped back to the handler, giving access to the predicate, the function, and the return label used to jump back to the with-handlers expression.
This works when there is exactly one exception handler, but nested handlers require one more piece of information: a pointer to the parent handler.
So each handler can be represented by four things pushed on the stack:
a predicate,
a function,
a return label, and
a pointer to the parent handler on the stack, if there is one.
A designated register can then hold a pointer to the current handler.
Submitting
Submit a zip file containing your work to Gradescope. Use make submit.zip from within the loot-exceptions directory to create a zip file with the proper structure.