D言語でBrainf*ckコンパイル時コンパイラを作ろう

D言語をよくご存じの方にはもうタイトルでオチが読まれてると思いますが・・・。

Brainf*ckとは

八つの命令のみで記述するプログラミング言語です。
ご存じない方はこちらをご覧下さい。

D言語でBrainf*ckコンパイル時コンパイラを作ろう

インタプリタではありません！

文字列ミックスイン

コンパイル時に決定される文字列を、あたかもDのコードとしてそこにコピペしたように扱う機能です。

void main() {
    import std.stdio;
    mixin(`writeln("Hello World");`);
}

コンパイル時関数実行(CTFE)

D言語の面白い機能の一つ。テンプレートとか大層なものを使うまでもなく、適当に関数を書いて適当にコンパイル時に必要なところで使えば勝手にコンパイル時に計算されます。

string hoge(dchar c) {
    switch(c) {
        case '+':
            return "field[ptr]++;";
        default:
            return "";
    }
}

unittest {
    //コンパイル時に決定される！
    enum test = hoge('+');
    static assert(hoge('+') == "field[ptr]++;");
}

もうこのあたりで大体何をしたいか察してもらえると思います・・・。

組み合わせると・・・

string bfCodeToDCode(string code) {
    import std.algorithm : group, map;
    import std.range : repeat, chain;
    import std.string : join;
    import std.conv : to;
    return "import std.stdio : write, stdin; ubyte[30000] field; size_t ptr;\n"
        ~ code
            .map!((token) {
                    switch(token) {
                    case '+': return "field[ptr]++;";
                    case '-': return "field[ptr]--;";
                    case '[': return "while(field[ptr]){";
                    case ']': return "}";
                    case ',': return "field[ptr]=stdin.byChunk(1).front[0];";
                    case '.': return "write(cast(char)field[ptr]);";
                    case '>': return "ptr++;";
                    case '<': return "ptr--;";
                    default : return "";
                    }})
            .join('\n');
}

void bfRun(string code)() {
    mixin(bfCodeToDCode(code));
}

void main() {
    enum string code = "+++++ +++ [> +++++ +++ <-] > + .";
    bfRun!(code)();
}

bfCodeToDCodeでBrainf*ckのコードを対応するDのコードに置き換え、mixinで無理矢理ぶち込むだけです。簡単すぎる！
実際、bfCodeToDCodeは以下のような文字列になっています。

import std.stdio : write, stdin; ubyte[30000] field; size_t ptr;field[ptr]++;
field[ptr]++;
field[ptr]++;
field[ptr]++;
field[ptr]++;

field[ptr]++;
field[ptr]++;
field[ptr]++;

while(field[ptr]){
ptr++;

field[ptr]++;
field[ptr]++;
field[ptr]++;
field[ptr]++;
field[ptr]++;

field[ptr]++;
field[ptr]++;
field[ptr]++;

ptr--;
field[ptr]--;
}

ptr++;

field[ptr]++;

write(cast(char)field[ptr]);

調子にのりすぎて問題が

Brainf*ckでマンデルブロ集合を描画するプログラムを読ませたところ、あまりに長すぎるためかError: out of memoryと叱られました。12000コマンドほどあり、その分のコードを一つの場所に出力するためでしょうか・・・。
ldcだと一応コンパイルはしてくれるのですが、とりあえず++++のようなところを減らすことにしました。

string bfCodeToDCode(string code) {
    import std.algorithm : group, map;
    import std.range : repeat, chain;
    import std.string : join;
    import std.conv : to;
    return "import std.stdio : write, stdin; ubyte[30000] field; size_t ptr;"
        ~ code
            .group
            .map!((g) {
                    dchar token = g[0];
                    size_t count = g[1];
                    switch(token) {
                    case '+': return "field[ptr]+=" ~ count.to!string ~ ";";
                    case '-': return "field[ptr]-=" ~ count.to!string ~ ";";
                    case '[': return "while(field[ptr]){".repeat(count).join;
                    case ']': return "}".repeat(count).join;
                    case ',': return "field[ptr]=stdin.byChunk(1).front[0];".repeat(count).join;
                    case '.': return "write(cast(char)field[ptr]);".repeat(count).join;
                    case '>': return "ptr+=" ~ count.to!string ~ ";";
                    case '<': return "ptr-=" ~ count.to!string ~ ";";
                    default : return "";
                    }})
            .join('\n');
}

void bfRun(string code)() {
    mixin(bfCodeToDCode(code));
}

void main() {
    bfRun!(import("test.b"))();
}

根本的解決になっていない気もしますが・・・。
とりあえずマンデルブロだ！

AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB

よし！

速さの方は・・・

Dのコードに変換されるということは、コンパイラの最適化を受ける権利があるということです。
実際、生成されるコードはかなり無駄の多いコードなので、-Oをつけるとかなり変わりますね。
コンパイルにすごい時間かかりますが・・・。

dmd -J. -release test.d

4197msecs

dmd -J. -release -O test.d

1413msecs

あとがき

実はこのネタは某所で見た記事が元なんですが、何も難しいことを考えずに書けることの良さを実感しました。
コンパイル時パーサジェネレータというのも作った方がいたそうですから、いろいろ使えそうですね。