Continuations

Concept

JavaScript has first-class functions — closures. First-class means that the functions in JavaScript are treated the same way as all the other objects, for example they can be assigned to a variable or passed as an argument to another function.

Continuations are first-class control structures. They represent a point in program’s execution and being first-class means they can — just like the JavaScript closures — be directly accessed by the programming language.

Call-with-current-continuation

In Scheme continuations are captured using the call-with-current-continuation (callcc) function.

This function takes a callback and invokes it passing as an argument the continuation object (k variable below). That continuation represents the point of program execution when the callcc was executed.

continuation = 0;

test = fn() {
  display(begin);

  i = 0;

  callcc(fn(k) {
    continuation <- k
  });

  i <- i + 1;

  display(end);

  i
}

Executing the test function saves the current continuation in a global variable and returns the current value of i that is 1.

test()

Continuation object can be invoked just like a function resuming execution from the point where callcc was originally called. In this case the execution will continue from the middle of the test function, incrementing the counter, displaying the message and returning the new value.

continuation()

Continuation can be called many times each time continuing execution from the same point.

Control flow structures

The simplest control flow structures — conditionals (if/else) can be implemented using functions only. Loops — with tail recursive function calls.

Continuations can be used to emulate more complex (structured non-local) control flow constructs.

Return

This simple programming language does not have a return statement, that is, a way of stopping the function execution earlier.

As the fragment of code below demonstrates the function returns the value of the last expression when it is called (in this case 3). Function f is called with one argument that is assigned to return — an identity function. That does not have any effect on result of this function call.

f = fn(return) {
  a = 1;
  return(2);
  3
};

f(fn(x) x) * 2

A different effect is achieved by using callcc to invoke the function f. Now return holds the continuation object that when invoked inside the function f immediately aborts the execution and returns a value of 2 at the same place where callcc was originally called.

f = fn(return) {
  a = 1;
  return(2);
  3
};

callcc(f) * 2

Generators

Generators are special kind of functions that maintain state between invocations. They are used to produce infinite streams of values.

In the code below each next() executes only enough code to reach the closest yield.

next = generator(fn(yield) {

  yield(1);

  display(inside);

  yield(2)
});

print(next());

display(outside);

print(next())

The following generator enumerates numbers from the Fibonacci sequence. This generator never finishes. Each number is computed on demand when the next() function is called.

next = generator(fn(yield) {
  i = 1;
  j = 1;
  step = fn() {
    current = j;
    j <- i;
    i <- i + current;
    yield(current);
    step()
  };
  step()
});

print(next());
print(next());
print(next());
print(next());
print(next());
print(next())

The generator function uses a symmetric protocol and is implemented with two calls to callcc.

generator = fn(func) {
  continuation = 0;
  resume = fn() {
    func(yield)
  };
  yield = fn(value) {
    callcc(fn(k) {
      resume <- k;
      continuation(value)
    })
  };
  fn() {
    callcc(fn(k) {
      continuation <- k;
      resume()
    })
  }
}

One variable (continuation) remembers when next() was called and jumps to the last yield. The second one (resume) initially invokes the function func but later it remembers the position of the last yield and jumps back to the place where next() was invoked.

Coroutines

A coroutine is a control structure where flow control is cooperatively passed between two different routines without returning.

The code below uses callcc to invoke two functions (producer and consumer) repeatedly.

producer = fn(continuation) {
  display(produce_item);
  producer(callcc(continuation))
};

consumer = fn(continuation) {
  display(consume_item);
  consumer(callcc(continuation))
};

producer(consumer)

The execution of this script is aborted after several iterations as it never completes.

Exceptions

Another example of non-local control flow structure that can be emulated using continuation are exceptions.

The code below uses two functions — try and catch. The function passed to try is invoked with one parameter — the throw function. That function stops execution and immediately calls the handler specified as an argument to catch. If the throw function is never called the last value from the try clause is returned instead.

try(fn(throw) {
  a = 1;
  throw(2);
  b = 3;
  a
}) catch fn(exception) {
  4 + exception
}

The implementation relies on two functions:

1. try returns either a pair of false and an exception or true and the clause’s result,
2. catch executes handler only when the exception has been thrown.

The example above also relies on a syntactic feature of this programming language — a catch b is equivalent to catch(a, b).

try = fn(clause) {
  callcc(fn(continuation) {
    throw = fn(exception) {
      continuation(pair(false, exception))
    };
    pair(true, clause(throw))
  })
};

catch = fn(result, handler) {
  if (first(result)) then
    second(result)
  else
    handler(second(result))
}

Amb operator

The amb operator described by John McCarthy is a control structure that works in a similar way to backtracking used in Prolog.

When amb is given a list of values to try it initially returns the first element. When amb options run out (the list passed as an argument is empty — nil) it uses backtracking to go back to previous invocation of amb and tries a different option.

The code below finds the values of x and y that multiplied give 8.

x = 0; y = 0;

x <- amb(1 : 2 : 3 : nil);
y <- amb(4 : 5 : 6 : nil);

if (x * y == 8) then
  print(x, y)
else
  amb(nil)

The implementation of amb remembers current execution using points linked list. When the choices run out it takes the most recent backtracking point (a continuation) and restores execution from there, trying the next option.

points = nil;

amb = fn(choices) {
  callcc(fn(return) {
    if (choices == nil) then {
      last = first(points);
      points <- second(points);
      last()
    } else 0;
    callcc(fn(cc) {
      points <- pair(cc, points);
      return(first(choices))
    });
    amb(second(choices))
  })
}

Yin-yang puzzle

To test continuations in this interpreter a yin-yang puzzle is implemented below.

{ fn(yin)
  { fn(yang)
    yin(yang)
  }({ fn(cc) { display(@); cc } }(callcc(fn(c) c)))
}({ fn(cc) { display(*); cc } }(callcc(fn(c) c)))

The execution of this script is aborted after several iterations as it never completes.

Script internals

This article utilizes a small scripting language that supports capturing and resuming continuations.

The language has only three constructs and one keyword (fn):

1. identifiers that constitute leafs in the syntax tree,
2. function calls,
3. function definitions that create closures.

Identifiers represent named bindings (variables), numbers and operators.

Function calls have two forms, one which uses parentheses:

print(12, 13)

And the second one that looks like an operator application:

3 * 2

But these two forms are fully interchangeable so the first invocation is equivalent to:

12 print 13

That form is used to build extensions that look like built-in constructs (for example conditionals or the exception handling) and small domain-specific languages.

Operators can also be called like a named function with two parameters:

*(3, 2)

That form is used to create partially applied functions that use operators:

mul3 = *(3);
mul3(2)

Symbols are also valid identifiers so multiplication operator can also be assigned to a variable:

mul = * ;
3 mul 2

Assignment (=) and semicolon (;) are also operators although their implementation is provided by the runtime.

Expressions can be grouped using braces:

{1 + 2} * 4

There are no blocks and each expression has a value. For example the semicolon operator (;) evaluates both left and right expressions and returns the value of the latter:

a = { 1; 2; 3 };
print(a)

Functions

Each function is a closure and it has direct access to all variables in scope in which it has been created.

counter = fn() {
  number = 0;
  fn() {
    number <- number + 1
  }
};

d = counter();
print(d());
print(d());
print(d())

The binding operator (=) attaches a value to the name in the current scope. A name can be bound to only once in the same scope but a different operator — assignment (<-) can be used to update the value.

Lists

Functions alone can be used to build pairs of values:

pair = fn(x, y) fn(choice) choice(x, y);

first = fn(list) list(fn(x, _) x);
second = fn(list) list(fn(_, y) y);

: = pair;

nil = fn(x) x

And pairs can be used to construct more complex structures — like linked lists.

