Exceptions in Bril

by Rolph Recto September 25, 2019

Overview

We add exceptions as a control structure in Bril to support non-local control flow. This allows frontends to compile exceptions directly. The ultimate goal is to extend Bril further with more powerful control structures such as first-class continuations or algebraic effects.

Function Calls

To make the implementation of exceptions nontrivial and to make exceptions actually be non-local control structures, we first extend Bril so that it supports function calls. We do this by adding a call instruction that takes as arguments a function name and a list of function arguments. We also extended function declarations to allow for formal parameters. The Bril text format now allows for declarations of the form

funcName arg1:type1 ... argN:typeN { instrs }

Our interpreter implemention explicitly represents the program stack as an object.

The interpreter's activation record has four components:

• Bril function object --- the current function whose list of instructions is being executed

• Variable environment --- map from local variables to values

• Handler environment --- map from exception names to handlers (see below)

• PC index --- the index into the instruction list of the current instruction being executed

The interpreter proceeds by executing instructions, which either change environment mappings and/or set the PC to the index of the next instruction to execute. When call is executed, the interpreter does the following:

• The current activation record is pushed into the program stack.

• An empty variable environment is constructed, and the formal parameters of the function are mapped to the arguments of the call instruction. An empty handler environment is constructed.

• The PC index is changed to 0, and the variable and handler environments are updated to be empty. The interpreter resumes execution in this new state.

When a function returns, it pops the top of the program stack as the new activation record or, if the program stack is empty, ends program execution.

Exceptions

Once we added support for function calls, implementing exceptions came quite easily. We add two instructions to this end: handle exnName handlerLabel installs a handler for exception exnName in the handler environment, while throw exnName throws an exception with name exnName. When an exception exnName is called, the interpreter does the following:

• The interpreter performs stack unwinding: first, it checks if there is a handler for exnName in the current handler environment. If none exists, it pops the top of the program stack and checks for a handler in that activation frame. It does this until it finds an appropriate handler; otherwise, it throws a exception (in the metalanguage) since a Bril exception was not handled properly.

• Once it finds an appropriate handler, the interpreter sets the handler's activation record as its current activation record and then it jumps to the PC index of the handler label.

Apologia

Our implementation explicitly represents the program stack. Our implementation could also have implicitly represented the program stack using the interpreter's own stack by making recursive calls to evalFunc, but we obviated this design for the more explicit one to have finer control over the program stack of Bril and to support future development of other non-local control structures that manipulate the stack. (For example, first-class continuations would involve storing program stacks as values in the environment map.) Also, the implicit representation of program stacks would essentially fix the non-local control structures of Bril to the control structures the metalanguage has. With the implicit representation, to throw exceptions in Bril programs one would need to throw an exception in the interpreter as well; supporting first-class continuations or algebraic effects would be impossible in this way.

Our implementation of exception handlers does not support passing exception objects. To support this in the future, we will make handlers be standalone functions instead of just labels in an existing function. This would make reasoning about the control flow of the program even less local since it would make handlers not syntactically part of the contexts in which they might be thrown, so we obviated this design choice for the current implementation.

Another limitation of the current implementation of exceptions is the fact that handlers are not tied to a lexical scope. That means a handler would override any handler for the same exception name installed at the same function. We choose this simpler albeit somewhat unintuitive design to obviate the introduction of nested lexical scopes in Bril, which we believe is antithetical to its intended use as a simple intermediate language.

Evaluation

Our main goal for evaluation is to check whether our implementation is correct. We considered performance considerations as out of bounds for evaluation since the Bril interpreter is sufficiently different enough from how, say, ISA instructions are implemented in hardware that we cannot infer anything useful regarding the performance of an analogous implemenation of our exceptions mechanism in the latter from results in the former.

To evaluate correctness, we created a suite of tests that check a variety of situations in which exceptions might be used. The suite has both positive and negative test cases to check for normal use of exceptions and for when they are used improperly. An inexhaustive list of tests include:

• (Positive) No stack unwinding: thrown exception is handled by a handler installed in the current activation frame

• (Positive) Deep stack unwinding: thrown exception is handled by a handler high up in the stack

• (Negative) Unhandled exception: no handler is installed for an exception

Using the Turnt testing tool, we were able to verify that our implementation passes all the tests in the suite.