QuantumGhost
7/21/2014 - 7:54 AM

CEK interpreter with TCO example

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);