The code below constructs a four element list and retrieves the third element:

list = 1 : 2 : 3 : 4;

third = first(second(second(list)))

Conditionals

Pairs can be used to build the conditional instruction:

true = fn(x, _) x;
false = fn(_, y) y;

if = fn(p) p;
then = fn(p, a) pair(p, a);
else = fn(cond, b) first(cond)(second(cond), b)()

true and false are functions returning the first or the second parameter.

if (2 > 3) then { fn() print(1) } else { fn() print(0) }

This notation uses an alternative form of the function call — then and else are invoked using the infix notation.

Because this language is an applicative-order language the arguments are evaluated immidiately before a function is executed. In case of conditionals it would evaluate both the consequent (then clause) and the alternative (else clause) ignoring the value of the condition. To prevent that both clauses are wrapped in functions.

The same effect can be achieved using the @lazy annotation on function arguments. This annotation wraps argument values in functions preventing their immediate execution.

true = fn(x, _) x;
false = fn(_, y) y;

if = fn(p) p;
then = fn(p, @lazy a) pair(p, a);
else = fn(cond, @lazy b) first(cond)(second(cond), b)()

The code below behaves exactly like the one above but looks more concise:

if (2 > 3) then print(1) else print(0)

:: = fn(first, @lazy rest) pair(first, rest);

head = first;
tail = fn(seq) second(seq)();

numbers = fn(start) start :: numbers(start + 1);

filter = fn(seq, predicate) {
  first = head(seq);
  rest = fn() tail(seq) filter predicate;
  if (predicate(first)) then first : rest else rest()
};

primes = fn(seq) {
  notDivBy = fn(seq, num) seq filter fn(x) x % num != 0;
  first = head(seq);
  rest = tail(seq) notDivBy first;
  first :: primes(rest)
};

. = fn(value, func) func(value);

printN = fn(n, seq) {
  if (n > 0) then {
    elem = head(seq);
    print(elem);
    elem + printN(n - 1, tail(seq))
  } else 0
};

2.numbers().primes().printN(8)

function Identifier(name) {
    this.name = name;
}

function FunctionDefinition(args, body) {
    this.args = args;
    this.body = body;
}

function FunctionCall(func, args) {
    this.func = func;
    this.args = args;
}

Identifier.prototype.toString = function() {
    return (this.annotations || []).concat(this.name).join(' ');
};

FunctionDefinition.prototype.toString = function() {
    return 'fn(' + this.args.join(', ') + ') ' + this.body;
};

FunctionCall.prototype.toString = function() {
    if (this.args.length === 2) {
        return '{' + this.args[0] + '} ' + this.func + ' {' + this.args[1] + '}';
    }
    return this.func + '(' + this.args.join(', ') + ')';
};

function lexer(text) {
    var REAL = '[0-9]+\\.[0-9]+';
    var INTEGER = '[0-9]+';
    var IDENTIFIER = '[@A-Za-z_][A-Za-z0-9_]*';
    var OPERATOR = ',|[(){}\\[\\]]|[+/*=<>:;!%&\|\\-\\.]+';
    var WHITESPACE = '\\n|[\\r \\t]+';

    var pattern = new RegExp(REAL + '|' + INTEGER + '|' + IDENTIFIER +
        '|' + OPERATOR + '|' + WHITESPACE, 'g');

    var match, matches = [], index = -1;
    while ((match = pattern.exec(text)) !== null) {
        matches.push(match[0]);
    }

    return {
        next: function() {
            index++;
            return {
                value: matches[index],
                done: index >= matches.length
            };
        }
    };
}

