Implementing async-await syntax using delimited continuations

One very popular monad (it is very much used outside the functional programming community) is the concept of promise. A promise is a value that you do not yet have, but that you want to manipulate. For instance, the javascript fetch function returns promises which you manipulate through the .then method:

const resp_promise = fetch("http://example.org/");
resp_promise.then(resp => {
    // Something ...
    // ...
})

As any web developper knows, using .then for managing sequential promises make for very ugly code:

const resp_promise = fetch("http://example.org/");
resp_promise.then(resp => {
    // Something ...
    // ...
    something.then(value => {
        // ...
        something_else.then(x => {
            //...
        })
    })
})

Javascript's solution to this problem is async and await. Using await on a promise will make the program look as if it is waiting for the result and async marks a function in which you would like to use await. It turns out that this piece of syntactic sugar is the same as the more general do notation in Haskell. Because the await keyword is familiar to many people, I will reuse it as a bind operator in the rest of the article. Because the await keyword essentially puts the delimited continuation from a point to the end of the async function into the .then, we can recreate the same behaviour by manually capturing this said delimited continuation.

Before we dive into the technical details of implementing async / await syntax, let me first explain what continuations are. The concept of a continuation captures the idea of "the rest of the program" from a certain point. Let's say an interpreter is evaluating the following expression and has just finished calculating the b*b - 4 * a * c sub expression.

(-b + sqrt(b*b - 4 * a * c))/(2*a)

The state of the interpreter holds the computed value (the results of evaluating b*b - 4 * a * c ) and what to do with it after. That information is the continuation. Thinking about continuations is useful for writing compilers, but it is also useful in other contexts. For instance, there is a certain program transformation (called Continuation-Passing-Style conversion) where every return keyword is eliminated and where every function call takes a new parameter, its continuation. For instance, let's CPS-convert the fib function.

function fib(n) {
    if (n <= 1) {
        return n
    } else {
        return fib(n - 1) + fib(n-2);
    }
}

console.log(fib(5))

5

It becomes the following:

function fib_cps(n, ret) {
    if (n <= 1) {
        ret(n);
    } else {
        fib_cps(n - 1, r1 => {
            fib_cps(n - 2, r2 => {
                ret(r1 + r2);
            })
        })
    }
}

fib_cps(5, res => {
    console.log(res);
})

5

Notice that instead of using return, we call a function that is explicitely passed as a parameter to fib_cps. Moreover, each time we call a function, we must act as if it will never return (it will not) and pass a handler (a continuation) that contains the rest of the computation. Notice that in the above code, after having computed the results for and , the results is passed to the continuation of the main call which is ret.

While this presentation is quite annoying to write, it lets us add exceptions, generators and other useful fancy control operators into languages that only support passing functions around.

The way call/cc works is that it gives as an argument to the thunk the function capturing the continuation exiting the block. Let's see how it works in scheme.

(define value
  (call/cc (lambda (ret)
             (display "one\n")
             (display "two\n")
             (ret 12345)
             (display "tree\n")
             (display "four\n"))))

