14 Implementing Exceptions🔗

We’ve seen a few different intuitions for continuation-passing style that we’ll briefly recap here:

• Continuations behave like universal accumulators that let you write programs in tail form.

• Continuations are functions that hold "the rest of the work to do"; you call a continuation with the result of the computation and it finishes the job.

• Continuations give you explicit control flow: when programs are written in continuation-passing style, function calls never need to return control flow to their callsites. All control is transferred explicitly by calling a continuation.

Last time we saw an example of how to use continuations to implement a return construct. Now let’s see how to implement exceptions, and grow our language to include a few more features.

14.1 Exceptions🔗

Consider the following abstract syntax and values for ExnLang, a language with catchable exceptions and lambdas:

> (define-type Exn     (numE [n : Number])     (addE [e1 : Exn] [e2 : Exn])     (identE [id : Symbol])     (appE [e1 : Exn] [e2 : Exn])     (lamE [arg : Symbol] [body : Exn])     (tryE [body : Exn] [handler : Exn])     (raiseE))

> (define-type ExnValue     (lamV [id : Symbol] [body : Exn])     (numV [n : Number]))

Our goal will be to make a definitional interpreter for this language to better understand how exceptions work and can be implemented.

First, let’s see some examples of the semantics of this language to get a better feel for how exceptions work. Consider this case:

(define prog1

(tryE (addE (raiseE) 2)

10))

In the event that an exceptoin is raised outside of any tryE expression, a uncaught-exception error should be raised.

prog1 should run to (numV 10): an exception is raised during addition, and we should immediately jump to the handler and return 10.

Lambdas make things quite a bit trickier. Consider the following program:

