Continuations

Continuations are procedures representing remaining steps in a computation:

void current_continuation(int result) {
 result += 8 ;
 result *= 3 ;
 (continuation of 3 * (f() + 8))(result) ;
}

When we say continuations are first class (or generally X is first class), we mean it is a first class value. This is the case for scheme.

Implementation is known as CPS (continuation passing style).

It satisfies constraint: No procedure is allowed to return to its caller ever.

When procedure is ready to return, it invokes current continuation (cc) callback on the return value.

Examples

Identity

function id(x) {
  return x;
}

rewritten in cps:

function id(x, cc) {
  cc(x);
}

or for returns:

function id(x, return) {
  return(x);
}

Factorial

function fact(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
}

cps:

function fact(n, cc) {
  if (n === 0) {
    cc(1)
  } else {
    fact(n - 1, t0 => cc(n * t0));
  }
}

Practical examples

  • Server side distributed computing. E.g. factorial:

    function choose(n,k,ret) {
    fact (n,   function (factn) {
    fact (n-k, function (factnk) {
    fact (k,   function (factk) {
    ret  (factn / (factnk * factk)) }) }) }) 
}

function fact(n,ret) {
    fetch ("./fact/" + n, function (res) {
        ret(eval(res))
    });
}

  • Exceptions: Add an extra “exception continuation”:

    function fact (n, return, throw) {...}

Utilities

call/cc / call-with-current-continuation

(define call/cc (f cc) (f (lambda (x k) (cc x)) cc))

Calls a procedure f, with current-continuation cc, when we invoke f, computation continues from cc.

function callcc (f,cc) { 
  f(function(x,k) { cc(x) },cc)
}

References

logo