Continuations

comment

There is one abstraction that can be used to implement such apparently diverse concepts as exceptions, generators, coroutines and even the backtracking mechanism present in Prolog.

This article demonstrates how to use continuations to implement these constructs in a custom, small programming language. Then the implementation of an interpreter for that language is presented.

Finally a Java servlet is demonstrated. It uses continuations with server-side JavaScript to simplify writing complex workflows that hide the request/response cycle of HTTP.

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 languagea 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)

                                            Sieve of Eratosthenes

                                            As a test for the language and the interpreter a prime number generator was implemented.

                                            This fragment of code displays a list of prime numbers by constructing a series of streams (lazy lists).

                                            :: = 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)

                                              Interpreter

                                              The interpreter is implemented in the continuation-passing-style and serves as a proof-of-concept of a simple functional programming language that supports continuations.

                                              The syntax tree is comprised of three elements — identifiers, function definitions and function calls.

                                              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;
                                              }

                                              Lexer and parser

                                              Lexer splits the source code into individual tokens.

                                              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
                                                          };
                                                      }
                                                  };
                                              }

                                              The operators helper object is used to resolve how tightly operators bind or what is their associativity. Only a few operators have predefined precedence that is adjusted so that the syntax seems similar to the languages in the C programming language family.

                                              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
                                                  }
                                              }());

                                              The parser returns a syntax tree for the given stream of tokens.

                                              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;
                                              }

                                              Evaluating expressions

                                              Each expression type calls an appropriate method on the context object. The complexity of evaluating a value of the function call is due to the fact that all arguments and the function itself need to be resolved in the continuation passing style.

                                              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);
                                              };

                                              The main interpreter function takes four arguments:

                                              1. the expression to evaluate,
                                              2. an object with global functions,
                                              3. a function that wraps all function invocations,
                                              4. the callback that will be invoked with the result of evaluating that given expression.
                                              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);
                                              
                                              }

                                              The code below calculates a simple mathematical expression:

                                              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);
                                              });

                                                Predefined functions

                                                Code examples in this article use several functions implemented in JavaScript.

                                                There are arithmetic functions that simply delegate to JavaScript.

                                                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;
                                                    }
                                                };

                                                Comparison operators use JavaScript operators and return a value that is bound to either true or false. Functions are added to globals object using ES6 Object.assign function.

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

                                                Binding a value to a name and the assignment operators are also functions. Their first argument is passed as an expression instead of the actual value because of the @lazy annotation.

                                                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.');
                                                    })
                                                });

                                                These two functions are used for logging purposes.

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

                                                Finally — a call-with-current-continuation function. It uses a different format — an object with the execute function — so that there is an explicit access to the continuation object.

                                                callcc invokes the function passed as the first argument with one function-like object contFunction. Calling that inner object resumes execution at the place where the original callcc was called. The continuation k is never used.

                                                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);
                                                        }
                                                    }
                                                });

                                                As contFunction is accessible inside the script it is called a reified program control state. Both continuation and k objects are implementation details of the interpreter and they cannot be accessed or manipulated by scripts.

                                                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();

                                                      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.jshttp://localhost:8080/script:

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

                                                      Sample numbers.jshttp://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.

                                                      Comments

                                                      copsarebastards
                                                      Y
                                                      This is an interesting write-up. This is the first clear explanation I've found of a situation where I can actually see a use for call/cc that I would actually use. (…)
                                                      cancel

                                                      Revisions

                                                      1. Initial version.