CEK interpreter with TCO example
// noprotect
function Lambda(param, body, e){
this.param = param
this.body = body
this.env = e
};
Lambda.prototype.apply = function(t, args, k0){
var e_ = Object.create(this.env);
for(var j = 0; j < this.param.length; j++){
e_[this.param[j]] = args[j];
}
e_['return'] = function(x){ return k0(x) };
return interpret(this.body, e_, k0)
};
var betas = 0
function interpret(c, e, k){ queue.push(c, e, k); betas += 1 }
function interpret1(c, e, k){
if(typeof c === 'string') return k(e[c]);
else if(c instanceof Array) switch(c[0]) {
case 'quote': return k(c[1]);
case 'if': return interpret(c[1], e, function(test){
if(test) return interpret(c[2], e, k)
else if(c[3]) return interpret(c[3], e, k)
else return k(void 0)
});
case 'lambda': {
var param = c[1], body = c[2];
return k(new Lambda(param, body, e))
};
case 'set': {
return interpret(c[2], e, function(x){
e[c[1]] = x;
return k(x);
})
};
default: {
return interpret$(c, e, function(terms){
var fn = terms[0];
var args = terms.slice(1);
if(fn instanceof Function) {
return k(fn.apply(null, args))
} else if(fn instanceof Lambda) {
return fn.apply(null, args, k)
}
});
};
} else {
return k(c)
}
};
function interpret$(c, e, k){
if(!c.length) return k([]);
else return interpret(c[0], e, function(c0){
return interpret$(c.slice(1), e, function(cx){
return k([c0].concat(cx))
})
})
}
var e = {
'print': function(x){ console.log(x); return x },
'+': function(x, y){ return (x + y) },
'-': function(x, y){ return (x - y) },
'*': function(x, y){ return (x * y) },
'car': function(a){ return (a[0]) },
'cdr': function(a){ return (a.slice(1)) },
'empty': function(a){ return (a.length === 0)},
'<': function(x, y){ return (x < y)},
'begin': function(){ return arguments[arguments.length - 1]}
};
var c = ['begin',
['set', 'sum1', ['lambda', ['low', 'hi', 'acc'],
['if', ['<', 'low', 'hi'],
['sum1', ['+', 'low', 1], 'hi', ['+', 'low', 'acc']],
['+', 'acc', 'low']]]],
['set', 'sum', ['lambda', ['low', 'hi'], ['sum1', 'low', 'hi', 0]]],
['print', ['sum', 1, 100000]], // will stack overflow when there is no TCO
['set', 'callcc', ['lambda', ['f'], ['f', 'return']]], // try to define callcc
['callcc', ['lambda', ['r'], ['begin', ['print', 1], ['r', 2], ['print', 3]]]],
['print', ['quote', 'lalala']]
];
var queue = []; var exit = false;
interpret(c, e, function(x){ console.log('Exit value : ' + x); exit = true });
while(!exit && queue.length){ interpret1(queue.shift(), queue.shift(), queue.shift()) }
console.log('Redexes : ' + betas);