LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Kray-G

Kinx で ModanShogi 実装してみた

Posted at

はじめに

新年明けましておめでとうございます。本年もよろしくお願いいたします。

さて、「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinxですが、今年も何卒ご贔屓頂ければ幸いです。

今回は言語処理系を作るシリーズその１。

パーサー・コンビネータ作ったし、JIT ライブラリも作ったので言語処理系作りたいですよね。今回が最初で最後かもしれないですけど。以前簡単な電卓作りましたがもうちょっと高度なものに挑戦してみるシリーズです。

尚、今まで隠してましたが私、実は将棋ファンです。羽生さんは神です。講演会も聞きに行きました。

ModanShogi を作る

一昔前に ModanShogi というのが流行りました。ちなみにここで言うモダンは決して「現代的」という意味ではなく、モダン焼き のモダンなので注意です。モダン焼きのモダンは**「盛りだくさん」**という意味だそうです。スペルも違います。

ソースコード

実はかなり前に作っていて、examples フォルダに忍ばせてあります。以下でソース全体を見ることができます。

そして、下にも書きましたが コンパイル版で実数のサポートを忘れていることにこの記事を書いて気がつきました。たぶんそのうち直します。あらかじめご了承ください。

今回はこれを上から解説してみようという趣旨で、ついでに自分自身の備忘録も兼ねてます。

ちなみに、これを実現するために、JIT ライブラリで下記で言うところの putc と putn が呼び出せるように細工してあることは内緒です。今後、C 関数を呼び出せるように汎用的に作り替えられればと思いますが、それまでの繋ぎです。

仕様

仕様については「ここ」を参照してください。

サンプルを上記より引用しておきます。尚、元記事がなくなってしまったときのために、一通り説明をしておきます。

ModanShogi による Hello World。

▲９八銀 △９二玉 ▲６四歩 △６六銀 ▲６一歩 △同　玉
▲６七歩 △６一玉 ▲６八玉 △６三歩 ▲６九玉 △７七銀
▲７五金 △７一玉 ▲４八銀 △４二玉 ▲９六と △９八歩
▲同　玉 △６七玉 ▲９五金 △９一玉 ▲６三金 △同　玉
▲６八金 △６二玉 ▲４一歩 △４三玉 ▲５五歩 △５三玉

文法

  • ソースコードのエンコーディングは UTF-8 でなければならない。
  • 命令は次の通り。
    • [PLAYER][COL][ROW][PIECE] (例：▲２四銀)
      • PLAYERは「▲」（⁠先手）または「△」（⁠後手）。意味は特にない。
      • ▲および△の代わりに Unicode で規定されている☗および☖も使用可能。
    • COL は全角アラビア数字の「１」から「９」。
    • ROW は漢数字の「一」から「九」。
      • COL は命令の第一引数、ROWは命令の第二引数である⁠。
      • COL およびROWが直前の命令と等しい場合には、これらをまとめて「同　」とすることができる。「⁠同」のあとは全角スペース。
    • PIECE は「香」「⁠桂」「⁠銀」「⁠金」「⁠玉」「⁠王」「⁠飛」「⁠角」「⁠龍」「⁠馬」「⁠と」。
      • PIECE は命令の種類を表す⁠。
      • PIECE としてはこの他に「成香」「⁠成桂」「⁠成銀」があり得る（ただし、これらは将来の拡張のために予約されており使用するべきではない）。
      • 将棋の棋譜としては「玉」のみを使うのが慣例。なので「王」を使用するべきではないらしい。
        • だが下記の putn を実現するためには必要。
  • ラベル
    • ラベルはジャンプ命令の飛び先として使われる⁠。
    • ラベルは *N (例：*1) の形式。
      • N は 1 以上の任意の自然数を、半角アラビア数字で表記したものである。

動作環境

ModanShogi プログラムは以下のような仮想的マシン上で実行される。

  • レジスタ

    • レジスタは 9 個あり、これらのレジスタには 1 番から 9 番までの番号が振られている。
    • 各レジスタは 1 つの実数を保持することができる（整数だけでなく小数も保持できる⁠）⁠。
    • プログラムの開始時には、各レジスタはそのレジスタ番号と同じ値を初期値としてもつ（1 から 9 までの整数が入っている⁠）⁠。

  • スタック

    • スタックは 1 つ。
    • このスタックには実数をプッシュ・ポップできる。

命令として、以下が存在する。

