Kinx ライブラリ - パーサ・コンビネータ（その2）
はじめに
「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。今回もパーサ・コンビネータです。
- 参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
- 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
- Pull Request 等お待ちしております。
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
前回 Kinx ライブラリ - パーサ・コンビネータ（その1） で AST を作るところまで実施しました。
今回はこれを解釈して実行させます。最後には JIT コンパイルして実行するところまでいきます。
その前に
おさらい
前回の最終的なプログラムを再確認しておきましょう。
using Parsek;
function makeAST(first, rest) {
var expr = first;
for (var i = 0, l = rest.length(); i < l; ++i) {
expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
}
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");
var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);
// test
System.println(expression.parseAll("1+2*3+2*(14-2)").value.toJsonString(true));
これです。これについて 1 つだけ問題点を直しておきましょう。問題というほどではないですが。
実はこのパーサー、空白文字があると失敗します。当然ですね、空白を解釈するところが無いので、空白に遭遇すると想定した文字でないため「文法あってないぜ！」と自信満々に答えてくるのです。
空白文字の読み飛ばし処理
普通のプログラミング言語では、トークンの切れ目が任意の数の空白文字になっており、空白は読み飛ばす対象であることが一般的です。そこで空白文字は読み飛ばすようにしましょう。そこで使うのが以下の 2 つです。
-
$.optWhitespaceは 0 個以上の任意の空白文字を解釈するパーサーです。具体的には$.regex(/\s*/)と同じです。したがって、空白、改行（CR/LF）、タブにマッチします。尚、$.whitespaceというのもあり、こちらは$.regex(/\s+/)で 1 個以上の空白文字にマッチします。 -
parser.skip(anotherParser)でparserにマッチした後anotherParserにマッチするか試し、マッチしたらparserの結果を返すといった動作をします。つまり、anotherParserのマッチ結果をスキップします。
この 2 つを使って、.skip($.optWhitespace) とすることで特定のパーサー・マッチングの後で空白文字を読み飛ばすことが可能になります。
ここでは以下のように lexeme() という関数を用意し、空白文字を読み飛ばす処理を追加しましょう。ignore は無視するものが増えたときにここに追加すればよいのと、最初の出だしでも空白文字のスキップが必要なので定義しておきます。
var ignore = $.optWhitespace;
var lexeme = &(p) => p.skip(ignore);
この lexeme() 関数は、トークンの切れ目にあれば良いので、number、addsub、muldiv、lbr、rbr の最小単位のパーサーにあれば良いですね。最初のプログラムを書き換えると次のようになります。
using Parsek;
function makeAST(first, rest) {
var expr = first;
for (var i = 0, l = rest.length(); i < l; ++i) {
expr = { lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
}
var $ = new Parsek();
var ignore = $.optWhitespace;
var lexeme = &(p) => p.skip(ignore);
var number = lexeme($.regex(/[1-9][0-9]*|[0-9]/)).map(Integer.parseInt);
var addsub = lexeme($.oneOf("+-"));
var muldiv = lexeme($.oneOf("*/%"));
var lbr = lexeme($.string("("));
var rbr = lexeme($.string(")"));
var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);
// test
System.println(expression.parseAll("1+2*3+2*(14-2)").value.toJsonString(true));
System.println(ignore.then(expression).parseAll(" 1 + 2 * 3 + 2 * ( 14 - 2 ) ").value.toJsonString(true));
/* Both results are the same.
{
"lhs": {
"lhs": 1,
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": 3
}
},
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": {
"lhs": 14,
"op": "-",
"rhs": 2
}
}
}
*/
どちらも同じ結果が返ります。
最初の ignore.then() が先頭の空白を無視する部分です。parser.then(anotherParser) は .skip() とは違って anotherParser のほうを返します。これによって、parser のほうが無視されます。
では、本題に入りましょう。
インタプリタ
まず JIT の前にインタプリタを実装してみましょう。こっちのほうが簡単です。インタプリタは AST をトラバースしながら逐次実行していきます。左辺を評価し、右辺を評価し、その結果で演算すれば OK。Interpreter クラスは以下のようになります。
class Interpreter(opts_) {
private sequence(r, op, lhs, rhs) {
return if (!opts_.enableSequence);
System.println("%d %s %d -> %d" % lhs % op % rhs % r);
}
public eval(ast) {
var lhs = ast.lhs.isObject ? eval(ast.lhs) : ast.lhs;
var rhs = ast.rhs.isObject ? eval(ast.rhs) : ast.rhs;
var r = 0;
switch (ast.op) {
case '+':
r = lhs + rhs;
break;
case '-':
r = lhs - rhs;
break;
case '*':
r = lhs * rhs;
break;
case '/':
r = lhs / rhs;
break;
case '%':
r = lhs % rhs;
break;
default:
throw RuntimeException('Invalid operator');
}
sequence(r, ast.op, lhs, rhs);
return r;
}
}
計算過程も見えるようにしてみました（コンストラクタに { enableSequence: true } を渡すと計算過程を表示します）。こんな感じで実行してみましょう。
System.println(
"Result = ",
new Interpreter({ enableSequence: true })
.eval(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * ( 14 - 2 ) ").value)
);
/*
2 * 3 -> 6
1 + 6 -> 7
14 - 2 -> 12
2 * 12 -> 24
7 + 24 -> 31
Result = 31
*/
ちゃんと優先順位に従って計算されてますね！ AST が優先順位の通りに構築されているので当然です。別の式でもやってみましょう。
System.println(
"Result = ",
new Interpreter({ enableSequence: true })
.eval(ignore.then(expression)
.parseAll("(( 123 ) * 2 * 4 - 3 * ( 12 + 10 )) % 100").value)
);
/*
123 * 2 -> 246
246 * 4 -> 984
12 + 10 -> 22
3 * 22 -> 66
984 - 66 -> 918
918 % 100 -> 18
Result = 18
*/
あってますねー。
JIT コンパイル
お待ちかねの JIT です。ただし、JIT 技術自体は素晴らしいのですが、正直このレベルの計算量（ループも条件分岐もない）だと素直に上記のインタプリタのほうが速いのでご了承ください。インタプリタと同じルートでコンパイルしてるのと、インタプリタ自体が大した事やってないので、JITコンパイル時間がインタプリタ時間（＋α）みたいなものになってしまってます。むむ。
あくまで技術ベースということで。もっと速さに差が出る例題にすればよかったな。今度 ここ の記事を参考にして Brainf*ck を題材に書き直すか。
さて、Interpreter では直接計算式を実行してましたが、計算を実行する代わりに同等のマシン語コードを出力するように書き換えれば OK です。JIT ライブラリ を見ながら、マシン語コードに変換する Compiler クラスは以下のようになるでしょう。ちょっと長いですが、そのまま載せます。今回も コンストラクタに { enableListing: true } とすることで中間形式のコンパイルコードを出力できます。
class Compiler(opts_) {
var regs_, regsLen_;
enum { MOV, BOP, DIVMOD, RET }
private initialize() {
regs_ = [
// Jit.R0 and Jit.R1 is used as a work register when it is division.
{ reg: Jit.R2, used: false, name: "R2" },
{ reg: Jit.R3, used: false, name: "R3" },
{ reg: Jit.R4, used: false, name: "R4" },
{ reg: Jit.R5, used: false, name: "R5" },
{ reg: Jit.S0, used: false, name: "S0" },
{ reg: Jit.S1, used: false, name: "S1" },
{ reg: Jit.S2, used: false, name: "S2" },
{ reg: Jit.S3, used: false, name: "S3" },
{ reg: Jit.S4, used: false, name: "S4" },
{ reg: Jit.S5, used: false, name: "S5" },
];
regsLen_ = regs_.length();
}
private listing(type, op, dst, op1, op2) {
return if (!opts_.enableListing);
switch (type) {
case MOV:
System.println("%s <- %s" % dst % op1);
break;
case BOP:
System.println("%s <- %s %s %s" % dst % op1 % op % op2);
break;
case DIVMOD:
System.println("R0 <- %s" % op1);
System.println("R1 <- %s" % op2);
System.println("%s <- R0 %s R1" % dst % op);
break;
case RET:
System.println("ret %s" % dst);
break;
}
}
private getReg() {
for (var i = 0; i < regsLen_; ++i) {
if (!regs_[i].used) {
regs_[i].used = true;
return i;
}
}
throw RuntimeException("Not enough register");
}
private releaseReg(i) {
regs_[i].used = false;
}
private compileLeaf(c, leaf) {
var r = getReg();
c.mov(regs_[r].reg, Jit.IMM(leaf));
listing(MOV, null, regs_[r].name, leaf);
return r;
}
private compileNode(c, ast) {
var rl = ast.lhs.isObject ? compileNode(c, ast.lhs) : compileLeaf(c, ast.lhs);
var rr = ast.rhs.isObject ? compileNode(c, ast.rhs) : compileLeaf(c, ast.rhs);
var r = getReg();
switch (ast.op) {
case '+':
c.add(regs_[r].reg, regs_[rl].reg, regs_[rr].reg);
listing(BOP, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case '-':
c.sub(regs_[r].reg, regs_[rl].reg, regs_[rr].reg);
listing(BOP, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case '*':
c.mul(regs_[r].reg, regs_[rl].reg, regs_[rr].reg);
listing(BOP, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case '/':
c.mov(Jit.R0, regs_[rl].reg);
c.mov(Jit.R1, regs_[rr].reg);
c.sdiv();
c.mov(regs_[r].reg, Jit.R0);
listing(DIVMOD, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case '%':
c.mov(Jit.R0, regs_[rl].reg);
c.mov(Jit.R1, regs_[rr].reg);
c.sdivmod();
c.mov(regs_[r].reg, Jit.R1);
listing(DIVMOD, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
default:
throw RuntimeException('Invalid operator');
}
releaseReg(rl);
releaseReg(rr);
return r;
}
public compile(ast) {
var c = new Jit.Compiler();
c.enter();
var r = compileNode(c, ast);
c.ret(regs_[r].reg);
listing(RET, null, regs_[r].name);
return c.generate();
}
public run(ast) {
var code = compile(ast);
return code.run();
}
}
レジスタは R2～R5、S0～S5 が利用可能です。R0 と R1 は除算で使う必要があるのでそのために取っておきます。レジスタの割り当て方は「使うときに予約して、使い終わったら返す」です。
尚、R 系のレジスタは関数呼び出し後に破壊される可能性がありますが、今回は演算するだけで関数呼び出しをしないので S 系と同様の扱いで良いでしょう。使えるレジスタを使い切るとエラーしますが、中間値の多くは短命なので問題ないでしょう。もし保存すべき値が増えたら、メモリへ退避させるコードを出します。また、Kinx の JIT ライブラリにはスタック上にローカル変数領域を持てるので、足りなくなったらそこに割り当てる、というのが一番楽です。
本格的にレジスタ割り付けとかを考えるとかなり奥が深いですが、JIT の場合は 最適化にはあまり時間をかけない というのがセオリーですので、この程度で十分でしょう。なぜならば、最適化の時間がもったいないからです。事前コンパイル（AOT Compilation）のときはコンパイル時間は気にせずに実行時に速ければ速いだけよいので最適化をガンガンしますが、JIT ではコンパイル時間も実行時間のうちなのでそうもいかないのです。
では早速計算させてみます。using Jit; を忘れずに。
using Parsek;
using Jit;
/* 省略 */
System.println(
"Result = ",
new Compiler({ enableListing: true })
.run(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * ( 14 - 2 ) ").value)
);
/*
R2 <- 1
R3 <- 2
R4 <- 3
R5 <- R3 * R4
R3 <- R2 + R5
R2 <- 2
R4 <- 14
R5 <- 2
S0 <- R4 - R5
R4 <- R2 * S0
R2 <- R3 + R4
ret R2
Result = 31
*/
あってますねー。もう一つの例もやってみましょう。
System.println(
"Result = ",
new Compiler({ enableListing: true })
.run(ignore.then(expression)
.parseAll("(( 123 ) * 2 * 4 - 3 * ( 12 + 10 )) % 100").value)
);
/*
R2 <- 123
R3 <- 2
R4 <- R2 * R3
R2 <- 4
R3 <- R4 * R2
R2 <- 3
R4 <- 12
R5 <- 10
S0 <- R4 + R5
R4 <- R2 * S0
R2 <- R3 - R4
R3 <- 100
R0 <- R2
R1 <- R3
R4 <- R0 % R1
ret R4
Result = 18
*/
こちらもあってます。
実際のマシン語コードもダンプできるのでやってみましょう。
var code = new Compiler()
.compile(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * ( 14 - 2 ) ").value);
code.dump();
System.println(code.run());
Linux での出力です。
0: 53 push rbx
1: 41 57 push r15
3: 41 56 push r14
5: 48 8b df mov rbx, rdi
8: 4c 8b fe mov r15, rsi
b: 4c 8b f2 mov r14, rdx
e: 48 83 ec 10 sub rsp, 0x10
12: 48 c7 c7 01 00 00 00 mov rdi, 0x1
19: 48 c7 c1 02 00 00 00 mov rcx, 0x2
20: 49 c7 c0 03 00 00 00 mov r8, 0x3
27: 49 89 cb mov r11, rcx
2a: 4d 0f af d8 imul r11, r8
2e: 4a 8d 0c 1f lea rcx, [rdi+r11]
32: 48 c7 c7 02 00 00 00 mov rdi, 0x2
39: 49 c7 c0 0e 00 00 00 mov r8, 0xe
40: 49 c7 c3 02 00 00 00 mov r11, 0x2
47: 4c 89 c3 mov rbx, r8
4a: 49 2b db sub rbx, r11
4d: 49 89 f8 mov r8, rdi
50: 4c 0f af c3 imul r8, rbx
54: 4a 8d 3c 01 lea rdi, [rcx+r8]
58: 48 89 f8 mov rax, rdi
5b: 48 83 c4 10 add rsp, 0x10
5f: 41 5e pop r14
61: 41 5f pop r15
63: 5b pop rbx
64: c3 ret
31
ざっくり読み解いてみましょう。
- 0xe 行目までがプロローグですね。
- 0x12 行目で
rdiレジスタに 0x01 を代入 - 0x19 行目で
rcxレジスタに 0x02 を代入 - 0x20 行目で
r8レジスタに 0x03 を代入 - 0x27-0x2a 行目で
r11レジスタにrcx * r8の結果を代入 - 0x2e 行目で
rcxレジスタにrdi + r11の結果を代入 - 0x32 行目で
rdiレジスタに 0x02 を代入 - 0x39 行目で
r8レジスタに 0x0e を代入 - 0x40-0x4a 行目で
rbxレジスタにr8 - r11の結果を代入 - 0x4d-0x50 行目で
r8レジスタにrdi * rbxの結果を代入 - 0x54 行目で
rdiレジスタにrcx + r8の結果を代入 - 0x58 行目で
raxレジスタにrdiを代入 - 0x5b 行目からはエピローグです。
関数の復帰値は x64 では rax レジスタと決まっているので、これで結果が返ります。
ではもう一つの例で。
var code = new Compiler()
.compile(ignore.then(expression)
.parseAll("(( 123 ) * 2 * 4 - 3 * ( 12 + 10 )) % 100").value);
code.dump();
System.println(code.run());
こちらも Linux での出力です。
0: 53 push rbx
1: 41 57 push r15
3: 41 56 push r14
5: 48 8b df mov rbx, rdi
8: 4c 8b fe mov r15, rsi
b: 4c 8b f2 mov r14, rdx
e: 48 83 ec 10 sub rsp, 0x10
12: 48 c7 c7 7b 00 00 00 mov rdi, 0x7b
19: 48 c7 c1 02 00 00 00 mov rcx, 0x2
20: 49 89 f8 mov r8, rdi
23: 4c 0f af c1 imul r8, rcx
27: 48 c7 c7 04 00 00 00 mov rdi, 0x4
2e: 4c 89 c1 mov rcx, r8
31: 48 0f af cf imul rcx, rdi
35: 48 c7 c7 03 00 00 00 mov rdi, 0x3
3c: 49 c7 c0 0c 00 00 00 mov r8, 0xc
43: 49 c7 c3 0a 00 00 00 mov r11, 0xa
4a: 4b 8d 1c 18 lea rbx, [r8+r11]
4e: 49 89 f8 mov r8, rdi
51: 4c 0f af c3 imul r8, rbx
55: 48 89 cf mov rdi, rcx
58: 49 2b f8 sub rdi, r8
5b: 48 c7 c1 64 00 00 00 mov rcx, 0x64
62: 48 89 f8 mov rax, rdi
65: 48 89 ce mov rsi, rcx
68: 48 99 cqo
6a: 48 f7 fe idiv rsi
6d: 48 89 d6 mov rsi, rdx
70: 49 89 f0 mov r8, rsi
73: 4c 89 c0 mov rax, r8
76: 48 83 c4 10 add rsp, 0x10
7a: 41 5e pop r14
7c: 41 5f pop r15
7e: 5b pop rbx
7f: c3 ret
18
計算結果もあってますね！
おわりに
通常、スクリプト言語系では AST から独自の中間形式コード（バイトコード）に変換して、それを実行します。Kinx もそうです。ただ、やってることは上記と大差ありません。どちらかというと、Compiler と似たようなことをやって、独自の Interpreter で実行する、といった感じですね。ネイティブなマシン語コードに変換できれば Intrpreter は不要です。普通は多倍長演算とかクラス・オブジェクトとかを扱うし、動的型付け言語は型が実行時まで分からないので、マシン語にコンパイルするのが面倒なだけです。特に、x64(Windows/Linux)/ARM とか色々対応しようとするとそれぞれごとにコンパイラを作らなくてはなりません。なのでバイトコード化がベスト・プラクティスな感じではあります。
そうは言っても本気のプロダクトは JIT 頑張ってますよね。Kinx も native 関数などで一部 JIT 化可能です。しかも抽象化アセンブラ（SLJIT）で表現可能な範囲で実現しているので、基本的には色々なプラットフォームへの移植性は高いはず。
いずれにしても、JIT は言語処理系では昔からホットな話題なので、Kinx の JIT ライブラリはちょっとしたオモチャとしては楽しいかなー、と自画自賛してます。しかも今回頑張ってパーサ・コンビネータなんて実装してしまったので、手軽に独自の DSL とか作ったりできるのではないでしょうか。結構楽しいと思いますがいかがでしょう。
Kinx JIT ライブラリのキャッチフレーズは 「気軽に JIT」、ですね。
ということで、では、また次回。