皆様、お久しぶりです。去る2月10日(土)、2月11日(日)に筑波大学情報科学類にて特別講義の講師をやってきました。といっても、私が全日担当したわけではなくOB一人が一コマを自分の得意分野について講義をするオムニバス形式のものです。
私はといえば去年やったのと同様、JavaScriptで抽象構文木を「手で」組み立てて解釈・実行するプログラミング言語Minisとその処理系を作るという講義を行いました。講義当日はスライドにミスがあることに途中で気づいたり色々あってテンパりましたがそれはそれとして。
元々、私が担当した「プログラミング言語作成概論」の趣旨は
プログラミング言語を作るというのはとても簡単な作業なのに、プログラマにすらあまり知られていないのはけしからん。
とはいえ、実際に作ってみせないと実感が湧かないのが人情。
抽象構文木をJavaScript上で組み立てて、それをevalする関数を書くことを通してインタプリタの作成方法を学ぼうじゃないか!
的なものです。たとえば、以下のプログラムは講義で作ったプログラミング言語Minisのもの(実際にはこれそのものを解析する構文解析機はまだ作ってませんが)です。MinisのことはわからなくてもC系言語を一つかじったことがあればおおよその意味はわかるかと思います。
a = 100;
b = 200;
if(a < b) {
500;
} else {
1000;
} // 500が返ってくる
しかし、これくらい単純な構文を持ったプログラミング言語でさえ「構文解析」というプログラミング言語にとって本質でないものが挟まるせいで無駄に行数が増えるのが現実です。ならばということで、以下のように直接抽象構文木を書かせれば(ナイーヴな)インタプリタの本質であるevalの記述に専念できるじゃあないかというのが講義を通して伝えたかったことでした。
const expression = tSeq(
tAssign('a', tInt(100)),
tAssign('b', tInt(200)),
tIf(tLt(tId('a'), tId('b')), tInt(500), tInt(1000)),
); // 上のプログラムをJSの関数呼び出しを通して構築したもの
expect(evaluate(expression, {})).toBe(500);
さて、多少プログラミング言語に心得のある皆様ならおわかりのようにこのアプローチは問題なく機能しますが、ただ、せっかくプログラミング言語を作ったのだから構文も設計したいのが人情です。比喩でいえば GUIかCUIかはプログラムの本質ではないけど、GUIの方が結果がわかりやすくていいよねみたいな。
というわけで今年は具象構文も追加することにしたのですが、しかし、構文解析の話をするには時間もありませんし、概念を理解するのも結構手間です(難しいものではないですが)。というわけで間をとってJSONでMinisの構文を書けるようにしたのでした。たとえば、上記のプログラムをMinisのJSON形式で記述すると以下のようになります:
{
"type": "seq",
"expressions": [
{"type": "assign", "name": "a", "value": 100},
{"type": "assign", "name": "b", "value": 200},
{"type": "if",
"condition": {"type": "<", "operands": [{"type": "id", "name": "a"}, {"type": "id", "name": "b"}]},
"then": 500,
"else": 1000
}
}
しかし、見ればわかる通り、元の抽象構文木をそのまま書き下したときより見づらくなってしまっています。
このJSON形式の構文を書き下したのは講義よりしばらく前でしたが、これだとちっとも嬉しくない……というわけで、JSONはJSONでももっと簡潔に書けるように考え直しました。
上記のJSON形式の問題点はすべての式をJSONのオブジェクト(あるいは値)として表現してしまっているせいで、必ずラベルが必要になる点です。しかし、よくよく考えればJSONを使うからといって別にオブジェクトを使う必要はないわけで、以下のように配列形式でいいわけです。
[
["assign", "a", 100],
["assign", "b", 200],
["if", ["<", ["id", a"], ["id", "b"]]
500,
1000]]
かなりMinisのプログラムを簡潔に書けるようになりました。と、ここで「それってほとんどS式では?」というツッコミが聞こえてきそうですが、概ねその通りです。強いていうとS式と違ってJSONにはシンボルがプリミティブにないために、余計なダブルクオートが必要になる程度でしょうか。
ともあれこのようにしてJSONでプログラムを表現してあげれば、後は簡単。JSON.parse(str)
で入力文字列をJSONとしてパーズした後は、抽象構文木に変換するロジックさえ書いてあげれば既存のMini言語に具象構文を与えることができます。
プログラミング言語Minisはナイーヴなインタプリタや上記のJSON構文を解釈できるものも含め、以下のリポジトリからソースを取得することができます。もし興味が湧いたら触っていただければと思います。単純な言語とはいえどこかにバグがある気もするので、バグ報告も歓迎します。ではでは。
github.com