PIECE 別名 COL ROW 意味
と mov X Y X = Y
歩 add X Y X += Y
金 sub X Y X -= Y
銀 mul X Y X *= Y
桂 div X Y X /= Y
香 mod X Y X %= Y
龍 push X _ X をプッシュ
馬 pop X _ X にポップ
玉 putc X _ 文字コード X の文字を出力
王 putn X _ X を数値として出力
飛 jump_if X Y X が非 0 ならレジスタ Y 番の示すラベルにジャンプ
角 jump_ifp X Y X が 0 以上ならレジスタ Y 番の示すラベルにジャンプ
  • mov 命令は、レジスタ Y 番の値をレジスタ X 番に上書きする。
  • add/sub/mul/div 命令は、レジスタ X 番と Y 番の加減乗除を行い、結果を X 番に上書きする。
    • div 命令の結果は小数になり得ることに注意。
  • mod 命令は、レジスタ X 番の値を Y 番の値で割った余りを X 番に書き込む。
  • push 命令は、レジスタ X 番の値をスタックにプッシュする。
  • pop 命令は、スタックからポップした値をレジスタ X 番に書き込む。
  • putc 命令は、レジスタ X 番の値を文字コードとしてもつ文字を標準出力に出力する。
  • putn 命令は、レジスタ X 番の値を数値として出力する。
  • jump_if 命令は、レジスタ X 番の値が 0 以外ならレジスタ Y 番の値をもつラベルにジャンプする（ジャンプ先のラベルの直後の命令から実行を続ける⁠）⁠。
  • jump_ifp 命令は、レジスタ X 番の値が 0 以上だった場合にジャンプする。

実装編

さて、ここから実装です。一般的に、言語処理系の動作は以下のようになります。

  • 構文解析して、中間言語にして、インタプリタで実行
  • 構文解析して、中間言語にして、ターゲット向けにコンパイルして、実行

ざっくりです。細かく言うと字句解析とか意味解析とか最適化とかいっぱいキーワードがありますが、今回は必要ないので上の流れにそって行きます。

パーサーを作る

さて、上記仕様を満たすようにまずはパーサーを作りましょう。基本的には、先ほどのソース の順で説明していきます。

ライブラリのロード

まず、必要なライブラリをロードします。以下の 2 つです。

using Parsek;
using Jit;

定数

次に、ModanShogi の各命令などの定数を定義しておきましょう。コード出力（ダンプ）のために文字列としても定義しておきます（使ってないけど）。

enum {
    label = 0,
    mov,
    add,
    sub,
    mul,
    div,
    mod,
    push,
    pop,
    putc,
    putn,
    jump_if,
    jump_ifp,
}

var opname = [
    "label",
    "mov",
    "add",
    "sub",
    "mul",
    "div",
    "mod",
    "push",
    "pop",
    "putc",
    "putn",
    "jump_if",
    "jump_ifp",
];

内部表現へのコンバータ

次はコンバータです。何をコンバートするかというと、文法解釈して得た値を内部表現にコンバートします。オペコードと引数の組み合わせにします。

class Converter {
    var map_ = [
        { '▲': 0, '△': 1, '☗': 0, '☖': 1 },
        { '１': 1, '２': 2, '３': 3, '４': 4, '５': 5, '６': 6, '７': 7, '８': 8, '９': 9, '同': 0 },
        { '一': 1, '二': 2, '三': 3, '四': 4, '五': 5, '六': 6, '七': 7, '八': 8, '九': 9, '　': 0 },
        { 'と': mov, '歩': add, '金': sub, '銀': mul, '桂': div, '香': mod,
          '龍': push, '馬': pop, '玉': putc, '王': putn, '飛': jump_if, '角': jump_ifp },
    ];
    var prev_;
    public convert(stmt) {
        # System.println(stmt);
        var r = stmt.map { => map_[_2][_1] };
        if (r[1] == 0) r[1] = prev_[1];
        if (r[2] == 0) r[2] = prev_[2];
        prev_ = r;
        return {
            r1: r[1],
            r2: r[2],
            op: r[3],
        };
    }
}

同　 を扱うためにひとつ前の状態（prev_）を保持しておくようにしています。

文法定義

さて、お待ちかねの文法定義です。パーサー・コンビネータは字句解析部分もある意味包含されているので楽ですね。

重要なのは以下の 2 つだけで、それ以外は読み飛ばします。

  • [PLAYER][COL][ROW][PIECE] ... 操作
  • *N ... ラベル

まず、読み飛ばすところから。基本的には先頭に来る文字までの要素を読み飛ばしますので、「*▲△☗☖」以外を読み飛ばせば OK です。

var conv = new Converter();
var $ = new Parsek();
var ignore = $.noneOf("*▲△☗☖").many();
var lexeme = &(p) => p.skip(ignore);

