Why Python and Racket?
My undergrad compilers class has to implement a compiler for Python.
The intermediate representation used by their compiler is a cut-down Racket extended with Pythonic control-flow constructs.
That's why you'll find motivating examples in Python that get desugared into a Racket-like code.
A note on
This code makes heavy use of
Not all languages support escape continuations, but many support the (more general) full continuations. Full continuations work in place of escape continuations with a mild performance penalty.
You can also simulate
in C with
Newcomers to functional programming are often
struck by the lack of a
(and, I suppose, by the lack of statements entirely).
There are natural coding patterns that exploit the ability to bail out of a function early, like the following:
def f(): if easy case: return this if also easy case: return that do something complicated down here
Fortunately, it's easy to add a return statement to functional languages that support continuations.
A return statement is a "second-class escape continuation."
Conversely, think of an escape continuation as a first-class return statement.
That is, imagine that
return was just a special procedure bound every time
you entered a function, and that to return from the function, you passed the
return value to this special procedure.
In Racket, we can grab the escape continuation for a function with
call/ec for short.
If we want to add a
define/return form to the language
so that the following works:
(define/return (max a b) (when (> a b) (return a)) (return b))
we can create a macro that desugars it into:
(define (max a b) (call/ec (lambda (return) (when (> a b) (return a)) (return b))))
(define-syntax (define/return stx) (syntax-case stx () [(_ f-params body ...) ; => (with-syntax ([return (datum->syntax #'f-params 'return)]) #'(define f-params (call/ec (λ (return) body ...))))]))
It's just as easy to add a
while loop seems easy
to implement in terms of tail-recursion or gotos.
In fact, it is.
complicate matters--especially when it comes time to
like return, are also escape continuations.
It's also best to implement these features as escape continuations.
Take the general
while loop form in
Python for example:
while cond: body else: otherwise
This would be desugared in Racket as:
(call/ec (λ (break) (letrec ([loop (λ () (when cond (call/ec (λ (continue) body)) (loop)))]) (loop) otherwise)))
A call to
bails out of the loop, skipping over the else case.
A call to
jumps to the next iteration of the loop.
A macro to transform
(while cond body else) forms is:
(define-syntax (while stx) (syntax-case stx () [(_ cond body else) ; => (with-syntax ([break (datum->syntax #'body 'break)] [continue (datum->syntax #'body 'continue)]) #'(call/ec (λ (break) (letrec ([loop (λ () (when cond (call/ec (λ (continue) body)) (loop)))]) (loop) else))))]))
Exceptions are the canonical example of escape continuations.
A reasonable approach for implementing exceptions is to create a special "handler" cell in memory. That cell contains the escape continuation to invoke once an exception is raised.
Let's start by compiling a
(try body handler)
This is a
try form without
We're going to add two global procedures to help--
(define $current-handler (lambda (ex) (error "top-level exception!"))) (define (current-handler) $current-handler) (define (set-current-handler! handler) (set! $current-handler handler))
$current-handler holds a pointer
to the current exception handler.
An isolated desugaring of the
try form is not hard:
(let ([$old (current-handler)]) (call/ec (lambda (ec) (set-current-handler! (lambda (ex) (set-current-handler! $old) (ec (handler ex)))) (let ([rv body]) (set-current-handler! $old) rv))))
- saves the old exception handler in
- captures the current escape continuation in
- sets a new handler that invokes
- runs the body.
Whether the body returns naturally, or by invoking an exception, the old handler gets restored.
But, what happens if we have code like the following?
def f(): try: return 10 except: print("you should never see me")
This function leaves the wrong handler installed after it returns!
This is because
return bypasses the clean-up routines
we established with the desugaring of
the handler installed.
To fix this, we need to bind new versions of
that perform handler clean-up before exiting the loop:
(let ([$old (current-handler)]) (let* ([return (λ args (set-current-handler! $old) (apply return args))] [continue (λ () (set-current-handler! $old) (continue))] [break (λ () (set-current-handler! $old) (break))]) (call/ec (λ (ec) (set-current-handler! (λ (ex) (set-current-handler! $old) (ec (handler ex)))) (let ([rv body]) (set-current-handler! $old) rv)))))
But, if we want to allow a
expression, through an expanded
(try body handler finally),
things get more complicated.
finally code must run when
we leave the dynamic extent of the
It must run whether we return out of it, whether we break out of it, whether we continue out of it, or where we raise out of it.
But, what it must do after
depends on how we got into it:
- If we fall through by exiting the
trybody normally, it should continue after the
- If we return out, then after the
finallycode executes, it should immediately return the provided return value.
- If we break out, then it should run the
finallycode and jump out of the enclosing loop form.
- If we continue out, then it should run the
finallycode and jump to the top of the enclosing loop form.
- If we raise out, then it should run the
finallycode and re-raise the exception--unless the exception was handled, in which case it should fall through the bottom of
We can make all of this possible by creating a pointer to a thunk that should perform the post-finally action.
We need to capture and redirect all escaping continuations to pass through
finally by having them install their ordinary behavior in that thunk.
There's a further wrinkle in that if during the course of the exception handling,
we throw another exception, we still have to run through the
In other words, the exception handler has to install an exception handler.
Here's the desugaring to make it all happen:
(let* ([$val (void)] [$fin (λ () $val)] [$old (current-handler)]) (call/ec (λ (fin) (let* ([return (λ args (set! $fin (λ () (apply return args))) (fin))] [continue (λ () (set! $fin continue) (fin))] [break (λ () (set! $fin break) (fin))]) (call/ec (λ (ec) (set-current-handler! (λ (ex) ; if the handler ; throws an exception, ; re-throw it after ; the finally block: (set-current-handler! (λ (ex*) (set! $fin (λ () (throw ex*))) (ec #f))) (ec (let ([rv (handler ex)]) (set! $fin (λ () rv)))))) (let ([rv body]) (set! $fin (λ () rv)) (fin))))))) (set-current-handler! $old) (set! $val finally) ($fin)))
We also need to consider a
try form without an exception handler,
(try body finally).
Fortunately, all it has to do is re-raise the exception:
(let* ([$val (void)] [$fin (λ () $val)] [$old (current-handler)]) (call/ec (λ (fin) (let* ([return (λ args (set! $fin (λ () (apply return args))) (fin))] [continue (λ () (set! $fin continue) (fin))] [break (λ () (set! $fin break) (fin))]) (call/ec (λ (ec) (set-current-handler! (λ (ex) ; re-throw after finally: (set! $fin (λ () (throw ex))) (fin))) (let ([rv body]) (set! $fin (λ () rv)) (fin))))))) (set-current-handler! $old) (set! $val finally) ($fin)))
Compared to all the excitement above,
throw desugars with a wimper:
(define (throw ex) ((current-handler) ex))
Macro-expanders for all of the above are available
- I learned everything I know about compiling exceptions from Appel's Compiling with Continuations.
- My post on programming with continuations.
- Reader Travis Cardwell pointed me to the this excellent resource by Graham Hutton and Joel Wright: Calculating an Exception Machine [video].