Lisp Interpreter

lisp.js

var readline = require('readline');

function Scope(variables, parent) {
    this.variables = variables || {};
    this.parent = parent;
}

Scope.prototype.find = function(name) {
    return this.variables.hasOwnProperty(name) ?
        this.variables[name] :
        typeof this.parent === 'undefined' ?
            undefined :
            this.parent.find(name);
}

Scope.prototype.setIfDefined = function(name, value) {

    if (typeof this.variables[name] === 'undefined') {
        throw 'Cannot assign to undefined variable';
    }

    this.define(name, value);
}

Scope.prototype.define = function(name, value) {
    this.variables[name] = value;
}

function IntepreterSyntaxError(message) {
    this.message = message;
    this.stack   = (new Error(message)).stack;
}

IntepreterSyntaxError.prototype = new Error();
IntepreterSyntaxError.prototype.constructor = IntepreterSyntaxError;

function LispRuntimeError(message) {
    this.message = message;
    this.stack   = (new Error(message)).stack;
}

LispRuntimeError.prototype = new Error();
LispRuntimeError.prototype.constructor = LispRuntimeError;

function LispNumber(value) {
    value = Number(value);

    if (isNaN(value)) {
        throw new IntepreterSyntaxError('Expected number. Got ' + value);
    }

    this.value = value;
}

function Intepreter(rootScope) {
    var realRootScope = new Scope({
        '+'  : function(arg1, arg2) { return arg1 +  arg2; },
        '*'  : function(arg1, arg2) { return arg1 *  arg2; },
        '-'  : function(arg1, arg2) { return arg1 -  arg2; },
        '/'  : function(arg1, arg2) { return arg1 /  arg2; },
        '>=' : function(arg1, arg2) { return arg1 >= arg2; },
        '<=' : function(arg1, arg2) { return arg1 <= arg2; },
        '<'  : function(arg1, arg2) { return arg1 <  arg2; },
        '>'  : function(arg1, arg2) { return arg1 >  arg2; },
        '='  : function(arg1, arg2) { return arg1 =  arg2; },
    });

    this.rootScope = new Scope((rootScope && rootScope.variables) || {}, realRootScope);
}

Intepreter.prototype.tokenize = function(lisp) {
    return lisp.replace(/\(/g, '( ').replace(/\)/g, ' )').split(' ');
}

Intepreter.prototype.parse = function(rawTokens, tokens) {
    if (!tokens) {
        tokens = rawTokens.slice();
    }

    if (!tokens.length) {
        throw new IntepreterSyntaxError('Unexpected EOF while reading');
    }

    var token = tokens.shift();
    var list;

    if (token === '(') {
        list = [];

        if (tokens[tokens.length - 1] !== ')') {
            throw new IntepreterSyntaxError('Unexpected EOF while reading');
        }

        while (tokens[0] !== ')') {
            list.push(this.parse(null, tokens));
        }

        tokens.shift();

        return list;
    } else if (token === ')') {
        throw new IntepreterSyntaxError('Unexpected token )');
    } else {
        return this.parseLiteral(token);
    }
}

Intepreter.prototype.parseLiteral = function(token) {
    return isNaN(Number(token)) ? token : new LispNumber(token);
}

Intepreter.prototype.evaluate = function(token, scope) {
    if (!scope) {
        scope = this.rootScope;
    }

    if (typeof token === 'string') {
        var val = scope.find(token);

        if (typeof val === 'undefined') {
            throw new LispRuntimeError('Undefined variable ' + token);
        }

        return val;
    }

    if (token instanceof LispNumber) {
        return token.value;
    }

    return this.evaluateStatement(token, scope);
}

Intepreter.prototype.evaluateStatement = function(token, scope) {

    switch (token[0]) {
        case 'quote':
            return token[1];
        break;

        case 'if':
            return this.evaluateIf(token, scope);
        break;

        case 'set!':
            scope.setIfDefined(token[1], this.evaluate(token[2]));
        break;

        case 'define':
            scope.define(token[1], this.evaluate(token[2]));
        break;

        case 'lambda':
            return this.evaluateLambda(token, scope);
        break;

        case 'begin':
            var val;
            token.slice(1).forEach(function(tkn) {
                val = this.evaluate(tkn, scope);
            }.bind(this));
            return val;
        break;

        default:
            var expressions = token.map(function(tkn) {
                return this.evaluate(tkn, scope);
            }.bind(this));

            if (!expressions[0]) {
                throw new LispRuntimeError('Undefined function ' + token[0]);
            }

            return expressions[0].apply(this, expressions.slice(1));
        break;
    }
}

Intepreter.prototype.evaluateIf = function(token, scope) {
    return this.evaluate(token[1], scope) ? this.evaluate(token[2], scope) : this.evaluate(token[3], scope);
}

Intepreter.prototype.evaluateLambda = function(token, scope) {
    return function() {
        var vars = {};
        [].slice.call(arguments).forEach(function(val, i) {
            vars[token[1][i]] = val;
        });

        return this.evaluate(token[2], new Scope(vars, scope));
    }.bind(this);
}

Intepreter.prototype.interpret = function(str) {
    return this.evaluate(this.parse(this.tokenize(str)));
}

function repl(prompt, it) {

    var rl = readline.createInterface({
        input  : process.stdin,
        output : process.stdout
    });

    rl.question(prompt, function(answer) {
        rl.close();
        try {
            console.log(it.interpret(answer));
        } catch (e) {
            console.log(e.stack);
        }
        repl(prompt, it);
    });
}

var interpreter = new Intepreter(new Scope());
repl('lisp>>> ', interpreter);