How to implement continuations in dynamic language like JavaScript?

Question

I need some hits how I should go about and implement continuation for lips in JavaScript (my lisp is almost like scheme, except no continuations and TOC).

Here is my evaluate function:

function getFunctionArgs(rest, { env, dynamic_scope, error }) {
    var args = [];
    var node = rest;
    markCycles(node);
    while (true) {
        if (node instanceof Pair && !isEmptyList(node)) {
            var arg = evaluate(node.car, { env, dynamic_scope, error });
            if (dynamic_scope) {
                arg = unpromise(arg, arg => {
                    if (typeof arg === 'function' && isNativeFunction(arg)) {
                        return arg.bind(dynamic_scope);
                    }
                    return arg;
                });
            }
            args.push(arg);
            if (node.haveCycles('cdr')) {
                break;
            }
            node = node.cdr;
        } else {
            break;
        }
    }
    return resolvePromises(args);
}
// -------------------------------------------------------------------------
function evaluateMacro(macro, code, eval_args) {
    if (code instanceof Pair) {
        //code = code.clone();
    }
    var value = macro.invoke(code, eval_args);
    return unpromise(resolvePromises(value), function ret(value) {
        if (value && value.data || !value || selfEvaluated(value)) {
            return value;
        } else {
            return quote(evaluate(value, eval_args));
        }
    });
}
// -------------------------------------------------------------------------
function evaluate(code, { env, dynamic_scope, error = () => {} } = {}) {
    try {
        if (dynamic_scope === true) {
            env = dynamic_scope = env || global_env;
        } else if (env === true) {
            env = dynamic_scope = global_env;
        } else {
            env = env || global_env;
        }
        var eval_args = { env, dynamic_scope, error };
        var value;
        if (isNull(code)) {
            return code;
        }
        if (isEmptyList(code)) {
            return emptyList();
        }
        if (code instanceof Symbol) {
            return env.get(code, { weak: true });
        }
        var first = code.car;
        var rest = code.cdr;
        if (first instanceof Pair) {
            value = resolvePromises(evaluate(first, eval_args));
            if (isPromise(value)) {
                return value.then((value) => {
                    return evaluate(new Pair(value, code.cdr), eval_args);
                });
                // else is later in code
            } else if (typeof value !== 'function') {
                throw new Error(
                    type(value) + ' ' + env.get('string')(value) +
                        ' is not a function while evaluating ' + code.toString()
                );
            }
        }
        if (first instanceof Symbol) {
            value = env.get(first, { weak: true });
            if (value instanceof Macro) {
                var ret = evaluateMacro(value, rest, eval_args);
                return unpromise(ret, result => {
                    if (result instanceof Pair) {
                        return result.markCycles();
                    }
                    return result;
                });
            } else if (typeof value !== 'function') {
                if (value) {
                    var msg = `${type(value)} \`${value}' is not a function`;
                    throw new Error(msg);
                }
                throw new Error(`Unknown function \`${first.name}'`);
            }
        } else if (typeof first === 'function') {
            value = first;
        }
        if (typeof value === 'function') {
            var args = getFunctionArgs(rest, eval_args);
            return unpromise(args, function(args) {
                var scope = dynamic_scope || env;
                var result = resolvePromises(value.apply(scope, args));
                return unpromise(result, (result) => {
                    if (result instanceof Pair) {
                        return quote(result.markCycles());
                    }
                    return result;
                }, error);
            });
        } else if (code instanceof Symbol) {
            value = env.get(code);
            if (value === 'undefined') {
                throw new Error('Unbound variable `' + code.name + '\'');
            }
            return value;
        } else if (code instanceof Pair) {
            value = first && first.toString();
            throw new Error(`${type(first)} ${value} is not a function`);
        } else {
            return code;
        }
    } catch (e) {
        error && error(e, code);
    }
}

NOTES:

// unpromise and resolvePromises is just used ot unwrap any promise
// inside list and return new promise for whole expression if found
// any promise and not found it just return value as is
// markCycles is used to prevent of recursive printing of list cycles
// if you create graph cycles using `set-cdr!` or `set-car!`

Do I need to create stack when evaluating expression for continuations? How can I do this? I thought that I create somehow class Continuation that will be in two modes one in filled when it can be called like Macro and in other waiting to be filled by evaluate with code that need to be executed, I'm not sure also how should I go about and not evaluate code that is before expression that call continuation like:

(* 10 (cont 2))

(* 10 x) need to be ignored

I'm also not sure how should I go about and create call/cc as function. Should it return some intermediate data structure with it's argument stored in that data structure so it can be called by evaluate with continuation?

'call/cc': function(lambda) {
   return new CallCC(lambda);
}

and if eval find instance of CallCC it get continuation (not sure how yet) use

if (value instanceof CallCC) {
   value.call(new Continuation(stack));
}

Is this how you will do this? So generally my question is about the stack. Is it needed for continuations? If it's needed, then how it should be created?

I've found this article Writing a Lisp: Continuations that show how to implement continuations, but it's hard to understand because it's in Haskell.

Answer 1

One way to implement continuations in an interpreter is to make that interpreter use its own explicit stack for function calling/returning and parameter passing. If you use the stack of the host language, and that language doesn't have continuations, then things are difficult.

If you use your own explicit stack, you can turn it into a "spaghetti stack" for continuations. A "spaghetti stack" is very similar to common representations of lexical environments. It contains frames, which point to parent frames. Capturing a continuation amounts to retaining a pointer to such a frame, and some code. Resuming a continuation means, more or less, restoring the stack to that frame, and the execution to that point in the code. The interpreter for the language doesn't recurse. When the interpreted language nests or recurses, the interpreter iterates and just pushes and pops the explicit stack to keep track of state.