var operators = (function() {

    var NOT_OPERATOR = null;
    var WORD_OPERATOR = 5;
    var CUSTOM_OPERATOR = 10;

    function getPrecedence(operator) {
        if (!operator) {
            return;
        }

        var operators = {
            '{': NOT_OPERATOR,
            '(': NOT_OPERATOR,
            '}': NOT_OPERATOR,
            ')': NOT_OPERATOR,
            ',': NOT_OPERATOR,
            ';': 2,
            '=': 3,
            '+': 20,
            '-': 20,
            '/': 40,
            '*': 40
        };

        if (operator in operators) {
            return operators[operator];
        }

        if (/^[A-Za-z0-9_]/.test(operator)) {
            // identifiers
            return WORD_OPERATOR;
        }

        // new operators
        return CUSTOM_OPERATOR;
    }

    function bindsToRight(operator) {
        return operator === ':';
    }

    return {
        getPrecedence: getPrecedence,
        bindsToRight: bindsToRight,
        // higher than ; but lower than word operators
        SMALL_PRECEDENCE: 4,
        LOW_PRECEDENCE: 0
    }
}());

function parse(tokens, ops) {

    var currentToken;

    function nextToken() {
        currentToken = tokens.next().value;
        if (currentToken && currentToken.trim() === '') {
            nextToken();
        }
    }

    function nextExpression(precedence) {
        var left = nextPrimary();
        return nextBinaryOperator(precedence, left);
    }

    function nextPrimary() {
        if (!currentToken) {
            throw new SyntaxError('Unexpected end of input.');
        }
        var primary, annotations = nextAnnotations();
        if (currentToken === 'fn') {
            primary = nextFunctionDefinition();
        } else if (currentToken === '{') {
            primary = nextParens();
        } else {
            primary = nextIdentifier();
        }
        while (currentToken === '(') {
            primary = nextFunctionArguments(primary);
        }
        primary.annotations = annotations;
        return primary;
    }

    function nextFunctionDefinition() {
        nextToken(); // eat fn
        if (currentToken !== '(') {
            throw new SyntaxError('Expected ( in function definition but found ' + currentToken);
        }
        var args = nextArguments();
        var body = nextExpression(ops.SMALL_PRECEDENCE);
        return new FunctionDefinition(args, body);
    }

    function nextParens() {
        nextToken(); // eat {
        var expression = nextExpression(ops.LOW_PRECEDENCE);
        if (currentToken !== '}') {
            throw new SyntaxError('Expected } but found ' + currentToken);
        }
        nextToken(); // eat }
        return expression;
    }

    function nextIdentifier() {
        var identifier = new Identifier(currentToken);
        nextToken(); // eat identifier
        return identifier;
    }

    function nextFunctionArguments(func) {
        return new FunctionCall(func, nextArguments());
    }

    function nextBinaryOperator(precedence, left) {
        while (true) {
            var tokenPrec = ops.getPrecedence(currentToken);

            if (!tokenPrec || tokenPrec < precedence) {
                return left;
            }

            var operator = nextIdentifier();
            var right = nextPrimary();
            var nextTokenPrec = ops.getPrecedence(currentToken);
            if (nextTokenPrec) {
                var nextPrec;
                if (tokenPrec < nextTokenPrec) {
                    nextPrec = tokenPrec + 1;
                } else if ((tokenPrec === nextTokenPrec) && ops.bindsToRight(operator.name)) {
                    nextPrec = tokenPrec;
                }
                if (nextPrec) {
                    right = nextBinaryOperator(nextPrec, right);
                }
            }

            left = new FunctionCall(operator, [left, right]);
        }
    }

    function nextArguments() {
        nextToken(); // eat (
        var args = [];

        if (currentToken === ')') {
            nextToken(); // eat )
            return args;
        }

        while (true) {
            args.push(nextExpression());
            if (currentToken === ')') {
                nextToken(); // eat )
                return args;
            }
            if (currentToken !== ',') {
                throw new SyntaxError('Expected , but found ' + currentToken);
            }
            nextToken(); // eat ','
        }
    }

    function nextAnnotations() {
        var annotations = [];
        while (currentToken && /^\@[A-Za-z0-9_]+$/.test(currentToken)) {
            annotations.push(currentToken);
            nextToken();
        }
        return annotations;
    }

    nextToken(); // initialize
    var topExpression = nextExpression();
    if (currentToken) {
        throw new SyntaxError('Text after the end of input: ' + currentToken);
    }
    return topExpression;
}

