みんなだいすきラムダ式

lambda.md

みんなだいすきラムダ式.

function Lambda(argName, body) {
    this.argName = argName;
    this.body    = body;
}

Lambda.prototype.eval = function (env) {
    var argName = this.argName;
    var body    = this.body;
    return function (_arg) {
        var local = Object.create(env);
        local[argName] = _arg;
        return body.eval(local);
    };
};

function Application(func, arg) {
    this.func = func;
    this.arg  = arg;
}

Application.prototype.eval = function (env) {
    var _func = this.func.eval(env);
    var _arg  = this.arg.eval(env);
    return _func(_arg);
};

function Variable(name) {
    this.name = name;
}

Variable.prototype.eval = function (env) {
    return env[this.name];
};

定番の自然数.

var global = Object.create(null);

// zero = λf x. x
global["zero"] = new Lambda("f", new Lambda("x", new Variable("x"))).eval(global);
// succ = λn f x. f (n f x)
global["succ"] = new Lambda("n",
        new Lambda("f", new Lambda("x",
            new Application(new Variable("f"),
                new Application(
                    new Application(new Variable("n"), new Variable("f")),
                    new Variable("x")
                )
            )
        ))
    ).eval(global);
// one = succ zero
// two = succ one
// ...
global["one"]   = new Application(new Variable("succ"), new Variable("zero")).eval(global);
global["two"]   = new Application(new Variable("succ"), new Variable("one")).eval(global);
global["three"] = new Application(new Variable("succ"), new Variable("two")).eval(global);
global["four"]  = new Application(new Variable("succ"), new Variable("three")).eval(global);
global["five"]  = new Application(new Variable("succ"), new Variable("four")).eval(global);

// plus = λm n f x. m f (n f x)
global["plus"] =
    new Lambda("m", new Lambda("n",
        new Lambda("f", new Lambda("x",
            new Application(
                new Application(new Variable("m"), new Variable("f")),
                new Application(
                    new Application(new Variable("n"), new Variable("f")),
                    new Variable("x")
                )
            )
        ))
    )).eval(global);

// foo = plus three five
global["foo"] =
    new Application(
        new Application(new Variable("plus"), new Variable("three")),
        new Variable("five")
    ).eval(global);

ちゃんと計算できてるか確認.

function Literal(val) {
    this.val = val;
}

Literal.prototype.eval = function (env) {
    return this.val;
};

global["+1"] = new Literal(function (n) { return n + 1; }).eval(global);
global["0"] = new Literal(0).eval(global);
console.log(
    new Application(
        new Application(new Variable("foo"), new Variable("+1")),
        new Variable("0")
    ).eval(global)
);