(define f1 (lamE 'x (raiseE)))

(define f2 (lamE 'f

(tryE (appE (identE 'f) (numE 10))

(numE 20))))

(define prog2

(appE f1 f2))

What should prog2 run to? Parse it carefully: this program should run to (numV 20). f1 raises an exception as soon as it’s called. f2 calls its argument and catches any exceptions that are raised with a handler that simply runs to 20. Notice that f1 does not know what handler it will be called with when it is defined; it could in fact be called multiple times with different handlers! We will need to handle this carefully in our interpreter.

14.1.1 Implementing the Interpreter🔗

Let’s begin implementing a definitional interpreter for this language. We will have a couple of standard helper functions for substitution and converting between values and expressions:

> (define (subst e1 x e2)     (type-case Exn e1                [(numE n) (numE n)]                [(addE l r)                 (addE (subst l x e2) (subst r x e2))]                [(identE id)                 (if (equal? id x) e2 (identE id))]                [(appE l r)                 (appE (subst l x e2) (subst r x e2))]                [(lamE arg body)                 (if (equal? x arg)                     (lamE arg body)                     (lamE arg (subst body x e2)))]                [(tryE body handler)                 (tryE (subst body x e2)                       (subst handler x e2))]                [(raiseE) (raiseE)]))

> (define (val->expr v)     (type-case ExnValue v                [(lamV id body) (lamE id body)]                [(numV n) (numE n)]))

To structure our interpreter we will have two continuations: a default continuation defaultk that is run if no exceptions are raised, and an exnk that is run if an exception is raised.

> (interp-exn-h : (Exn (ExnValue -> 'a) (-> 'a) -> 'a))

> (define (interp-exn-h e defaultk exnk)     (type-case Exn e                [(numE n) (defaultk (numV n))]                [(addE e1 e2)                 (interp-exn-h e1                               (λ (e1k)                                 (interp-exn-h e2                                               (λ (e2k)                                                 (defaultk (numV (+ (numV-n e1k) (numV-n e2k)))))                                               exnk))                               exnk)]                [(identE id) (error 'runtime "unbound ident")]                [(appE e1 e2)                 (interp-exn-h e1                               (λ (e1k)                                 (interp-exn-h e2                                              (λ (e2k)                                                (let* ([id (lamV-id e1k)]                                                       [body (lamV-body e1k)]                                                       [subst-body (subst body id (val->expr e2k))])                                                  (interp-exn-h subst-body defaultk exnk)))                                              exnk))                               exnk)]                [(tryE body handler)                 (interp-exn-h body defaultk                               (λ () (interp-exn-h handler defaultk exnk)))]                [(raiseE) (exnk)]                [(lamE id body) (defaultk (lamV id body))]))

> (interp-exn : (Exn -> ExnValue))

> (define (interp-exn e)     (interp-exn-h e                   (λ (x) x)                   (λ () (error 'uncaught-exception "uncaught exception error"))))

> (test (interp-exn (tryE (addE (raiseE) (numE 2))                           (numE 10)))         (numV 10))

- Void good (interp-exn (tryE (addE (raiseE) (numE 2)) (numE 10))) at line 10   expected: (numV 10)   given: (numV 10)

> (define prog2 (appE (lamE 'f                             (tryE (appE (identE 'f) (numE 10))                                   (numE 20)))                       (lamE 'x (raiseE))))

> (test (interp-exn prog2)         (numV 20))

- Void good (interp-exn prog2) at line 12   expected: (numV 20)   given: (numV 20)

There are a few things to note about the above interpreter, which we will discuss in detail in class:

• The (raiseE) arm simply calls the exception continuation.

• The (tryE body handler) case runs the interpreter on body with a new exception handler that calls the interpreter on handler. Note that this lambda captures the outer defaultk and exnk continuations; this is important for handling nested try blocks.

14.2 Compiling Away Exceptions🔗

Now we will study how to compile ExnLang into the untyped lambda calculus. Why do we want to do this? This gives us a way to add exceptions to languages that do not have exceptions in them! For example, you can add exceptions to C programs this way.

The core idea of this compiler is carefully translate the above interpreter into the lambda calculus. Here is the full source listing, which we will discuss in detail in class:

(compile : (Exn Lam Lam -> Lam))

(define (compile e defaultk exnk)

(type-case Exn e

[(numE n)

; apply the default continuation to the number

(appL defaultk (numL n))]

[(identE x)

; apply the default continuation to the identifier

(appL defaultk (identL x))]

[(addE e1 e2)

; label the results of computing e1 and e2 as r1 and r2

(compile e1

(lamL 'r1 (compile e2

(lamL 'r2

; apply the default continuation to the result

; of adding r1 and r2

(appL defaultk (addL (identL 'r1) (identL 'r2))))

exnk))

exnk)]

[(tryE body handle)

; compile the body with an exception handler that calls the handler

(compile body defaultk (lamL '_ (compile handle defaultk exnk)))]

[(lamE x body)

; compiling lambdas is tricky because we don't know yet which exception handlers

; and default continuation will be active when the lambda is eventually called.

; To deal with this, we add two extra arguments to the lambda: a defaultk,

; and an 'exnk, which are *themselves* lambdas. During application, we will

; have to call lambdas with extra arguments to pass in the default and

; exception continuations.

(appL defaultk (lamL 'defaultk

(lamL 'exnk

(lamL x (compile body (identL 'defaultk) (identL 'exnk))))))]

[(appE e1 e2)

(compile e1

(lamL 'e1v

(compile e2

(lamL 'e2v

; now we have to call e1v with 3 arguments:

; 1. the current default continuation

; 2. the current exception continuation

; 3. e2v, the argument

(appL (appL (appL (identL 'e1v) defaultk) exnk) (identL 'e2v)))

exnk))

exnk)]

[(raiseE)

; simply call the exception continuation

(appL exnk (numL 0))]))

(test (interp (compile (addE (numE 1) (numE 2))

(lamL 'x (identL 'x))

(lamL 'x (errorL))))

(numLV 3))

(test (interp (compile (addE (addE (numE 1) (numE 2)) (numE 3))

(lamL 'x (identL 'x))

(lamL 'x (errorL))))

(numLV 6))

(test (interp (compile (tryE (addE (raiseE) (numE 2))

(numE 10))

(lamL 'x (identL 'x))

(lamL 'x (errorL))))

(numLV 10))

(test (interp (compile (appE (lamE 'x (numE 10)) (numE 20))

(lamL 'x (identL 'x))

(lamL 'x (errorL))))

(numLV 10))

(test (interp (compile prog2

(lamL 'x (identL 'x))

(lamL 'x (errorL))))

(numLV 20))