Identifier.prototype.evaluate = function(context, variables, continuation) {
    continuation(context.substitute(variables, this.name));
};

FunctionDefinition.prototype.evaluate = function(context, variables, continuation) {
    var func = context.compile(variables, this.args, this.body);
    continuation(func);
};

FunctionCall.prototype.evaluate = function(context, variables, continuation) {
    var args = this.args;
    function continueFunc(func) {
        var values = [];
        function continueArg(index, continuation) {
            function bindArgument(value) {
                values[index] = value;
                continueArg(index + 1, continuation);
            }
            if (index < args.length) {
                context.evaluateArgument(variables, func, index, args[index], bindArgument);
            } else {
                context.invoke(variables, func, values, continuation);
            }
        }
        continueArg(0, continuation);
    }
    this.func.evaluate(context, variables, continueFunc);
};

function interpret(expression, globals, wrapInvocation, callback) {

    function substitute(variables, name) {
        if (!isNaN(parseInt(name, 10))) {
            return parseInt(name, 10);
        }
        if (!(name in variables)) {
            throw new Error(name + ' symbol is not bound.');
        }
        return variables[name];
    }

    function compile(scope, parameters, body) {
        return {
            parameters: parameters,
            body: body,
            execute: function (context, variables, arguments, continuation) {
                var symbols = Object.create(scope);
                for (var i = 0; i < parameters.length; i++) {
                    symbols[parameters[i].name] = arguments[i];
                }
                body.evaluate(context, symbols, continuation);
            },
            length: parameters.length,
            toString: function() {
                return 'fn(' + parameters.join(', ') + ') { ' + body + ' }';
            }
        };
    }

    function invoke(variables, func, args, continuation) {
        continuation = wrapInvocation(continuation);
        if (func.length > args.length) {
            continuation({
                length: func.length - args.length,
                execute: function(context, variables, current, continuation) {
                    context.invoke(variables, func, args.concat(current), continuation);
                },
                toString: function() {
                    return func + '(' + args.join(', ') + ')';
                }
            });
        } else if (typeof func === 'function') {
            continuation(func.apply(variables, args));
        } else if (typeof func.execute === 'function') {
            func.execute(this, variables, args, continuation);
        } else {
            throw new Error('Func must be a function.');
        }
    }

    function evaluateArgument(variables, func, index, value, continuation) {
        if (hasAnnotation(func.parameters, index, '@lazy')) {
            continuation(this.compile(variables, [], value));
        } else {
            value.evaluate(this, variables, continuation);
        }
    }

    function hasAnnotation(parameters, index, annotation) {
        var annotations = parameters && parameters[index] && parameters[index].annotations;
        return annotations && annotations.some(function(parameterAnnotation) {
            return parameterAnnotation === annotation;
        });
    }

    expression.evaluate({
        substitute: substitute,
        compile: compile,
        invoke: invoke,
        evaluateArgument: evaluateArgument
    }, globals, callback);

}

var code = '2 + 3 * 6';

var expression = parse(lexer(code), operators);

var globals = {
    '+': function(a, b) {
        print('add ' + a + ' and ' + b);
        return a + b;
    },
    '*': function(a, b) {
        print('multiply ' + a + ' and ' + b);
        return a * b;
    }
};

var identity = function(value) {
    return value;
};

interpret(expression, globals, identity, function(result) {
    print('result ' + result);
});

var globals = {
    '*': function(a, b) {
        return a * b;
    },
    ';': function(a, b) {
        return b;
    },
    '+': function(a, b) {
        return a + b;
    },
    '-': function(a, b) {
        return a - b;
    },
    '%': function(a, b) {
        return a % b;
    }
};

