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.
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.