[Java] Kinx Library-Parser Combinator (Part 2)

12 minute read

Kinx Library-Parser combinator (Part 2)

Introduction

The script language Kinxdeliveredby”“ItlookslikeJavaScript,thebrain(contents)isRuby,(stabilityisAC/DC)”). This time is also a parser combinator.

Last time, I did it up to making AST with Kinx library-Parser combinator (1).

This time I will interpret this and execute it. At the end, I will compile and execute JIT.

before that

review

Let’s reconfirm the final program from last time.

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

This. Let’s fix one problem with this. It’s not a problem, though.

Actually, this parser fails if there is a space character. Of course, there is no place to interpret white space, so it is not the character that you expect to encounter white space, and you will be confidently answering “There is no grammar!”

Skipping whitespace characters

In normal programming languages, token breaks are any number of whitespace characters, and whitespace is commonly skipped. Therefore, let’s skip the white space character. There are two things to use there.

  • $.optWhitespace is a parser that interprets zero or more arbitrary whitespace characters. Specifically, it is the same as $.regex(/\s*/). Therefore, it matches blanks, line breaks (CR/LF), and tabs. There is also $.whitespace, which uses $.regex(/\s+/) to match one or more whitespace characters.
  • parser.skip(anotherParser) tries to match parser, then anotherParser, and if so, returns the result of parser. That is, skip the match result of anotherParser.

These two can be used to skip whitespace characters after a particular parser match with .skip($.optWhitespace).

Here, prepare a function called lexeme() as shown below and add a process to skip whitespace characters. Define ignore so that you can add it here when there are more things to ignore, and skip whitespace at the beginning.

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

This lexeme() function only needs to be at the break between tokens, so it is all right if it is in the minimum unit parser of number, addsub, muldiv, lbr, and rbr. If you rewrite the first program, it will be as follows.

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
        }
    }
}
*/

Both return the same result.

The first ignore.then() is the part that ignores leading white space. parser.then(anotherParser) returns anotherParser, unlike .skip(). This causes parser to be ignored.

Now let’s get into the main subject.

Interpreter

First, let’s implement the interpreter before JIT. This is easier. The interpreter traverses the AST and executes it serially. Evaluate the left side, evaluate the right side, and operate on the result. The Interpreter class looks like this:

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

I tried to make the calculation process visible (passing { enableSequence: true } to the constructor will display the calculation process). Let’s run it like this.

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

It is calculated according to the priority order properly! Not surprisingly, because AST is built according to priority. Let’s try another formula.

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

There is.

JIT compilation

I’m looking forward to JIT. However, JIT technology itself is wonderful, but please understand that the above interpreter is honestly faster at this level of computational complexity (no loops or conditional branches). JIT compilation time is like interpreter time (+α) because it is compiling with the same route as the interpreter and the interpreter itself does not do much. Mumu.

It’s just a technology base. I wish I could have made an example where the difference in speed was even greater. Will you rewrite Brainf*ck with the article of here next time?

Now, in Interpreter, we executed the calculation formula directly, but it is OK if we rewrite it so that the equivalent machine language code is output instead of executing the calculation. Looking at JIT library, the Compiler class that converts to machine language code will be as follows. It’s a little long, but I will post it as it is. Again, you can output the intermediate format compile code by setting { enableListing: true } in the constructor.

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();
    }
}
```Registers are available from `R2` to `R5` and `S0` to `S5`. We need to save `R0` and `R1` because we need to use them for division. The register allocation method is "Reserve when using, and return when using".

Note that the `R` series registers may be destroyed after the function is called, but this time it is possible to handle it in the same way as the `S` series, since it only calculates and does not call the function. An error will occur if all available registers are used up, but many intermediate values are short-lived, so this should not be a problem. If the value to be saved increases, we will issue a code to save it in memory. Also, the Kinx JIT library can have a local variable area on the stack, so it's easiest to allocate to it when there is not enough space.

It is quite deep considering register allocation in earnest, but in JIT it is the theory that **it does not take much time for optimization**, so this level is enough. Because the optimization time is wasted. In the case of pre-compilation (AOT Compilation), you don't have to worry about the compile time, and the faster the run time is, the faster the optimization is.

Let's calculate now. Don't forget `using Jit;`.

```javascript
using Parsek;
using Jit;

/* omitted */
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
*/

There is. Let’s try another example.

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

There is also here.

You can also dump the actual machine code, so let’s try it.

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

Output on 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

Let’s roughly read and understand.

  • The prologue is up to the 0xe line.
  • At line 0x12, assign 0x01 to the rdi register
  • At line 0x19, assign 0x02 to the rcx register
  • At line 0x20, assign 0x03 to the r8 register
  • At line 0x27-0x2a, assign the result of rcx * r8 to the r11 register
  • At line 0x2e, assign the result of rdi + r11 to the rcx register
  • At line 0x32, assign 0x02 to the rdi register
  • At line 0x39, assign 0x0e to the r8 register
  • At line 0x40-0x4a, assign the result of r8-r11 to rbx register
  • At line 0x4d-0x50, assign the result of rdi * rbx to r8 register
  • At line 0x54, assign the result of rcx + r8 to the rdi register
  • At line 0x58, assign rdi to rax register
  • From line 0x5b, it is the epilogue.

The return value of the function is determined to be the rax register on x64, so this returns the result.

So in another example.

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

This is also the output on 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, rdi23:   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」、ですね。

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