An alternative approach is to use a linear stack, but copy it when a continuation is made. To resume a continuation, you can restore the entire stack from the copied snapshot. This is useful for delimited continuations, which can avoid copying the entire stack, but only that part of it that is delimited (and restore it on top of the existing stack, rather than by replacement). I have implemented delimited continuations in a language that uses the underlying C stack. A segment of the C stack is memcpy-d out into an object that lives on the heap. When a continuation is restored, that saved stack segment is blasted on top of the current stack. Pointers have to be adjusted, of course, because the segment is now at a different address, and the "dangling cabling" has to be hooked up to integrate that stack segment into the stack properly.

If a language is treated by compilation to CPS (continuation passing style), then continuations pop out for free. Every function has an implicit hidden argument: the continuation it has received. Function returning is compiled into a call to this continuation. If a block of code in the function needs to compute the current continuation, it just has to compose a small local computational future (representable as a lambda) with that incoming continuation (the future computation that happens when the local part returns). Henry Baker wrote a paper based on the observation that under CPS, since no function ever returns (returns compile to tail calls to the continuation), old stack frames are never revisited. The stack can just be allowed to grow, and when it reaches a limit, it can be "rewound" back to the top. Chicken Scheme implements the concept; it's worth investigating if you're interested in continuations. Chicken Scheme compiles to C code that uses the regular C stack. However, the generated functions never return: they simulate returning by calling continuations, and so the stack grows. What is even more fascinating is that objects which we normally understand as dynamic material are allocated from the stack also. Since nothing returns, those objects are safe. Whenever a certain stack limit is reached, all of the objects on the stack which are still live are moved to the heap, and the stack pointer is rewound back to the top.

Answer 2

First off. All languages has continuations. When you do 7 + n * 5 JavaScript reorders that to mul_k(n, 5, (_v) => (add _v 7 k) where k is a function that does everything that happnes after that expression.

Now the first argument to mul_k is a continuation. Nothing scary about it except for one little think. You never actually return anything any longer. Every "return" is just passed to it's continuation which always is a tail call.

A recursive function that itself isn't tail recursive will produce a new closure at each step and nest the next. These are are stored on the heap so non tail recursive functions becomes tail calls with lots of nested closures created.

Here is a small example:

(define (get-c) (call/cc (lambda (cont) cont)))

(let ((example (get-c)))
  (displayln example)
  (if (procedure? example)
      (example 10)
      "done"))

Lets imagine this is the whole program. Lets just write this to JavaScript.

// simple CPS version of displayln
const displayln = (arg, k) k(console.log(arg));

// simple CPS version of procedure?
const isProcedure = (arg, k) k(arg instanceOf Function);

// Simple CPS version of call/cc
const callCC = (userFun, callCCK) 
  => userFun((result, actualK) => callCCK(result), callCCK);

// simple top level continutation. Not a CPS function.
const kTopLevel = console.log;

// the user function get-c transformed into CPS
const getC = getCK => callCC((cont, k) => k(cont), getCK);

// the let code transformed into CPS
getC((example) => // c1
  displayln(example, (_undefined) => // c2 
    isProcedure(example, (result) => // c3
      result ? example(10, kTopLevel) : kTopLevel("done"))

Here is what's happening:

• getC gets the whole continuation (c1) and it calls callCC
• callCC calls c1 with gets (result, _) => c1(result) as example
• display prints example, the continuation, passes its undefinded return value to it's continuation c2
• isPorcedure on example and it being a continuation it passes true as result to continuation c3
• being true it calls example(10, kTopLevel) which becomes c1(10), thus 10 as example
• display prints èxample, the number10, passes its underfined return value to its continuationc2`
• isProcedure on example passes false as result to continuation c3
• Being false it calls TopLevel("dome")
• TopLevel prints "done"

As you can see. call/cc is easy peasy as long as the code is transformed to CPS before execution. JavaScript supports CPS very well.

To help with how to convert code to CPS Matt Might has done it countless times in his essays. Look for continuations in that list. He has even done it in JavaScript.

Now if your implementation needs to beinterpreted you could do the same conversion in Scheme and interpret that instead of user code. If you have continuation barriers you just need CPS from call/cc until the barrier.

Answer 3

synchronous call/cc

callcc can be implemented in direct style using try-catch. The important bit is that the continuation must "box" the return value and "unbox" it in catch to avoid swallowing real errors -

const callcc = f => {
  class Box { constructor(v) { this.unbox = v } }
  try { return f(value => { throw new Box(value) }) }
  catch (e) { if (e instanceof Box) return e.unbox; throw e  }
}

console.log(5 + callcc(exit => 10 * 3))
console.log(5 + callcc(exit => 10 * exit(3)))
console.log(5 + callcc(exit => { exit(10); return 3 }))
console.log(5 + callcc(exit => { exit(10); throw Error("test failed") }))

try {
  console.log(5 + callcc(exit => { throw Error("test passed!") }))
}
catch (e) {
  console.error(e)
}

.as-console-wrapper { min-height: 100%; top: 0; }

35                     ? 5 + 10 * 3
8                      ? 5 + 3
15                     ? 5 + 10
15                     ? 5 + 10
Error: test passed!    ? Errors are not swallowed

callcc was originally implemented in this Q&A. Read on for additional info and examples.