Object.assign(globals, {
    '>': function(a, b) {
        return this[a > b];
    },
    '!=': function(a, b) {
        return this[a !== b];
    },
    '==': function(a, b) {
        return this[a === b];
    }
});

function firstLazy(fn, parameters) {
    fn.parameters = [ { annotations: ['@lazy'] } ];
    return fn;
}

Object.assign(globals, {
    '=': firstLazy(function (expr, value) {
        if (expr && expr.body instanceof Identifier) {
            if (this.hasOwnProperty(expr.body.name)) {
                throw new Error('Symbol ' + expr.body.name + ' has already been bound.');
            }
            return this[expr.body.name] = value;
        }
        throw new Error('Left side should be an identifier.');
    }),
    '<-': firstLazy(function (expr, value) {
        if (expr && expr.body instanceof Identifier) {
            var name = expr.body.name, table = this;
            while (table && !(table.hasOwnProperty(name))) {
                table = Object.getPrototypeOf(table);
            }
            if (table) {
                return table[name] = value;
            }
            throw new Error(name + ' is not bound.');
        }
        throw new Error('Left side should be an identifier.');
    })
});

Object.assign(globals, {
    print: function(value) {
        print(Array.prototype.join.call(arguments, ', '));
        return value;
    },
    display: firstLazy(function(expr) {
        print(expr.body);
        return 0;
    })
});

Object.assign(globals, {
    callcc: {
        execute: function(context, vars, args, continuation) {
            var contFunction = {
                execute: function(context, vars, args, k) {
                    continuation(args[0]);
                }
            };
            context.invoke(vars, args[0], [contFunction], continuation);
        }
    }
});

if (!Object.assign) {
  Object.defineProperty(Object, "assign", {
    enumerable: false,
    configurable: true,
    writable: true,
    value: function(target, firstSource) {
      "use strict";
      if (target === undefined || target === null)
        throw new TypeError("Cannot convert first argument to object");

      var to = Object(target);

      var hasPendingException = false;
      var pendingException;

      for (var i = 1; i < arguments.length; i++) {
        var nextSource = arguments[i];
        if (nextSource === undefined || nextSource === null)
          continue;

        var keysArray = Object.keys(Object(nextSource));
        for (var nextIndex = 0, len = keysArray.length; nextIndex < len; nextIndex++) {
          var nextKey = keysArray[nextIndex];
          try {
            var desc = Object.getOwnPropertyDescriptor(nextSource, nextKey);
            if (desc !== undefined && desc.enumerable)
              to[nextKey] = nextSource[nextKey];
          } catch (e) {
            if (!hasPendingException) {
              hasPendingException = true;
              pendingException = e;
            }
          }
        }

        if (hasPendingException)
          throw pendingException;
      }
      return to;
    }
  });
}

Trampoline

Continuation passing style can pose serious problems with nontrivial programs in a language when loops are emulated using function calls.

var dependencies = lists.get() + ' ; ' + cond.get() + ' ; ';

var code = 'fib = fn(i) { if (i > 2) then { fib(i - 1) + fib(i - 2) } else 1 }; fib(6)';

var expression = parse(lexer(dependencies + code), operators);

var identity = function(value) {
    return value;
};

interpret(expression, globals, identity, function(result) {
    print('result ' + result);
});

For small values (like 7) the Fibonacci number is properly calculated. Trying to calculate the value for a bigger input number (like 15) will yield a stack overflow error.

var dependencies = lists.get() + ' ; ' + cond.get() + ' ; ';

var code = 'fib = fn(i) { if (i > 2) then { fib(i - 1) + fib(i - 2) } else 1 }; fib(15)';

var expression = parse(lexer(dependencies + code), operators);

var identity = function(value) {
    return value;
};

interpret(expression, globals, identity, function(result) {
    print('result ' + result);
});

