8c6794b6.github.io

Introduction

Exploring delimited continuation in Common Lisp, in particular, shift and reset from Danvy and Filinski. There is cl-cont package, which supports shift/reset style continuation with rewriting expression inside with-call/cc macro. The implementation shown in this post is simple, short (less than 50 lines), and uses monadic functions to capture continuations.

Monad for Continuation

As Wadler mentioned in various papers, monads could be used to express continuations. Monads consists of type constructor M and following two operations:

unit :: a -> M a
(★)  :: M a -> (a -> M b) -> M b

It is possible to express concept of Monads in other programming languages than Haskell. Several implementation already exist, such as in Scheme and JavaScript, to name a few. In impure languages, there are not much needs for monad, since the problems solved by monads in purely functional language are solved with different techniques. Though, one of the programming techniques which could be solved with monad, and missing in most language is, expressing first class continuation.

One of the programming languages supporting first class continuation is Scheme. Scheme has call-with-current-continuation, which captures undelimited continuation as first class value. Some of the Scheme implementations also support delimited continuations. Delimited continuations are not in the Scheme language specifications so far, though it is possible to implement it with undelimited continuations.

Wrapping Expression Into CPS

In a programming language without builtin support for continuation, one need to express the computation in Continuation-Passing-Style (CPS) to capture the continuation, and that is where monad is used for. Firstly, defining a structure to represent continuation. The structure CONT has single field, a function taking the current continuation.

