Skip to content

Instantly share code, notes, and snippets.

@be5invis
Last active July 1, 2019 11:26
Show Gist options
  • Save be5invis/67a44015ab7367b577d6 to your computer and use it in GitHub Desktop.
Save be5invis/67a44015ab7367b577d6 to your computer and use it in GitHub Desktop.
A CPS-style S-exp interpreter (with call/cc)
function interpret(form, env, k){
if(form instanceof Array){
switch(form[0]){
case 'lambda': {
var params = form[1];
var body = form[2];
return k(function(k){ return function() {
var e = Object.create(env);
for(var j = 0; j < params.length; j++)
e[params[j]] = arguments[j];
return interpret(body, e, k)
}})
};
case 'if': {
var test = form[1];
var consequent = form[2];
var alternate = form[3];
return interpret(form[1], env, function(c){
if(c) return interpret(consequent, env, k)
else return interpret(alternate, env, k)
})
};
case 'callcc': {
return interpret(form[1], env, function(f){
var fctx = function(){
return function(x){ return k(x) }};
return f(fctx)(fctx)
})
};
case 'quote': {
return k(form[1])
};
default: {
return interpretCall(form, env, k);
};
}
} else if(typeof form === 'string') {
return k(env[form])
} else {
return k(form)
}
}
function interpretCall(form, env, k){
return interpret(form[0], env, function(callee){
return interpret$(form.slice(1), env, function(args){
return callee(k).apply(null, args)
})
})
}
function interpret$(form, env, k){
if(!form.length) return k([]);
else return interpret(form[0], env, function(x0){
return interpret$(form.slice(1), env, function(x$){
return k([x0].concat(x$))
})
})
}
function id(x){ return x }
var env0 = {
trace: function(k){
return function(x) { return k(console.log(x)) }},
begin: function(k){
return function(x$) { return k(arguments[arguments.length - 1]) }}
};
interpret(['trace', ['callcc', ['lambda', ['return'], ['begin',
['trace', ['quote', 1]], // traces
['return', ['quote', 2]], // returns, sent to 'trace'
['trace', ['quote', 3]] // not executed
]]]], env0, id);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment