Call-with-current-continuation in an Explicit Control Evaluator for JavaScript
revised on May 20, 2022
Motivation
In the post An Explicit-control Evaluator in Stages, control is made explicit by a continuation data structure. The continuation explicitly keeps track of the components that need to be evaluated after the current component is dealt with. The evaluator compiles complex components such as conditionals and applications on the fly into sequences of smaller components in the continuation. Components can push and pop from an operand stack, and a runtime stack allows return statements to pass control back to caller of the currently executing function.
In this post, I show how this explicit-control evaluator can be modified to handle call-with-current-continuation, a powerful construct available in Scheme. The resulting call-cc-enabled evaluator includes the implementation and examples given below.
What is call-with-current-continuation?
The idea is to call a function f in such a way that the current continuation
at the time of calling f is available to the programmer as a unary function.
Calling that continuation with an argument x will return control back to the
place where f was called, with x as return value. More concretely, our
evaluator will provide a function callcc which can be applied to a unary function f.
When declaring the function f, the programmer can refer to the current continuation
at the time of calling callcc on f using the parameter of f, for example the name
continuation. The application
callcc(f) is treated as an application of f(continuation).
If at any time, this continuation
gets applied to an argument x, control immediately
goes back to the place where callcc was
called. The value x is then treated as the return value of the call of callcc.
Example
Consider the following program in a version of JavaScript that is extended by
callcc.
function f(ret) {
ret(2);
return 3;
}
display(f(x => x)); // displays 3
display(callcc(f)); // displays 2
When f is applied normally to a given function such as
x => x as ret, that function gets
gets applied to 2. Then
the evaluation of the body of f continues, and f returns the value 3. When f
is applied using callcc, the current continuation of the call site of callcc is
available as ret during the evaluation of the body of f. The effect of calling ret
with argument 2 is that control immediately returns to the place where callcc was
called, with 2 as the return value of the application of callcc. The
statement return 3; is not executed in this case. The value 2 is displayed.
Implementation Strategy
Implementation of callcc in the explicit-control evaluator is not hard, but a bit
tricky. My strategy is to treat both callcc and the continuations as primitive
functions that have direct access to the operand stack, runtime stack, and continuation.
To make this work, I need to slightly modify the way primitive functions are
applied, which means I need to come up with a modified calling convention for primitive
functions. With that in place, the primitive function callcc can be added to
the environment that is used for evaluating a given program.
Tweaking the calling convention for primitive functions
Recall that the explicit-control evaluator compiles a function application into a sequence of components in the continuation: the function expression, followed by the argument expressions, followed by a call instruction that remembers the number of arguments used in the application. The following fragment of the explicit-control evaluator handles the case where the function being applied is a primitive function.
// call instruction clause in explicit control evaluator
} else if (is_call_instruction(component)) {
const arity = call_instruction_arity(component);
const args = take(operands, arity);
const callee_and_remaining_operands = drop(operands, arity);
const callee = head(callee_and_remaining_operands);
operands = tail(callee_and_remaining_operands);
if (is_primitive_function(callee)) {
components = continuation;
operands = pair(apply_in_underlying_javascript(
primitive_implementation(callee),
args),
operands);
} else {
...
}
} else ...
In this calling convention, the primitive implementation does not get a chance
to change the operands, because any changes to operands done in the primitive
implementation is undone by the assignment to operands which of course
gets executed after that call of apply_in_underlying_javascript. In our
new evaluator, I sightly change the calling convention:
// new call instruction clause in explicit control evaluator
} else if (is_call_instruction(component)) {
const arity = call_instruction_arity(component);
const args = take(operands, arity);
const callee_and_remaining_operands = drop(operands, arity);
const callee = head(callee_and_remaining_operands);
operands = tail(callee_and_remaining_operands);
if (is_primitive_function(callee)) {
operands = pair(undefined, // dummy
drop(operands, arity + 1));
components = continuation;
const return_value =
apply_in_underlying_javascript(
primitive_implementation(callee),
args);
set_head(operands, return_value); // replace dummy
} else {
...
}
} else ...
The value of operands at the time of calling the primitive implementation
has a dummy value undefined in place of the return value.
The application of set_head will set the head of the
pair to which the name operands refers after
after execution of the primitive implementation.
Therefore, the primitive implementation can make
changes to operands, which will survive after execution of the call
instruction. Regardless what changes the primitive implementation is
making on operands, the return value is guaranteed to become its
first value.
Note that this modified calling convention does not make a difference
for any existing primitive functions, because they do not modify operands.
Implementing callcc
With this tweak in place, I implement callcc as
a primitive function, which is made available to the evaluator
in the initial environment that the evaluator starts with.
function evaluate(program) {
let callcc = list("primitive",
f => {
...
});
// add primitive function callcc to initial environment
let environment = extend_environment(list("callcc"),
list(callcc),
the_global_environment);
let components = list(program);
let operands = null;
let runtime_stack = null;
while (! is_null(components)) {
...
}
return head(operands);
}
By placing the definition of the callcc primitive inside the
function evaluate, the implementation can refer to and
manipulate the state of the evaluator. In particular, it can
declare the_continuation as a primitive function (explained
later).
function evaluate(program) {
let callcc = list("primitive",
f => {
...
const the_continuation =
list("primitive",
x => {
...
});
// place dummy and f on operand stack;
// current call instruction will replace dummy
// with return value the_continuation
operands = append(list(undefined, f),
// drop previous dummy
tail(operands));
// put call instruction back into components
// which will find the_continuation on top of
// operand stack and f below it, so f will be
// called with the_continuation as argument
components = pair(make_call_instruction(1),
components);
return the_continuation;
});
...
}
This implementation of the callcc primitive pushes a new call instruction
on the continuation, in order to call the function f with the current
continuation. To make sure f is called, it will appear in second position
on the operand stack, after a dummy value undefined, which will be
replaced by the return value of the primitive function, according to the
new calling convention. The previous dummy value, which was placed by
the call instruction on top of operands, is dropped.
The continuation itself is also implemented by a primitive function, and therefore also has access to the machine state. Here is its implementation.
function evaluate(program) {
let callcc = list("primitive",
f => {
// take snapshot of evaluator state
const the_components = components;
const the_operands = operands;
const the_environment = environment;
const the_runtime_stack = runtime_stack;
const the_continuation =
list("primitive",
x => {
// reinstate evaluator state
components = the_components;
environment = the_environment;
runtime_stack = the_runtime_stack;
operands = the_operands;
// call instruction of continuation
// will replace dummy value
// on top of the_operands by x
return x;
});
...
return the_continuation;
});
...
}
The primitive function callcc avails to the continuation
the state of the evaluator at the time callcc was called.
When the continuation is called, it restores this state.
The calling convention places a dummy value undefined for
the return value of callcc on top of operands.
The return
value of the continuation is the argument of the continuation, which
will replace the dummy value.
The nuclear bomb in your garage
This wiki explains the pros and cons of call-with-current-continuation, and I recommend that you take a close look if you would like to include this feature in your programming language. I’m taking the liberty to slightly modify the “nuclear bomb” example from the wiki, which shall conclude this blog post.
parse_and_evaluate(`
function for_each(p, lst) {
if (is_null(lst)) {
return "done";
} else {
p(head(lst));
for_each(p, tail(lst));
}
}
display(callcc(exit => {
for_each(x => x === "nuclear"
? exit(x + " alarm")
: display(x),
list("this", "is", "a",
"nuclear", "bomb",
"in", "your", "garage")
);
return "don't worry";
}));
`);
Here, the function to which callcc is applied passes a function to
for_each which calls the continuation exit if the value
"nuclear" is encountered. When that happens, control immediately returns
to the place where callcc was called, with the argument of exit, here
the string "nuclear alarm", as
return value. Therefore, the program displays the following:
"this"
"is"
"a"
"nuclear alarm"
If you replace the line "nuclear", "bomb", with "neat", "bicycle",,
the program will display:
"this"
"is"
"a"
"neat"
"bicycle"
"in"
"your"
"garage"
"don't worry"