この記事は OUCC Advent Calendar 2015 の 13 日目の記事です. 昨日は @yuntan_t 氏による ~~量子力学~~ matplotlibで図を描く，保存する，アニメーションさせるでした.

さて, 今年 (というか去年の後半から) は何かと言語実装に縁があり, まとめると大体以下のようなことをしていました.

というわけで, 折角なので JavaScript で簡単な言語処理系の実装についての解説を書こうと思います. 簡単のためにいくつか ES 2015 の機能を使うので, Node.js の最新版を想定していますが, そうでない環境や他の言語で実装したいという人は適当に読み替えてください.

Google 先生もご存知の通り, 言語処理系にはインタプリタとコンパイラがあって, この記事では抽象構文木 (abstract syntax tree, 以下 AST) インタプリタを実装します. バイトコードインタプリタやコンパイラを作りたいという人は, 残念ながら私に知識が無いので, 他のそっち系に詳しい人に聞いてください.

f:id:susisu:20151213171711p:plain (Sketch の練習のためだけに作った図です.)

文法

まずは文法を定義しましょう. ここでは ML ライクな構文を採用します (ただし処理系は動的型付けです).

# 式 = プログラム
expr ::=
      application
    | literal
    | variable
    | if-then-else
    | let-in
    | "(" expr ")"
fexpr ::=
      application
    | literal
    | variable
    | "(" expr ")"
aexpr ::=
      literal
    | variable
    | "(" expr ")"
# 関数適用
application ::= fexpr aexpr
# リテラル
literal ::= number | boolean
# 数値
number ::= (なんか数値の定義)
# 真偽値
boolean ::= "true" | "false"
# 変数
variable ::= identifier
# 識別子
identifier ::= (なんか識別子の定義)
# ラムダ式 (匿名関数)
lambda ::= "fun" identifier "->" term
# 条件分岐
if-then-else ::= "if" term "then" term "else" term
# 変数束縛
let-in ::= "let" identifier "=" term "in" term

この文法では, 例えば次のようなプログラムが書けます.

(* 2 と 3 の大きい方を求める *)
let max =
    fun x -> fun y ->
        if gt x y then x
        else y
in max 2 3 (* 3 *)

AST

パーサを書くにも評価 (= 計算の実行) 部分を書くにも, まずは AST の表現を決めておく必要があります.

というわけで, 次のように文法と対応する AST を表現するクラスを定義します.

// 式 = プログラム の基底クラス
class Expr {
}

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

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

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

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

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

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

これらを使うと, 上に挙げたプログラム例は次のようなオブジェクトとして表すことができます.

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

見た目はエグいですが, どうせパーサを書くので, これを手書きするわけではないので安心してください.

パーサ

次に, 文字列として与えられるソースコードを AST に変換するパーサを書きます (字句解析器 (lexical analyzer, lexer) と構文解析器 (parser) に分けられますが, この記事ではまとめてパーサと呼びます).

構文解析器は PEG.js などのパーサジェネレータを使うか, Parsimmon や Loquat (拙作) などのパーサコンビネータを使って書くのが楽だと思います.

が, 正直これについて詳しく書くととんでもない長さになってしまいそうなので, ここでは詳細な説明は省きます.

Loquat (npm install loquat でインストール) の場合, 字句解析器は以下のようにちょちょいのちょいと書けます.

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 src = `
(* 2 と 3 の大きい方を求める *)
let max =
    fun x -> fun y ->
        if gt x y then x
        else y
in max 2 3 (* 3 *)
`;
console.log(require("util").inspect(
    parse(src),
    { colors: true, depth: null }
));

たぶんうまくいくはずです. めでたいですね.

評価

次に AST の評価 (evaluation) 部分を, Expr クラスのメソッドとして実装していきます.

とりあえず基底クラスにはエラーを返すように実装しておきましょう

class Expr {
    eval(env) {
        throw new Error("unknown expression");
    }
}

引数の env は環境と呼ばれるもので, 簡単に言えば「変数の辞書」です. ここでは単なる JavaScript のオブジェクトだと思いましょう.

リテラルの評価は, 特に変わったことはせず, 持っている値を返すだけです.

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];
    }
}

ラムダ式は後で説明するとして, 先に関数適用の評価を実装します.

関数適用は, まず関数 func と引数 arg を評価して, 次にそれらを用いた結果を返すようにすれば OK です.

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

条件分岐も同様に, 条件 cond をまず評価し, true なら conseq を, false なら alt を評価した結果を返せばよいです.

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

続いて変数束縛です. 変数束縛では, まずローカルな環境 (スコープ) を Object.create() を用いて作成し, その中で束縛される式を評価した後, 同じくローカルな環境内で本体を評価して, その結果を返します. JavaScript のオブジェクトのプロトタイプチェインを, そのままスコープチェインとして使えるので便利ですね.

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

ちなみに, 束縛される式を外側のスコープで評価すると Scheme や ML の let, ローカルなスコープで評価すると letrec あるいは let rec に近い実装になります. 後で再帰関数を定義したいので, ここでは let rec の方を採用しました.

最後にラムダ式です. ラムダ式の評価結果は関数で, 呼びだされた時に let と同様にローカルな環境を作り, 引数を束縛してから本体の評価を行うようにします.

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

この時, 少しわかりづらいですが, ラムダ式の評価結果の関数は, ラムダ式自体の情報 (this.body など) と, 評価された時の環境 env の組を持っていて, こういったものをクロージャと呼びます. これによってレキシカルスコープが実現できるわけですね.

ちなみにちなみに, ここでは結果の関数は 1 つの引数のみをとりますが, 関数適用の際に, 本体を評価するための環境を引数として渡してやるようにすればダイナミックスコープにもできます. そんなことしませんが.

さて, お気づきの方も多いと思いますが, これで評価部分の実装が終わりました.

✲ﾟ｡.(✿╹◡╹)ﾉ☆.｡₀:ﾟ✲ﾟ:₀｡

定義済み関数

というわけで評価部分までできましたが, これだけでは数値や真偽値に対する計算ができないので, 最後にいくつか定義済みの関数を用意しておきましょう.

面倒だったので型エラーまでは用意していませんが, まあ変な値を入れても数値か真偽値のどちらかにはなるので, とりあえずこれで良いでしょう.

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 src = `
(* 2 と 3 の大きい方を求める *)
let max =
    fun x -> fun y ->
        if gt x y then x
        else y
in max 2 3 (* 3 *)
`;
var ast = parse(src);
console.log(ast.eval(prelude)); // -> 3

うまく動いているようです.

続いて再帰関数も試してみましょう.

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

✌(’ω’✌ )三✌(’ω’)✌三( ✌’ω’)✌