Differences with Racket’s exception system🔗

There are important differences between this project’s specification and Racket’s exception system.

In our approach, 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 ([(λ (x) #t) (λ (x) 1)])          (add1 #f))))

'err

Racket on the other hand, uses its exception mechanism to signal errors:

Examples

> (with-handlers ([(λ (x) #t) (λ (x) 1)])     (add1 #f))

1

Consequently Racket evaluates this expression to 1 for this example.

This simplifies things in our setting because the only way that 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 the semantics of Loot exceptions and Racket exceptions, we recommend always using 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, we assume each with-handlers has exactly one predicate and function.

Hints on implementation🔗

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, then a value is being returned normally, and we can pop off the handler information from the stack. However, if at some point during the execution of the body, there’s a raise, then we need to start the process of handling the raised value, applying the predicate, etc. A basic problem though is that there may be an arbitrary amount of stuff pushed on to the stack between the handler information and the point when the raise occurs.

For example:

Examples

> (define (f x)      (if (zero? x)          (raise x)          (+ x (f (sub1 x)))))

> (with-handlers ([(λ (x) #t) (λ (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. We now need the handler, but how? We can’t possibly use the compile-time environment to compute its location on the stack because it lives past that portion of the stack. But it is also worth noting that 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 we need to transfer control back to the with-handlers expression and execute the code that follows it. That means jumping back to the with-handlers, but how will raise know where to jump? We can store a return pointer together with the predicate and function. That way the raise can use the return address to jump back. But the issue remains: how does raise find all this handler information on stack?

A simple approach is to designate a register to hold a pointer to the handler on the stack. When executing a raise, the stack can be popped back to the handler, giving us access to the predicate, the function, and the return label used to jump back to the with-handlers expression.

This works great when there’s exactly one exception handler, but what happens when handlers are nested? It would seem a single register to point into the stack won’t suffice. The fix is to add a fourth piece of information to the handler information: the pointer to the parent handler.

And a designated register holds a pointer to the current handler.

Hint on implementation🔗

An implementation of arbitrarily large integers involves designing a good representation for these new kinds of values and then overloading arithmetic operations to work on both immediate integers (called fixnums) and pointer-based integers (called bignums), and in the case of binary operations, combinations of these kinds of integers.

Here’s a sketch of how bignums could be represented (but you are free to design the representation however you’d like).

A bignum can be a tagged pointer to a bit indicating the sign of the number and a linked list of “digits” in order of increasing significance. What we mean by “digit” is up to our choosing, but basically it’s an integer in some fixed range that can fit into a register. To explain the idea, let’s take this range to be [0,9] i.e. literally digits. The same approach will work for larger bases and for the real implementation, you’ll want to pick a larger base.

Let’s forget about the sign for a bit and assume we’re only dealing with positive bignums and let’s talk about the algorithm at a high-level.

With this representation in mind, numbers outside the range [0,9] can be represented by sequences of digits. For example, 192 would be represented as 2 9 1; 2025 would be 5 2 0 2. Notice that the least significant digit is first and the most significant is last.

Doing addition of two numbers follows the grade-school algorithm of adding each place of the numbers, from least to most significant digit, possibly with a carry. Whenever we reach the end of one of the numbers, we take an remaining digits from the other number.

For example adding 2 9 1 to 5 2 0 2, would go digit by digit:

• add 2 to 5 to get 7,

• add 9 to 2 to get 1, carrying 1,

• add 1 to 0 and the carried 1 to get 2,

• and now take the remaining digits, in this case just 2.

Thus the sum is 7 1 2 2, aka 2217, which is the sum of 2025 and 192.

Notice that each step of the computation only involves adding digits together and the sum of two digits can be represented as a single digit and possibly a carry. Also notice that this approach works no matter what base we choose.

Suppose we used base 100, then 192 would be represented as 92 1 and 2025 would be represented as 25 20.

To add them together:

• add 92 to 25 to get 17, carry 1

• add 1 to 20 and the carried 1 to get 22

Thus we get 17 22, aka 2217.

Now the idea for bignums is to use a large base for the “digits,” so long as it’s not larger than 264. The sum and possible carry of each pair of digits can be carried out with arithmetic instructions and machine integers and the arbitrarily large sequence of “digits” is represented using memory.

The core ideas and algorithms here are pretty simple but the details will involve some careful thought. You probably will save yourself a lot of trouble by working the details out using a high-level language first before trying to implement everything in assembly.

Bits to values🔗

Because this project involves your own memory representation for bignums, you will need to add functionality in types.rkt to bits->value so that Racket integers can be reconstructed from your representation of bignums. This is needed to test any programs that return bignum values. But this shouldn’t stop you from writing tests using expressions that compute intermediate results that are bignums, but whose final result is not a bignum. Several such tests are provided in the starter code.

You do not need to implement printing for bignums in the C run-time system. We will not test that code at all.