The problem is that in the continuation passing style no function ever returns thus the call stack is continuously growing. Until JavaScript supports tail calls (that is calls to functions that do not add stack frames) the problem has to be solved differently.

One solution is to convert the execution from the recursive style to the iterative one using a trampoline.

var trampoline = (function() {
    var thunks = [];

    function wrap(func) {
        return function() {
            thunks.push({
                func: func,
                args: arguments
            });
        };
    }

    function execute() {
        var result, thunk;
        while ((thunk = thunks.shift())) {
            result = thunk.func.apply(null, thunk.args);
        }
        return result;
    }

    return {
        wrap: wrap,
        execute: execute
    };
}());

The code below uses a trampoline to collect and iteratively invoke continuation functions (thunks). Even for bigger input numbers like 15 this code works correctly.

var dependencies = lists.get() + ' ; ' + cond.get() + ' ; ';

var code = 'fib = fn(i) { if (i > 2) then { fib(i - 1) + fib(i - 2) } else 1 }; fib(15)';

var expression = parse(lexer(dependencies + code), operators);

interpret(expression, globals, trampoline.wrap, function(result) {
    print('result ' + result);
});

trampoline.execute();

function fneval(globals, code, callback) {
    var ast = parse(lexer(code), operators);
    return interpret(ast, globals, function(f) { return f; }, callback);
}

function evalCode() {
  fneval(window.staticGlobals, code.get(), function(result) {
     print(result, 'Result');
     document.querySelector('.continuation-execute').disabled = false;
  });
}
clear();
try {
    if (!window.staticGlobals) {
      window.staticGlobals = globals;
      fneval(window.staticGlobals, init.get(), evalCode);
    } else {
    evalCode();
  }
} catch (e) {
    print(e, 'Error');
}

function fneval(code) {
    var ast = parse(lexer(code), operators), result;
    interpret(ast, globals, trampoline.wrap, function(res) { result = res; });
    trampoline.execute();
    return result;
}

clear();
try {
    if (typeof lists !== 'undefined') {
        fneval(lists.get());
    }
    if (typeof cond !== 'undefined') {
        fneval(cond.get());
    }
    if (typeof precode !== 'undefined') {
        fneval(precode.get());
    }
    print(fneval(code.get()), 'Result')
} catch (e) {
    print(e, 'Error');
}

function fneval(code) {
    var ast = parse(lexer(code), operators), result, count = 0;
    interpret(ast, globals, function(k) {
      count++;
      if (count > 80) {
        throw 'Stop execution';
      }
      return trampoline.wrap(k);
    }, function(res) { result = res; });
    trampoline.execute();
    return result;
}

clear();
try {
    print(fneval(code.get()), 'Result')
} catch (e) {
    print(e, 'Error');
}

Simplifying web applications

Server-side web applications need to be structured around the request/response model of the stateless HTTP. Continuations can be used to hide the fact that the application waits for an another request with the data needed to advance the logical code flow.

The following Java servlet implements a simple generic form-based flow using JavaScript interpreter Rhino which supports continuations.

package org.curiositydriven.continuations;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Method;

import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import javax.servlet.http.HttpSession;

import org.mozilla.javascript.Context;
import org.mozilla.javascript.ContinuationPending;
import org.mozilla.javascript.FunctionObject;
import org.mozilla.javascript.Script;
import org.mozilla.javascript.ScriptableObject;

@WebServlet("/")
public class ContinuationsServlet extends HttpServlet {

    private static final String CONTINUATION_KEY = "continuation";
    private static final String READ_METHOD_NAME = "read";

    private static final long serialVersionUID = 1L;

    private final Method readMethod;

    public ContinuationsServlet() {
        try {
            this.readMethod = ContinuationsServlet.class.getDeclaredMethod(
                    READ_METHOD_NAME, String.class);
        } catch (NoSuchMethodException e) {
            throw new AssertionError("Method declared", e);
        } catch (SecurityException e) {
            throw new AssertionError("Method declared", e);
        }
    }

