Implementing Exceptions With Continuations Racket Lisp

Jan 30th, 2019 - written by Kimserey with .

Last week a colleague of mine introduced me to the concept of continuation in Racket (the best of Scheme and Lisp - at least that is what racket-lang.org states). I knew about the existence of Lisp but I never really paid attention to what it provided as language features. So I took the bite and started to read the post shared to me on continuations, written by Matt Might and oh boy… was I confused. Everything about the code confused me, the notation, the syntax, and of course the flow of the program itself. What I understood was that this piece was implementing Exceptions by using continuations which was enough to make me want to understand it.

So today, what I am sharing with you is my understanding of this implementation of Exceptions that Matt Might added at the end of his post, using Racket, coming from someone who had zero knowledge in Lisp and Racket. This post isn’t a guide on Racket, but rather an attempt to understand Matt’s post without prior knowledge in Racket.

Notation
Defining Syntax
Continuation
Implementing Exceptions

Here is the implementation of Exceptions in Racket language that we will try to understand:

; current-continuation: -> continuation
(define (current-continuation) (let/cc k k))

; exception-stack: list[continuation]
(define exception-stack '())

; throw: exception -> unit
(define (throw exception-value)
  (define cc (car exception-stack))
  (cc (list 'exception exception-value)))

; (try EXP ... catch catch-procedure)
; Runs EXP ... and invokes catch-procedure with
; the value passed to throw.
(define-syntax try
  (syntax-rules (catch)
    [(_ EXP ... catch catch-procedure)
     (let ([cc (current-continuation)])
       (cond
         [(procedure? cc) (dynamic-wind
                           (lambda () (set! exception-stack (cons cc exception-stack)))
                           (lambda () EXP ...)
                           (lambda () (set! exception-stack (cdr exception-stack))))]
         [(pair? cc) (catch-procedure (cadr cc))]))]))


; Example:
(try (try (throw 'foo)
          catch
          (lambda (exn)
            (display "got inner exception: ")
            (display exn)
            (newline)
            (throw 'bar)))
     catch
     (lambda (exn)
       (display "got outer exception: ")
       (display exn)
       (newline)))

Source: Examples in Continuations by example: Exceptions, time-traveling search, generators, threads, and coroutines - Matt Might

Notation

As someone who never seen Lisp or Racket before, it is hard to understand the notation as the term used aren’t familiar terms with more widespread/general languages. Therefore in this first part we will go through the notation and explain some aspects of it.

S-expression

The first apparent difference with other languages is the extensive usage of parentheses. This notation is named S-expression for symbolic expression. Everything in parenthesis represents an expression which is executed.

For example when I do (hello), if hello is a procedure, it will be executed. If hello accepts arguments, we can call it with the arguments with (hello 1 2 3).

Also another important point is that () and [] are equivalent. They can be used interchangeably to ease reading.

`define` and `let`

The second keyword used is define. In the code that we’re trying to understand, we use define in two ways.

The first one:

; (define id expr)
(define my-value 1)

Binds the result of the expression body to the id my-value.

While the second usage:

; (define (head args) body ...+)
(define (f) 1)

Binds a procedure to the id f. Which can then be executed with (f).

We also see let being used, which creates a local binding while executing the content of the body.

; (let ([id val-expr] ...) body ...+)
(let ([x 1] [y 2])
  (printf "~a ~a\n" x y))

x and y are initiated with a default value 1 and 2 specified in [] and the body is then evaluated with the value of x and y.

List and operations

list procedure is used to create a list with initial elements:

> (list 1 2 3)
'(1 2 3)

We can also use quote or ' to create a list:

> '(1 2 3)
'(1 2 3)

We can then add an element an existing list with cons:

> (const 10 '(1 2 3))
'(10 1 2 3)

With a list we have few operations procedures available:

we can get the first element of a list with car,
we can get the rest of the list excluding first element with cdr,
we can get the second element with cadr (which is basically combining (cdr (car ...))).

> (car '(1 2 3))
1

> (cdr '(1 2 3))
'(2 3)

> (cadr '(1 2 3))
2

`quote` or `'`

We just saw that quotes could be used to create list. What actually happens is that a quote creates a datum of a single value or a list of datum for an S-expression where a datum is a literal version of the value or s-expression.

> 'hello
'hello

> '(+ 1 1)
'(+ 1 1)

Conditions

Another syntax that we see is cond for condition/clause.

; (cond cond-clause ...)
; cond-clause = [test-expr then-body ...+]
;  | [else then-body ...+]
;  | [test-expr => proc-expr]
;  | [test-expr]

; procedure
(define (do-something v)
   (cond
     [(procedure? v) (v)]
     [(pair? v) (displayln (cdr v))]))

; results in "print from first clause" as the lambda provided
; is a procedure therefore match the first clause
(do-something (lambda () (displayln "Print from first clause")))

; results in "(2 3 4 5)" printed
(do-something '(1 2 3 4 5))

We start by definining a procedure do-something which takes a single argument v. We then create a cond-clause with two clauses:

(cond
  [(procedure? v) (v)]
  [(pair? v) (displayln (cdr v))])

Both clauses match on the datatype of v, the first one check if v is a procedure, and executes (v). The second one check if v is a pair.

Now if we call do-something with a procedure, the procedure will be executed as it matches the first clause:

> (do-something (lambda () (displayln "Print from first clause")))
print from first clause

Whereas if we passed a list of values, we would have the second clause matched:

> (do-something '(1 2 3 4 5))
(2 3 4 5)

The second clause matching on pairs considers '(1 2 3 4 5) as a pair and executes displayln (cdr v) as outcome.

If you are thinking why would a list ‘(1 2 3) be considered as a pair?. The answer is that a pair is whatever list where cdr returns a value. Therefore '() or '(1) aren’t pairs while '(1 2) and '(1 2 3) are pairs where the car returns 1 and repectively cdr returns '(2) and '(2 3).

`dynamic-wind`

Another important syntax used in the example is dynamic-wind. dynamic-wind applies a pre-thunk and post-thunk operations and returns the value of the value-thunk.

; (dynamic-wind
;    pre-thunk
;    value-thunk
;    post-thunk)
(dynamic-wind
 (lambda () (displayln "pre"))
 (lambda () (displayln "Hello world"))
 (lambda () (displayln "post")))

Executing this construct will yield:

pre
Hello world
post

The pre-thunk is invoked, then the value-thunk and lastly the post-thunk.

Now what is interesting for dynamic-wind is that pre and post are always executed even when we jump stack with continuations.

In this example of Exceptions implementation, dynamic-wind is used to push an element to a list on pre, and pop out an element from the same list on post using set! which sets a previously defined value.

Defining Syntax

`define-syntax`

While define is used to define a binding of a value or procedure, define-syntax is used to define a syntax transformer. A syntax transformer expands the id to the expression provided. For example, we could do the following:

; (define-syntax id expr)
(define-syntax say-hello (lambda (stx) (syntax "Hello")))

This creates a binding to a say-hello transformer. syntax can also be written with #' therefore say-hello can be written:

(define-syntax (say-hello stx) #'"Hello")

Then when we use (say-hello), we get "Hello".

`syntax-rules`

define-syntax can be used with syntax-rules to transform syntax based on pattern matching rules. For example here we create a syntax hello with rules allowing the literal keyword in:

; (define-syntax id
;  (syntax-rules (literal-id ...)
;    [pattern template]
;    ...))
(define-syntax hello
  (syntax-rules (in)
    [(_ name in time)
     (cond
       [ (equal? "morning" time) (printf "Good Morning, ~a\n" name)]
       [ (equal? "evening" time) (printf "Good Evening, ~a\n" name)]
       [ else (printf "Time not recognized\n")])]
    [(_ name) (printf "Hello ~a\n" name)]
    [(_ EXP ...) (printf "~a\n" '(EXP ...))]))

The first pattern matches on (_ name in time) and checks if time is either morning or evening resulting in the propert print of Good Morning or Good Evening.

> (hello "Kimserey" in "morning")
Good Morning, Kimserey

> (hello "Kimserey" in "evening")
Good Evening, Kimserey

> (hello "Kim" in "")
Time not recognized

The second pattern (_ name) matches a single name.

> (hello "Kim")
Hello Kim

And the last pattern ellipsis (_ EXP ...) matching the whole expression.

> (hello "a" 1 2 3 "b")
(a 1 2 3 b)

Continuation

The last important syntax used in the code is let/cc. let/cc creates a binding by providing a continuation as argument. /cc is a short form for with current-continutation so let/cc means let binding with current continuation.

> (+ 1 (+ 2 (let/cc k (+ 10 1))))
14

k being the continuation, if we invoke it, the let binding will be short circuited.

> (+ 1 (+ 2 (let/cc k (k 5) (+ 10 1))))
8

Continuations are the main topic of Matt’s post, it is the construct that allows implementation of Exceptions in his example.

A continuation captures the rest of the computation and makes it available as a procedure. (This is greatly simplified as more than the rest of the execution is captured and I can’t proclaim that I understand it fully - but seeing it as a procedure was the best interpretation which allowed me to understand the implementation so I’ll go with it).

So here (+ 1 (+ 2 (let/cc k (+ 10 1)))), k is not used therefore the let binding results in 11 then gets +2 and +1 resulting in 14.

In the second case, (+ 1 (+ 2 (let/cc k (k 5) (+ 10 1)))), k is called with 5 which then short circuits the normal result (+ 10 1) and result in the let binding being equal to 5 which then results in 8.

The continuation changed the control flow by jumping back to where it was defined.

The other important aspect is that the continuation can also be called from outside the let binding.

(define (current-continuation) (let/cc k k))

(define (call) #f)

(let ([cc (current-continuation)])
  (cond
    [(procedure? cc) (set! call cc)]
    [(string? cc) (displayln cc)]))

(call "hello")

Here we define a call procedure initialized with false. We then define a let which sets the current continuation to the beginning of let as a initial value for cc as argument.

We then check with a cond-clause whether it was entered with a procedure as cc, and if it is, we set call to the continuation.

If cc is a string, we know that call was invoked with a string as argument, therefore we display the content of cc.

This allows us to use call anywhere and therefore rewind & replay the content of let.

Implementing Exceptions

Looking back at the Exception implementation:

; current-continuation: -> continuation
(define (current-continuation) (let/cc k k))

; exception-stack: list[continuation]
(define exception-stack '())

; throw: exception -> unit
(define (throw exception-value)
  (define cc (car exception-stack))
  (cc (list 'exception exception-value)))

; (try EXP ... catch catch-procedure)
; Runs EXP ... and invokes catch-procedure with
; the value passed to throw.
(define-syntax try
  (syntax-rules (catch)
    [(_ EXP ... catch catch-procedure)
     (let ([cc (current-continuation)])
       (cond
         [(procedure? cc) (dynamic-wind
                           (lambda () (set! exception-stack (cons cc exception-stack)))
                           (lambda () EXP ...)
                           (lambda () (set! exception-stack (cdr exception-stack))))]
         [(pair? cc) (catch-procedure (cadr cc))]))]))

We now know all the syntax used in this code and we also know the concept behind the flow. The two main aspects of Racket allowing us to implement Exceptions are:

the ability to define new syntax,
the ability to control the execution flow of our program with continuations.

Going line by line, we start by defining a procedure which will capture the current continuation when called:

(define (current-continuation) (let/cc k k))

Then we define an empty list which will be used as a exception handling stack as try/catch constructs can be embedded, we can try and within the try, try another time, etc…

(define exception-stack '())

Our exception handlers will be current continuations from the beginning of the try/catch. We will see how we set them later.

Then we define a throw procedure which takes an exception as argument:

(define (throw exception-value)
  (define cc (car exception-stack))
  (cc (list 'exception exception-value)))

Our throw takes the first continuation from the stack with car and calls it passing in a pair of 'exception, quoted exception literal, and the exception-value.

Lastly, we define a syntax try with a literal catch:

(define-syntax try
  (syntax-rules (catch)
    [(_ EXP ... catch catch-procedure)
     (let ([cc (current-continuation)])
       (cond
         [(procedure? cc) (dynamic-wind
                           (lambda () (set! exception-stack (cons cc exception-stack)))
                           (lambda () EXP ...)
                           (lambda () (set! exception-stack (cdr exception-stack))))]
         [(pair? cc) (catch-procedure (cadr cc))]))]))

The pattern (_ EXP ... catch catch-procedure) will match a try try-body catch catch-body construct where EXP ... will by the try-body and catch-procedure will be the catch-body.

The expression for the syntax-rule is a let which instantiates a current continuation as argument and checks with a condition whether the argument cc is a procedure or a pair similarly as we did in our hello example. (This is actually the idiom for continuation explained by Matt Might in his post)

(let ([cc (current-continuation)])
       (cond
         [(procedure? cc) (dynamic-wind
                           (lambda () (set! exception-stack (cons cc exception-stack)))
                           (lambda () EXP ...)
                           (lambda () (set! exception-stack (cdr exception-stack))))]
         [(pair? cc) (catch-procedure (cadr cc))]))

When we enter the condition, if cc is a procedure, we know that it is the first time the try/catch is invoked therefore we use dynamic-wind to add the continuation to the stack, then we return the body of the try with EXP .... Lastly if either the body is executed properly or we jumped out of the execution with a continuation, the unwinding removes the continuation from the stack.

On the other hand if cc is a pair, it means that the continuation was invoked from throw by passing in the (list 'exception exception-value) argument which we then take with cadr and in turn invoke the catch handler by doing (catch-procedure (cadr cc)).

This construct allows throw to short circuit the try execution and invoke catch instead.

When throw occurs as part of EXP ..., the continuation which was set during winding of dynamic-wind is called, the cond-clause is then re-evaluated with cc being a pair of exception with an exception value which then matches the second clause resulting in the call of the catch-procedure.

Example

The try syntax allows developers to write the following try/catch logic:

(try
 (try
  (throw 'foo)
  catch
  (lambda (exn)
    (display "got inner exception: ")
    (display exn)
    (newline)
    (throw 'bar)))
 catch
 (lambda (exn)
   (display "got outer exception: ")
   (display exn)
   (newline)))

; got inner exception: foo
; got outer exception: bar

The logic is executed as followed:

the outer try/catch continuation is pushed to the stack as part of the winding,
then the try expression body of the outer try/catch, containing the inner try/catch, is executed,
then the inner try/catch continuation is pushed to the stack as part of the winding,
then the inner try expression body is executed,
throw occurs in the body of the inner try, which calls the continuation stacked by the inner body,
unwinding of the inner body try/catch removes the continuation from the stack,
catch procedure of the inner try/catch is executed,
throw occurs in the catch of the inner body, which calls the continuation stacked by the outer body,
unwinding of the outer body try/catch removes the continuation from the stack,
catch procedure of the outer try/catch is executed.

The result is the following:

got inner exception: foo
got outer exception: bar

And that concludes today’s post!

Conclusion

Today we explored a blog post written by Matt Might on Continuations. The goal of this post was to explain how Exceptions could be implemented in a language supporting syntax definition and continuations. We started by looking at the syntax of Racket, explaining each aspect of the notation used in the example. We then moved on to see how we could define our own syntax, following with a brief example on how continuations worked. Finally we completed the post by looking at an implementation of Exceptions looking step by step at how the flow jumped when exceptions were raised. I hope you liked this post! See you on the next one!