The CS 6120 Course Blog

Exceptions in Bril

by Rolph Recto


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:

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:

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.


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:


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.


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:

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