(defstruct (cont (:constructor make-cont (fn)))
  (fn #'values :type function))

(defun run-cont (c k)
  (funcall (cont-fn c) k))

Defining unit and (★) to make CONT as an instance of monad. In the code shown below, unit is renamed to returnc, and (★) is renamed to bindc.

(defun returnc (x)
  (make-cont (lambda (k)
               (funcall k x))))

(defun bindc (c f)
  (make-cont (lambda (k)
               (run-cont c (lambda (x)
                             (run-cont (funcall f x) k))))))

Definition of returnc makes CPS representation of x wrapped with CONT structure. bindc runs the continuation c, then pass the result to f, and runs the continuation returned by f with the current continuation k. Note that in bindc, current continuation k is not passed to c but to the returned value of f.

Some examples:

> (run-cont (returnc 'foo) #'values)
FOO
> (run-cont (bindc (returnc 21) (lambda (x) (returnc (* x 2)))) #'values)
42

Adding two syntax helper macros, letc* and progc. The macro letc* is similar to let*, but instead of binding result of pure expressions, letc* binds the variable to the argument passed to the continuation.

(defmacro letc* (bindings &body body)
  (if (null bindings)
      `(progn ,@body)
      (destructuring-bind (name c) (car bindings)
        `(bindc ,c (lambda (,name)
                     (letc* ,(cdr bindings) ,@body))))))

The second example shown above could be written with letc* as follows:

> (run-cont (letc* ((x (returnc 21)))
              (returnc (* x 2)))
            #'values)
42

progc is similar to letc*, but discards the variable, intended to be used in the codes where side effects of continuations are the main concern.

(defmacro progc (&body body)
  (if (null (cdr body))
      (car body)
      (let ((garg (gensym)))
        `(bindc ,(car body)
                (lambda (,garg)
                  (declare (ignore ,garg))
                  (progc ,@(cdr body)))))))

Shift And Reset

With monadic interfaces for continuation, shift and reset could be expressed as below. The function reset unwrap the CONT structure if the given argument is CONT, otherwise returns the given value itself.

(defun reset (k)
  (if (cont-p k)
      (run-cont k #'values)
      k))

The macro shift binds the current continuation to given var as a function defined with flet, and then invoke the expr. Inside expr, bounded continuation could be invoked as an ordinary function. In other words, shift captures the continuation from the captured place until the first appearance of enclosing reset.

(defmacro shift (var expr)
  (let ((gk (gensym))
        (garg (gensym)))
    `(make-cont (lambda (,gk)
                  (declare (function ,gk))
                  (flet ((,var (,garg)
                           (funcall ,gk ,garg)))
                    (declare (ignorable (function ,var)))
                    ,expr)))))

Evaluating some sample expressions with shift and reset. The resulting value of shift is a CONT:

> (shift k (k 2))
#S(CONT :FN #<FUNCTION (LAMBDA (#:G656)) {1004B9A55B}>)

To perform the computation in CONT, one can apply reset:

> (reset (shift k (k 2))
2

The resulting CONT object from shift could be passed to bindc, as those made from returnc:

> (reset (letc* ((x (shift k (k 2))))
           (returnc (+ x 3))))
5

When the expression in shift returns without calling captured continuation, the whole computation will escape immediately. Instead of the sum of x and y or an error from +, following expression evaluates as symbol FOO:

> (reset (letc* ((x (returnc 100))
                 (y (shift k 'foo)))
           (returnc (+ x y))))
FOO

Since captured continuation is an ordinary function, it could be invoked multiple times. In the following expression, the captured computation with shift could be viewed as (lambda (x) (+ x 3)). The captured continuation is applied twice, which results in (+ (+ 2 3) 3):

> (reset (letc* ((x (shift k (k (k 2)))))
           (returnc (+ x 3))))
8

Inside the expression of shift, further computation could be done with returned value from captured computation. Following expression applies captured continuation twice as in previous example, then multiplies by 2:

> (reset (letc* ((x (shift k (* 2 (k (k 2))))))
           (returnc (+ x 3))))
16

In the implementation of shift and reset shown here, continuations are captured with monad, hence some wrapping with returnc and unwrapping with letc* are required. In an implementation which has builtin support of shift and reset (e.g.: Racket), the last example could be written as:

> (reset (+ (shift k (* 2 (k (k 2)))) 3))
16

Example: Nondeterminism

One common use of continuation is for nondeterministic programming. Showing an implementation of choice from the Danvy and Filinski's paper, and its use with function triple. The problem we have is to find out all triples of distinct positive integers i, j, and k less than or equal to a given integer n that sums to a given integer s:

(defun fail ()
  (shift k 'no))

(defun choice (n)
  (shift k (loop for i from 1 to n do (k i) finally 'no)))

(defun triple (n s)
  (letc* ((i (choice n))
          (j (choice (- i 1)))
          (k (choice (- j 1))))
    (if (= s (+ i j k))
        (returnc (list i j k))
        (fail))))

To print the results of triple, one may write as follows:

> (reset (letc* (ijk (triple 9 15)))
           (returnc (print ijk))))
(6 5 4)
(7 5 3)
(7 6 2)
(8 4 3)
(8 5 2)
(8 6 1)
(9 4 2)
(9 5 1)
NIL

Note that unlike the original example in the paper, the version of shift in this post returns a value of CONT structure. The expression (triple 9 15) is evaluated as CONT structure, not the answer values returned by (returnc (list i j k)). The answers need to be unwrapped with letc* or bindc to print with print function.

Example: Coroutine

Another famous problem solved with continuation is, so-called the same-fringe problem. Two binary trees have the same fringe if they have exactly the same leaves reading from left to right. The problem is to decide whether two binary trees have the same fringe. Basically, we want to return from the tree traversal as soon as we detect that the trees are different.

(defun donep (x) (eq 'done x))

(defun nextp (x) (not (donep x)))

(defun next (n k) (lambda () (values n k)))

(defun walkerc (tree)
  (cond
    ((null tree) (returnc 'done))
    ((atom tree) (shift k (next tree #'k)))
    (t (progc
         (walkerc (car tree))
         (walkerc (cdr tree))))))

The function walkerc takes a tree, returns a CONT value. Each element of the tree is converted as a closure with the function next. The closure returns two values: the element and the captured continuation. The resulting CONT could be viewed as a coroutine object, which traverses the tree from right to left order.

With walkerc, function same-fringe could be written as below:

(defun same-fringe (t1 t2)
  (labels ((rec (r1 r2)
             (if (nextp r1)
                 (and (nextp r2)
                      (multiple-value-bind (n1 k1) (funcall r1)
                        (multiple-value-bind (n2 k2) (funcall r2)
                          (and (eql n1 n2)
                               (rec (funcall k1 nil)
                                    (funcall k2 nil))))))
                 (donep r2))))
    (rec (reset (walkerc t1))
         (reset (walkerc t2)))))

Sample runs:

> (same-fringe '((1) (2 (3 (4) 5))) '((1 (2) (3 4) 5)))
T
> (same-fringe '((1) (2 (3 (4) 5))) '((1 (2) (4) 5)))
NIL

Some thoughts

Both non-deterministic example and coroutine example could be directly written in continuation passing style (CPS), which shall be slightly efficient since direct CPS does not require to make the cont structure.

Te implementation shown in this post is similar to the one done by Matthew D Swank, written in 2006.

Delimited continuations with monadic functions in Common Lisp