    public static String read(String parameter) {
        Context context = Context.enter();
        try {
            ContinuationPending pending = context.captureContinuation();
            pending.setApplicationState(parameter);
            throw pending;
        } finally {
            Context.exit();
        }
    }

    @Override
    protected void doPost(HttpServletRequest request,
            HttpServletResponse response) throws IOException {
        this.doGet(request, response);
    }

    @Override
    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws IOException {
        response.setContentType("text/html");
        response.setStatus(HttpServletResponse.SC_OK);

        HttpSession session = request.getSession(true);

        Object state = session.getAttribute(CONTINUATION_KEY);

        String scriptName = request.getRequestURI() + ".js";
        String value = request.getParameter("value");

        PrintWriter writer = response.getWriter();

        try {
            writer.println("<h1>Hello Servlet</h1>");
            writer.println("<form method=post>");
            Result result = executeScript(scriptName, state, value);
            if (result.isDone()) {
                writer.println("<h2>Result</h2>");
                writer.println(result.value);
                session.removeAttribute(CONTINUATION_KEY);
            } else {
                writer.println("<h2>" + result.value + "</h2>");
                writer.println("<input autofocus name=value>");
                writer.println("<input type=submit></form>");
                session.setAttribute(CONTINUATION_KEY, result.state);
            }
        } finally {
            writer.close();
        }
    }

    private Result executeScript(String scriptName, Object state,
            String value) throws IOException {

        Context ctx = Context.enter();
        ctx.setOptimizationLevel(-1);

        ScriptableObject scope = ctx.initStandardObjects();

        FunctionObject readFunction = new FunctionObject(READ_METHOD_NAME,
                readMethod, scope);
        scope.put(READ_METHOD_NAME, scope, readFunction);

        Script script = ctx.compileReader(getScriptReader(scriptName),
                scriptName, 1, null);

        try {
            Object result;
            if (state == null) {
                result = ctx.executeScriptWithContinuations(script, scope);
            } else {
                result = ctx.resumeContinuation(state, scope, value);
            }
            return Result.done(result);
        } catch (ContinuationPending pending) {
            return Result.resume(pending.getApplicationState(),
                    pending.getContinuation());
        } finally {
            Context.exit();
        }
    }

    private InputStreamReader getScriptReader(String scriptName) {
        return new InputStreamReader(
                ContinuationsServlet.class.getResourceAsStream(scriptName));
    }

    private static final class Result {
        public final Object value;

        public final Object state;

        private Result(Object value, Object state) {
            this.value = value;
            this.state = state;
        }

        public boolean isDone() {
            return this.state == null;
        }

        public static Result done(Object result) {
            return new Result(result, null);
        }

        public static Result resume(Object value, Object state) {
            return new Result(value, state);
        }
    }
}

To run these examples checkout the project from Github, download Maven and execute mvn jetty:run in the project’s directory. The web server will be started and listening on port 8080.

This servlet reads JavaScript files that have one special read function exposed. Calling that function sends a response to the browser and suspends the script execution. When the browser posts the form back to the server the continuation is looked up in the session object and the script execution is resumed.

Sample script.js — http://localhost:8080/script:

var a = read("enter a");
var b = read("enter b");
parseInt(a, 10) + parseInt(b, 10);

Sample numbers.js — http://localhost:8080/numbers:

var number;
do {

  number = read("Enter a number");

} while(isNaN(parseInt(number, 10)));

number + " is a number.";

Although the flow of code spans multiple request/response cycles the code is straightforward to read because of its apparent synchronous nature.

This approach is used in the Seaside web application framework.

Disadvantages

Continuations are powerful control mechanism but their biggest disadvantage is the fact that code abusing continuations can be hard to follow. Other problems with using continuations include possible memory leaks and a significant performance penalty.

Some of these problems can be alleviated with delimited continuations.