次に操作を表すシンタックスを書いてみましょう。こんな感じです。説明には書いてませんでしたが、「同　金左」など「上右左直」の表現も受け付けられるようにしておく必要があるようです（どこかに書いてあったのだが見付からず…）。

#   [PLAYER][COL][ROW][PIECE]
#   (例：▲２四銀)
var player = $.oneOf('▲△☗☖');
var col = $.oneOf('１２３４５６７８９同');
var row = $.oneOf('一二三四五六七八九　');
var piece = $.oneOf('歩香桂銀金玉王飛角龍馬と');
var addc = $.oneOf("上右左直");

次はラベルです。ラベルはオペコードとして label を持ち、指定された番号を address として保持しておきます。

なお、今更ながら分かりづらいですが、address はラベルの番号のことです。

var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var labelp = lexeme($.seq($.string('*'), number)).map { => { op: label, address: _1[1] } };

操作かラベルのどちらかが現れれば良いので、それをプログラムとすると以下のようにプログラムを表現できます。

var stmt = lexeme($.seq(player, col, row, piece)).map { => conv.convert(_1) };
var program = $.alt(stmt, labelp).many();

上記 program は以下を表現しています。

  • 操作（stmt）は先ほど作ったコンバータに引き渡して内部表現に変換しておきます。
  • （stmt と labelp のどちらか）が　0 回以上繰り返される。

インタプリタを作る

さて、インタプリタを作ってみましょう。先ほどのルールに従って VM を表現します。ただし、先にジャンプ先のアドレスだけ解決しておきます。以下のようになっています。

  • まず（stack）スタックを用意します。
  • 次にレジスタ（reg）を用意します。
  • ジャンプ先アドレスを格納した配列を作成しておきます。
  • インタプリタとして命令を逐次実行します。
class Interpreter(opts_) {
    private setJumpAddress(code) {
        var address = [];
        for (var i = 0, l = code.length(); i < l; ++i) {
            if (code[i].op == label) {
                address[code[i].address] = i;
            }
        }
        return address;
    }
    public eval(code) {
        var stack = [];
        var reg = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        var address = setJumpAddress(code);
        for (var i = 0, l = code.length(); i < l; ++i) {
            var { op, r1, r2 } = code[i];
            # System.println([opname[op], r1, r2]);
            switch (op) {
            case label: # nop
                break;
            case mov:
                reg[r1] = reg[r2];
                break;
            case add:
                reg[r1] += reg[r2];
                break;
            case sub:
                reg[r1] -= reg[r2];
                break;
            case mul:
                reg[r1] *= reg[r2];
                break;
            case div:
                reg[r1] /= reg[r2];
                break;
            case mod:
                reg[r1] %= reg[r2];
                break;
            case push:
                stack.push(reg[r1]);
                break;
            case pop:
                reg[r1] = stack.pop();
                break;
            case putc:
                if (!opts_.disableDisplay) {
                    System.print(*Integer.parseInt(reg[r1]));
                }
                break;
            case putn:
                if (!opts_.disableDisplay) {
                    System.print(reg[r1]);
                }
                break;
            case jump_if:
                if (reg[r1]) {
                    i = address[reg[r2]];
                }
                break;
            case jump_ifp:
                # System.println("check = ", reg[r1]);
                if (reg[r1] >= 0) {
                    i = address[reg[r2]];
                }
                break;
            }
        }
    }
}

先ほどのルールを再掲しますので、実装と合っているか確認してみると理解が進むでしょう（PIECE はインタプリタ上では既に消滅していますが）。

PIECE 別名 COL ROW 意味
と mov X Y X = Y
歩 add X Y X += Y
金 sub X Y X -= Y
銀 mul X Y X *= Y
桂 div X Y X /= Y
香 mod X Y X %= Y
龍 push X _ X をプッシュ
馬 pop X _ X にポップ
玉 putc X _ 文字コード X の文字を出力
王 putn X _ X を数値として出力
飛 jump_if X Y X が非 0 ならレジスタ Y 番の示すラベルにジャンプ
角 jump_ifp X Y X が 0 以上ならレジスタ Y 番の示すラベルにジャンプ

コンパイラを作る

では次にコンパイラの実装です。

この記事を書いてて気づきましたが、実数をサポートしてませんね。後で直そう...

コンパイラは Jit ライブラリでネイティブ・コードにコンパイルします。同じようにジャンプ先のアドレス解決を先にしておきます。インタプリタよりはややこしいですね。特にジャンプアドレスの解決方法は多少トリッキーです。これは、言語仕様上レジスタ値による間接ジャンプなので、コンパイル時点で飛び先がわからないためです。あらかじめラベル番号に応じたジャンプ先をテーブルの形で保持しておいて、実行時にテーブル参照してジャンプします。

  • まず、コンパイラ（Compiler）を用意して関数の入り口（enter）を作ります。
  • 次にラベル保持用とジャンプ先用の配列を用意します。
  • ジャンプ先アドレス解決用の配列を作成しておきます。これは変数領域をあらかじめ作っておいて、後からアドレスを入れられるようにしておく、という準備をしています。
    • Jit.VAR(n) は変数領域です。
    • makeConst という命令は、Jit.VAR(n) で示した n 番目の変数領域に対するアドレスを保持したオブジェクトを返します。
    • 最後のところで setLabel(label) で、そのアドレスにラベル自体の（既にコード生成後の解決済）アドレスを差し込む、といったことをしています。
    • ジャンプする際は、該当する変数領域からアドレスを取得して、そこにジャンプします。
  • 次にレジスタ（reg）を用意します。S5 レジスタはスタックポインタとして使うので、使えるレジスタは S0 ～ S4 です。それだけでは足りないので、一部メモリ（変数領域）を使うようにしています。
  • VM のレジスタの値を初期化します。（初期値はレジスタの番号と同じ値）
  • JIT ライブラリの S5 レジスタ（用語が重複してて紛らわしいな）にスタックポインタの初期値（max + 5）を設定します。
    • max までは先ほどのジャンプ先格納領域です。
    • max + 4 までは ModanShogi の不足していた VM 用のレジスタ領域です。
  • スタック領域を確保します。max + 5 まで使っているので、さらに 1000 足します。
    • スタック領域は（1000 要素分＝8000 バイト分）です。
    • そのアドレスに値を設定することで、自動的に変数領域がそこまで使えるように確保されることを利用しています。
  • 命令列に従ってコンパイルします。
  • コード生成後に、先ほどのジャンプ先アドレスをすべて解決させます。
class Compiler(opts_) {
    private setJumpAddress(code, c) {
        var address = [], max = 0;
        for (var i = 0, l = code.length(); i < l; ++i) {
            if (code[i].op == label) {
                address[i] = c.makeConst(Jit.VAR(code[i].address));
                max = code[i].address if (max < code[i].address);
            }
        }
        return [address, max];
    }
    public compile(code) {
        var c = new Jit.Compiler();
        c.enter();

        var jt;
        var labelTarget = [];
        var jumpTarget = [];
        var [address, max] = setJumpAddress(code, c);
        var reg = [-1, Jit.VAR(max+1), Jit.VAR(max+2), Jit.VAR(max+3), Jit.VAR(max+4), Jit.S0, Jit.S1, Jit.S2, Jit.S3, Jit.S4];
        for (var i = 1, l = reg.length(); i < l; ++i) {
            c.mov(reg[i], Jit.IMM(i));
        }
        c.mov(Jit.S5, Jit.IMM(max+5));
        c.mov(Jit.VAR(max+1005), Jit.IMM(0));
        for (var i = 0, l = code.length(); i < l; ++i) {
            var { op, r1, r2 } = code[i];
            # System.println([opname[op], r1, r2]);
            switch (op) {
            case label:
                labelTarget[i] = c.label();
                break;
            case mov:
                c.mov(reg[r1], reg[r2]);
                break;
            case add:
                c.add(reg[r1], reg[r1], reg[r2]);
                break;
            case sub:
                c.sub(reg[r1], reg[r1], reg[r2]);
                break;
            case mul:
                c.mul(reg[r1], reg[r1], reg[r2]);
                break;
            case div:
                c.mov(Jit.R0, reg[r1]);
                c.mov(Jit.R1, reg[r2]);
                c.div();
                c.mov(reg[r1], Jit.R0);
                break;
            case mod:
                c.mov(Jit.R0, reg[r1]);
                c.mov(Jit.R1, reg[r2]);
                c.divmod();
                c.mov(reg[r1], Jit.R1);
                break;
            case push:
                c.mov(Jit.R1, Jit.S5);
                c.localp(Jit.R0, Jit.R1);
                c.mov(Jit.MEM1(Jit.R0), reg[r1]);
                c.add(Jit.S5, Jit.S5, Jit.IMM(1));
                break;
            case pop:
                c.sub(Jit.S5, Jit.S5, Jit.IMM(1));
                c.mov(Jit.R1, Jit.S5);
                c.localp(Jit.R0, Jit.R1);
                c.mov(reg[r1], Jit.MEM1(Jit.R0));
                break;
            case putc:
                if (!opts_.disableDisplay) {
                    c.mov(Jit.R0, reg[r1]);
                    c.icall(Jit.IMM(Jit.Clib.putc));
                }
                break;
            case putn:
                if (!opts_.disableDisplay) {
                    c.mov(Jit.R0, reg[r1]);
                    c.icall(Jit.IMM(Jit.Clib.putn));
                }
                break;
            case jump_if:
                jt = c.eq(reg[r1], Jit.IMM(0));
                c.mov(Jit.R1, reg[r2]);
                c.localp(Jit.R0, Jit.R1);
                c.mov(Jit.R0, Jit.MEM1(Jit.R0));
                c.ijmp(Jit.R0);
                jt.setLabel(c.label());
                break;
            case jump_ifp:
                jt = c.slt(reg[r1], Jit.IMM(0));
                c.mov(Jit.R1, reg[r2]);
                c.localp(Jit.R0, Jit.R1);
                c.mov(Jit.R0, Jit.MEM1(Jit.R0));
                c.ijmp(Jit.R0);
                jt.setLabel(c.label());
                break;
            }
        }

        c.ret(Jit.R0);
        var code = c.generate();
        address.each {
            if (_1) _1.setLabel(labelTarget[_2]);
        };
        return code;
    }
}

