Kinx ライブラリ - パーサ・コンビネータ（その2）

# Kinx ライブラリ - パーサ・コンビネータ（その2）

## はじめに

**「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」** でお届けしているスクリプト言語 [Kinx](https://github.com/Kray-G/kinx)。今回もパーサ・コンビネータです。

* 参考
    * 最初の動機 ... [スクリプト言語 KINX（ご紹介）](https://qiita.com/Kray-G/items/ca08b6fb40d15dd0ec76)
        * 個別記事へのリンクは全てここに集約してあります。
    * リポジトリ ... [https://github.com/Kray-G/kinx](https://github.com/Kray-G/kinx)
        * Pull Request 等お待ちしております。  

前回 [Kinx ライブラリ - パーサ・コンビネータ（その1）](https://qiita.com/Kray-G/items/0224128078af7554fd08) で AST を作るところまで実施しました。

今回はこれを解釈して実行させます。最後には JIT コンパイルして実行するところまでいきます。

## その前に

### おさらい

前回の最終的なプログラムを再確認しておきましょう。

```javascript
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` は無視するものが増えたときにここに追加すればよいのと、最初の出だしでも空白文字のスキップが必要なので定義しておきます。

```javascript
var ignore = $.optWhitespace;
var lexeme = &(p) => p.skip(ignore);
```

この `lexeme()` 関数は、トークンの切れ目にあれば良いので、`number`、`addsub`、`muldiv`、`lbr`、`rbr` の最小単位のパーサーにあれば良いですね。最初のプログラムを書き換えると次のようになります。

```javascript
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` クラスは以下のようになります。

```javascript
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 }` を渡すと計算過程を表示します）。こんな感じで実行してみましょう。

```javascript
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 が優先順位の通りに構築されているので当然です。別の式でもやってみましょう。

```javascript
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コンパイル時間がインタプリタ時間（＋α）みたいなものになってしまってます。むむ。

あくまで技術ベースということで。もっと速さに差が出る例題にすればよかったな。今度 [ここ](https://postd.cc/adventures-in-jit-compilation-part-2-an-x64-jit/) の記事を参考にして Brainf*ck を題材に書き直すか。

さて、`Interpreter` では直接計算式を実行してましたが、計算を実行する代わりに同等のマシン語コードを出力するように書き換えれば OK です。[JIT ライブラリ](https://qiita.com/Kray-G/items/a237f195630f3f0a91df) を見ながら、マシン語コードに変換する `Compiler` クラスは以下のようになるでしょう。ちょっと長いですが、そのまま載せます。今回も コンストラクタに `{ enableListing: true }` とすることで中間形式のコンパイルコードを出力できます。

```javascript
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;` を忘れずに。

```javascript
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
*/
```

あってますねー。もう一つの例もやってみましょう。

```javascript
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
*/
```

こちらもあってます。

実際のマシン語コードもダンプできるのでやってみましょう。

```javascript
var code = new Compiler()
       .compile(ignore.then(expression)
                      .parseAll("  1 + 2 * 3 + 2 * ( 14 - 2 )  ").value);
code.dump();
System.println(code.run());
```

Linux での出力です。

```nasm
       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` レジスタと決まっているので、これで結果が返ります。

ではもう一つの例で。

```javascript
var code = new Compiler()
       .compile(ignore.then(expression)
                      .parseAll("(( 123 ) * 2 * 4 - 3 * ( 12 + 10 )) % 100").value);
code.dump();
System.println(code.run());
```

こちらも Linux での出力です。

```nasm
       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](https://github.com/Kray-G/kinx) もそうです。ただ、やってることは上記と大差ありません。どちらかというと、`Compiler` と似たようなことをやって、独自の `Interpreter` で実行する、といった感じですね。ネイティブなマシン語コードに変換できれば `Intrpreter` は不要です。普通は多倍長演算とかクラス・オブジェクトとかを扱うし、動的型付け言語は型が実行時まで分からないので、マシン語にコンパイルするのが面倒なだけです。特に、x64(Windows/Linux)/ARM とか色々対応しようとするとそれぞれごとにコンパイラを作らなくてはなりません。なのでバイトコード化がベスト・プラクティスな感じではあります。

そうは言っても本気のプロダクトは JIT 頑張ってますよね。[Kinx](https://github.com/Kray-G/kinx) も native 関数などで一部 JIT 化可能です。しかも抽象化アセンブラ（SLJIT）で表現可能な範囲で実現しているので、基本的には色々なプラットフォームへの移植性は高いはず。

いずれにしても、JIT は言語処理系では昔からホットな話題なので、[Kinx](https://github.com/Kray-G/kinx) の JIT ライブラリはちょっとしたオモチャとしては楽しいかなー、と自画自賛してます。しかも今回頑張ってパーサ・コンビネータなんて実装してしまったので、手軽に独自の DSL とか作ったりできるのではないでしょうか。結構楽しいと思いますがいかがでしょう。

Kinx JIT ライブラリのキャッチフレーズは **「気軽に JIT」**、ですね。

ということで、では、また次回。