(format #t "value is ~a\n" value)

one
two
value is 12345

Using this primitive, it is possible to do pretty much everything that was doable in CPS, but without having to actually write CPS code (and endure a thousand levels of nesting).

Delimited continuations are continuations that end with a value, their reification in functions are more natural because they are reified into functions that return something. Because those continuations don't capture the entire execution of the program, they play well with each other and with other constructs. Let's see them in action through the call-with-prompt and abort-to-prompt scheme operators.

In Guile Scheme, delimited continuations are created through two procedures.

call-with-prompt

You use it together with a special value (a tag) to delimit the end of the continuation you want to take.

abort-to-prompt

You use it together with the tag to define the location at which continuation will start.

(define tag (make-prompt-tag))

(call-with-prompt tag
  (lambda ()
    (let ((x 12345))
      ;; ...
      (let ((y (+ x (abort-to-prompt tag))))
        ;; ...
        y)))
  (lambda (kont)
    ;; ...
    ))

The first argument of call-with-prompt (the tag) is necessary for the abort-to-prompt call to be able to specify which continuation to open in situations in which multiple call-with-prompt are nested. The second argument is a zero argument function (thunk) which will delimit the end of the captured continuation. When the captured delimited continuation is called, execution will flow from the abort-to-prompt call to the end of this thunk. The third argument is the handler (kind of like try / catch) that will be called with the created continuation when abort-to-prompt is called. To better understand how it works, here is an example:

(define tag (make-prompt-tag))
(define cont
  (call-with-prompt tag
    (lambda ()
      (display "hello!\n")
      (let ((x (abort-to-prompt tag "some-value")))
        (+ 5 x)))
    (lambda (k val)
      (format #t "got value: ~s\n" val)
      k)))

(display (cont 1)) (newline)
(display (cont 3)) (newline)

Here is the output of the code:

hello!
got value: "some-value"
6
8

At first glance, we can see that, contrary to continuations captured by call/cc(which act kind of like value-carrying goto s), these delimited continuations return something. Another difference is that in call/cc, the k parameter captures the continuation starting from the call/cc call itself, whereas in call-with-prompt it captures the continuation starting from the innermost abort-to-prompt call inside the thunk.

Now that we understand better the concept of continuation, let's use it to analyze what the await keyword does.

One familiar with promises will know that writing this

async function do_something() {

    // Some code before the await

    const x = await returns_promise();

    // Some code after the await

    return y;
}

is equivalent to writing that:

function do_something() {
    // Some code before the await

    returns_promise().then(x => {

        // Some code after the await

        return y;
    })
}

The part that is put in the .then (the callback) is actually the continuation starting from the await and ending when the async function ends. If we have some kind of .then operator (called >>= or bind in Haskell), each time we await an effectful value, we can capture the current delimited continuation (from the await to the async) and use it as a handler for the value through our .then function.

Let's use this technique to implement nondeterministic computation.

One way of modeling nondeterministic computation is through lists. Each time we want to say "this value contains a superposition of many Ints", we will say [Int]. When we want to model a nondeterministic computation on Ints (let's say, into strings), we use Int -> [String]. we combine those two values through first applying the function to each possible value (getting a [[String]]), then by flattening the lists together into a [String]. When implemented in Scheme, it looks like this:

(define (.then l func)
  (apply append (map func l)))

(define (pure x)
  (list x))

Actually implementing the syntax is slightly more tricky.

(define prompt-tag (make-prompt-tag))

;; Awaiting a value (choosing a value among nondeterministic choices)
;; is simple, just abort to the nearest handler and give the list.
(define (await mval)
  (abort-to-prompt prompt-tag
                   mval))

;; When the continuation is to be threaded using nondeterministic
;; value (a list of things), we use .then on the continuation while
;; making sure we re-delimit the end of the continuation using another
;; async block.
(define (async thunk)
  (call-with-prompt prompt-tag
    thunk
    (lambda (cont value)
      (.then value (lambda (v)
                   (async
                    (lambda ()
                      (cont v))))))))

Finally we can test our code on a toy example. Here, a sequential nondeterminist choice of number, letter and fruit should yield every combination of number, letter and fruit.

(use-modules (ice-9 pretty-print))

(pretty-print
 (async
  (lambda ()
    (let ((num (await '(1 2 3)))
          (letter (await '(a b c)))
          (fruit (await '("apple" "orange" "banana"))))
      (pure (list num letter fruit))))))

((1 a "apple")
 (1 a "orange")
 (1 a "banana")
 (1 b "apple")
 (1 b "orange")
 (1 b "banana")
 (1 c "apple")
 (1 c "orange")
 (1 c "banana")
 (2 a "apple")
 (2 a "orange")
 (2 a "banana")
 (2 b "apple")
 (2 b "orange")
 (2 b "banana")
 (2 c "apple")
 (2 c "orange")
 (2 c "banana")
 (3 a "apple")
 (3 a "orange")
 (3 a "banana")
 (3 b "apple")
 (3 b "orange")
 (3 b "banana")
 (3 c "apple")
 (3 c "orange")
 (3 c "banana"))

It works! Note that for the types to work, the output of every async thunk must be wrapped into a monadic value. You do not have to do this when using Javascript promises simply because it is done automatically. Note that you can use the exact same code for every monad, just change the definition of .then and pure. You can use this code to ease the implementation of monadic parser combinators, promises (which is just, as we have seen, continuation passing style) and other effects.