実行部分

インタプリタとコンパイラが揃ったので、実際にソースコードをパースして実行する部分を書きましょう。サンプルのコメントアウトは無視して、以下の棋譜を読み込ませます。

var kifu =
# Hello, world!
%{
    ▲９八銀 △９二玉 ▲６四歩 △６六銀 ▲６一歩 △同　玉
    ▲６七歩 △６一玉 ▲６八玉 △６三歩 ▲６九玉 △７七銀
    ▲７五金 △７一玉 ▲４八銀 △４二玉 ▲９六と △９八歩
    ▲同　玉 △６七玉 ▲９五金 △９一玉 ▲６三金 △同　玉
    ▲６八金 △６二玉 ▲４一歩 △４三玉 ▲５五歩 △５三玉
};

以下、タイマーを使った実行時間の計測と結果の表示です。

var t, tmr = new SystemTimer();

まずは構文解析。

# Parsing the code
tmr.restart();
var r = ignore.then(program).parseAll(kifu);
t.parse = tmr.elapsed();

次にインタプリタで実行。

# Interpret it
var interp = new Interpreter();
tmr.restart();
interp.eval(r.value);
t.interpret.total = tmr.elapsed();

最後にコンパイラで実行。コンパイル・フェーズと実行フェーズに分かれます。

# Compile it
var compiler = new Compiler();
tmr.restart();
var code = compiler.compile(r.value);
t.jit.compile = tmr.elapsed();

# Execute it
tmr.restart();
code.run();
t.jit.execute = tmr.elapsed();
t.jit.total = t.jit.compile + t.jit.execute;

そして結果表示です。

System.println("Result = ", t.toJsonString(true));

ベンチマーク

ベンチマークの結果です。ひとまずここでは Linux です。

Hello, world!
Hello, world!
Result = {
    "interpret": {
        "total": 0.001682
    },
    "jit": {
        "compile": 0.000799,
        "execute": 0.00014,
        "total": 0.000939
    },
    "parse": 0.008555
}

ちゃんと Hello, world! が 2 回出ましたね！

JSON の結果が何を表しているかというと、以下のような結果を表しています。

  • 構文解析時間は約 8.5 ミリ秒。
  • インタプリタでの実行時間は約 1.7 ミリ秒。
  • コンパイル時間は約 0.8 ミリ秒。
  • コンパイル結果の実行時間は約 0.1 ミリ秒。

つまり、構文解析処理は共通なので、インタプリタとコンパイラで比較してみると以下の通りコンパイラのほうが実行時間が速くなったということですね！

実行形体 構文解析処理 実行 全体
インタプリタ 8.5 ms 1.7 ms 10.2 ms
コンパイラ 8.5 ms (0.8+0.1) 0.9 ms 9.4 ms

おわりに

題材がアレですが、先にも書いたように

  • 構文解析して、中間言語にして、インタプリタで実行
  • 構文解析して、中間言語にして、ターゲット向けにコンパイルして、実行

という流れはなんとなく掴めるのではないでしょうか。

それでは皆さんも、楽しい言語実装ライフをお楽しみください！

コンパイラで実数を扱えるようにしなくては。

ではまた。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?