簡単な言語処理系の実装

interpreter.js

/*
 * 簡単な言語処理系の実装
 *
 * copyright (c) 2015 Susisu
 */

"use strict";

// AST
// 式 = プログラム の基底クラス
class Expr {
    eval(env) {
        throw new Error("unknown expression");
    }
}

// リテラル (数値または真偽値)
class Literal extends Expr {
    constructor(val) {
        super();
        this.val = val;
    }

    eval(env) {
        return this.val;
    }
}

// 変数
class Variable extends Expr {
    constructor(name) {
        super();
        this.name = name;
    }

    eval(env) {
        // 変数が未定義
        if (typeof env[this.name] === "undefined") {
            throw new Error("unbound variable: " + this.name);
        }
        return env[this.name];
    }
}

// ラムダ式 (匿名関数)
class Lambda extends Expr {
    constructor(param, body) {
        super();
        this.param = param;
        this.body  = body;
    }

    eval(env) {
        return arg => {
            // ローカルな環境を作成
            var local = Object.create(env);
            // 束縛
            local[this.param] = arg;
            return this.body.eval(local);
        };
    }
}

// 関数適用
class Application extends Expr {
    constructor(func, arg) {
        super();
        this.func = func;
        this.arg  = arg;
    }

    eval(env) {
        var _func = this.func.eval(env);
        var _arg  = this.arg.eval(env);
        // 関数でなければエラー
        if (typeof _func !== "function") {
            throw new Error(String(_func) + " is not a function");
        }
        return _func(_arg);
    }
}

// 条件分岐
class IfThenElse extends Expr {
    constructor(cond, conseq, alt) {
        super();
        this.cond   = cond;
        this.conseq = conseq;
        this.alt    = alt;
    }

    eval(env) {
        var _cond = this.cond.eval(env);
        // 真偽値でなければエラー
        if (typeof _cond !== "boolean") {
            throw new Error(String(_cond) + " is not a boolean");
        }
        if (_cond) {
            return this.conseq.eval(env);
        }
        else {
            return this.alt.eval(env);
        }
    }
}

// 変数束縛
class LetIn extends Expr {
    constructor(name, bound, body) {
        super();
        this.name  = name;
        this.bound = bound;
        this.body  = body;
    }

    eval(env) {
        // ローカルな環境を作成
        var local = Object.create(env);
        var _bound = this.bound.eval(local);
        // 束縛
        local[this.name] = _bound;
        return this.body.eval(local);
    }
}

new LetIn(
    "max",
    new Lambda(
        "x",
        new Lambda(
            "y",
            new IfThenElse(
                new Application(
                    new Application(
                        new Variable("gt"),
                        new Variable("x")
                    ),
                    new Variable("y")
                ),
                new Variable("x"),
                new Variable("y")
            )
        )
    ),
    new Application(
        new Application(
            new Variable("max"),
            new Literal(2)
        ),
        new Literal(3)
    )
);

// パーサ
var lq = require("loquat");

var langDef = new lq.LanguageDef(
    // 複数行コメント
    "(*", "*)",
    // 一行コメント (ここでは無し)
    "",
    // コメントのネストを許可するか
    true,
    // 識別子 (一文字目と二文字目以降)
    lq.letter, lq.alphaNum.or(lq.oneOf("_'")),
    // 演算子  (一文字目と二文字目以降)
    lq.oneOf(":!#$%&*+./<=>?@\\^|-~"),
    lq.oneOf(":!#$%&*+./<=>?@\\^|-~"),
    // 予約語
    [
        "true", "false",
        "fun",
        "if", "then", "else",
        "let", "in"
    ],
    // 予約演算子
    ["->", "="],
    // 大文字と小文字を区別するか
    true
);
var tp = lq.makeTokenParser(langDef);

// 式 = プログラム
var expr = new lq.LazyParser(() => lq.choice([
    application,
    lambda,
    ifThenElse,
    letIn,
    tp.parens(expr)
]));
// 数値
var t_number = tp.naturalOrFloat
    .bind(nf => lq.pure(nf[nf.length === 1 ? 0 : 1]))
    .label("number");
// 真偽値
var t_true = tp.reserved("true").then(lq.pure(true));
var t_false = tp.reserved("false").then(lq.pure(false));
var t_boolean = t_true.or(t_false)
    .label("boolean");
// リテラル
var literal = t_number.or(t_boolean)
    .bind(val => lq.pure(new Literal(val)));
// 識別子
var identifier = tp.identifier;
// 変数
var variable = identifier.bind(name => lq.pure(new Variable(name)));
// aexpr
var aexpr = lq.choice([
    literal,
    variable,
    tp.parens(expr)
]);
// 関数適用 または lambda, if-then-else, let-in 以外の式
var application = aexpr.bind(func =>
    aexpr.many().bind(args =>
        lq.pure(args.reduce(
            (app, arg) => new Application(app, arg),
            func
        ))
    )
);
// ラムダ式 (匿名関数)
var lambda = tp.reserved("fun").then(identifier).bind(param =>
    tp.reservedOp("->").then(expr).bind(body =>
        lq.pure(new Lambda(param, body))
    )
);
// 条件分岐
var ifThenElse = tp.reserved("if").then(expr).bind(cond =>
    tp.reserved("then").then(expr).bind(conseq =>
        tp.reserved("else").then(expr).bind(alt =>
            lq.pure(new IfThenElse(cond, conseq, alt))
        )
    )
);
// 変数束縛
var letIn = tp.reserved("let").then(identifier).bind(name =>
    tp.reservedOp("=").then(expr).bind(bound =>
        tp.reserved("in").then(expr).bind(body =>
            lq.pure(new LetIn(name, bound, body))
        )
    )
);

// プログラム (前後の空白を無視)
var program = tp.whiteSpace.then(expr).left(lq.eof);

// パース関数
function parse(src) {
    var res = lq.parse(program, "", src, 8);
    if (res.succeeded) {
        return res.value;
    }
    else {
        throw new SyntaxError(res.error.toString());
    }
}

// 定義済み関数
var prelude = Object.create(null);
prelude["neg"] = x => -x;

prelude["add"] = x => y => x + y;
prelude["sub"] = x => y => x - y;
prelude["mul"] = x => y => x * y;
prelude["div"] = x => y => x / y;
prelude["mod"] = x => y => x % y;

prelude["eq"] = x => y => x === y;
prelude["notEq"] = x => y => x !== y;

prelude["lt"] = x => y => x < y;
prelude["ltEq"] = x => y => x <= y;
prelude["gt"] = x => y => x > y;
prelude["gtEq"] = x => y => x >= y;

prelude["not"] = x => !x;
prelude["and"] = x => y => x && y;
prelude["or"] = x => y => x || y;

// 試してみる
var src1 = `
(* 2 と 3 の大きい方を求める *)
let max =
    fun x -> fun y ->
        if gt x y then x
        else y
in max 2 3 (* 3 *)
`;
var ast1 = parse(src1);
console.log(ast1.eval(prelude)); // -> 3

var src2 = `
(* 10 の階乗 *)
let fact =
    fun n ->
        if gt n 0 then mul n (fact (sub n 1))
        else 1
in fact 10
`;
var ast2 = parse(src2);
console.log(ast2.eval(prelude)); // -> 3628800