• トップ
  • ブログ一覧
  • 【番外編】Brainfuckを実装しながら学ぶC++【改造編】
  • 【番外編】Brainfuckを実装しながら学ぶC++【改造編】

    広告メディア事業部広告メディア事業部
    2020.12.28

    IT技術

    さて前回で、「Brainfuckを実装しながら学ぶC++」シリーズのメインは、終わりを迎えましたね!

    【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう!後編】2020.12.22【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう!後編】第4回~Brainfuckを実装しながら学ぶC++「Brainfuckを実装しながら学ぶC++」シリーズも、今回を含め...

    今回は番外編ということで、出来上がったコードを、少しだけ改造してみたいと思います。

    皆さんのオリジナルの Esolang 作成、または C++ 学習の一助となれば幸いです。

    命令を変えてみよう

    まずは、一番簡単なアレンジです。

    1constexpr char INCREMENT =  '+';
    2constexpr char DECREMENT =  '-';
    3constexpr char RIGHT =  '>';
    4constexpr char LEFT =  '<';
    5constexpr char LOOP_START =  '[';
    6constexpr char LOOP_END =  ']';
    7constexpr char OUTPUT =  '.';
    8constexpr char INPUT =  ',';

    の部分を好きなものに変えてみましょう。

    例えば、

    1constexpr char INCREMENT =  'a';
    2constexpr char DECREMENT =  'b';
    3constexpr char RIGHT =  'c';
    4constexpr char LEFT =  'd';
    5constexpr char LOOP_START =  'e';
    6constexpr char LOOP_END =  'f';
    7constexpr char OUTPUT =  'g';
    8constexpr char INPUT =  'h';

    と変えるだけでも、オリジナルの Esolang になりますね!

    ただし、char 型は1バイト文字なので、文字列は指定できません

    さらに、C / C++ の switch 文は、「整数」もしくは今回のような「1バイト文字」しか分岐が行えません。

    この文字列を使った、Esolang 作成の対処については、後半で紹介します。

    switchではなくmapを使う

    実は、switch を使わずとも、Brainfuck インタプリタは作成できます。

    その場合、std::map<> を使います。

    これは、Python の辞書型変数のように扱うことができる、便利な STL (Standard Template Library) の一つです。

    mapの使い方

    まずは、インクルードしましょう。

    1#include <map>

    これで使えるようになります。

    キーは、どんな型でも良いのですが、例えば以下のように扱います。

    1std::map<std::string, int> dict = {
    2    {"Tokyo", 1395},
    3    {"Osaka", 882},
    4}
    5
    6std::cout << map["Osaka"] << "万人" << std::endl;  
    7// > 882万人

    stringをキーとして関数を呼ぶ

    map を使った実装では、例えば「 "+" をキーとしたら、increment() を呼ぶ」のように実装する必要があります。

    つまり、以下のように呼び出せるのが理想です。

    1bfs["+"]();  // increment()が呼ばれる

    こういった処理は、関数ポインタを利用して、実装する手段があります。

    関数ポインタとは、その名の通り関数へのポインタです。

    1#include <iostream>
    2#include <map>
    3using namespace std;
    4
    5void increment(){ cout << "Called Increment function." << endl; }
    6void decrement(){ cout << "Called Decrement function." << endl; }
    7
    8int main(){
    9    map<string, void (*)()> bfs = {
    10            {"+", increment},
    11            {"-", decrement},
    12    };
    13 
    14    bfs["+"](); // > Called Increment function.
    15    bfs["-"](); // > Called Decrement function.
    16    
    17    return 0;
    18}

    このように、関数ポインタは void (*) のように、括弧が必要です。

    なぜ括弧が必要かと言うと、こういうことです。

    1void* i_ptr() = &increment;    // [エラー] これだと void* が戻り値の関数とみなされる
    2void (*d_ptr)() = &decrement;  // こっちだとd_ptrがポインタだと解釈される
    3
    4i_ptr();  // エラー
    5d_ptr();  // >Called Decrement function.

    ややこしいですね…

    ちなみに、その後ろの括弧は引数です。

    Brainfuckインタプリタに適用してみる

    早速、関数ポインタと map を駆使して、インタプリタを再構築してみましょう!

    まずは、各命令に対して、関数を定義します。

    このとき、全ての関数について「ポインタ」や「メモリ」は弄る対象となるので、参照渡しで定義しましょう。

    中身は、前回実装したものと同じです。

    まずは、関数部。

    1/* 省略 */
    2#include <map>
    3
    4/* 省略 */
    5
    6void increment (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){ memory[ptr]++; }
    7void decrement (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){ memory[ptr]--; }
    8void right     (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){ ptr = (ptr >= MEMORY_SIZE-1)? 0: ptr + 1; }
    9void left      (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){ ptr = (ptr <= 0)? MEMORY_SIZE-1: ptr - 1; }
    10void output    (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){ putchar(memory[ptr]); }
    11void input     (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){ memory[ptr] = getchar(); }
    12void loop_start(unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){
    13    loops.push(code_ptr);   // "["の位置を保存
    14    /* ポインタの値が0ならば "]" に飛ぶ */
    15    if (memory[ptr] == 0) {
    16        int depth = 1;  //! ループの深さ
    17        // 対応する "]" を探す
    18        while (depth > 0){
    19            code_ptr++;  // コードポインタを進める
    20            // もしコード終端に来てしまったらエラー
    21            if (code_ptr >= code_len){
    22                cerr << "Error: Cannot find \"]\"." << endl;
    23                exit(-1);
    24            }
    25            // "[" と "]" を見つけたら深さを修正
    26            if (code[code_ptr] == LOOP_START)
    27                depth++;
    28            if (code[code_ptr] == LOOP_END)
    29                depth--;
    30        }  //  もしdepth=0であれば、対応する "]" が見つかったので抜ける
    31        loops.pop();  // ループ終わり
    32    }
    33}
    34void loop_end  (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){
    35    if(loops.empty()){
    36        cerr << "Error: Loop start order, " << LOOP_START << ", is not found." <<endl;
    37        exit(-1);
    38    }
    39    code_ptr = loops.top() - 1;  // 対応する "[" に移動
    40    loops.pop();                 // 飛んだらまたスタックされるのでポップしておく
    41}
    42
    43int main(int argc, char* argv[]) { /* ... */ }

    これらを格納する、map を定義します。

    1int main(int argc, char* argv[]) {
    2
    3    unsigned char memory[MEMORY_SIZE];    //! 1Byte=8bit (0~255) で構成されるメモリを定義
    4    unsigned int ptr = 0;                 //! メモリポインタ (負の値は取らないのでunsigned)
    5    unsigned int code_ptr = 0;            //! Brainfuckコードのポインタ
    6    unsigned int code_len = 0;            //! Brainfuckコードの終端 (長さ)
    7    stack<int> loops;                     //! ループのネスト用スタック: "[" のコードポインタが格納される
    8
    9    /* [new] Brainfuck orders */
    10    map<char, void(*)(unsigned char*, unsigned int&, unsigned int&, string&, stack<int>&, unsigned int&)> bfs = {
    11            {INCREMENT, increment},
    12            {DECREMENT, decrement},
    13            {RIGHT, right},
    14            {LEFT, left},
    15            {OUTPUT, output},
    16            {INPUT, input},
    17            {LOOP_START, loop_start},
    18            {LOOP_END, loop_end},
    19    };
    20    
    21    /* 省略 */
    22}

    このように定義することで、Brainfuck 解析部分の while 文の中は、以下のようにかなりスッキリしますね!

    1/* Brainfuck 解析 */
    2while (code_ptr < code_len){
    3    // もしキーが存在すれば
    4    if (bfs.count(code[code_ptr]) > 0){
    5        bfs[code[code_ptr]](memory, ptr, code_ptr, code, loops, code_len);
    6    }
    7    code_ptr++;
    8}

    ちなみに、map を使った方が、コードの管理はしやすいかもしれません。

    ですが、switch の方が、実行速度が速いのです。

    文字列を命令にする

    map を利用すれば、文字列を命令とした、Esolang が作成できるようになります。

    命令を文字列へ

    1// 命令をコンパイル時定数として定義
    2constexpr char* INCREMENT   =  (char*) "abc";
    3constexpr char* DECREMENT   =  (char*) "def";
    4constexpr char* RIGHT       =  (char*) "ghi";
    5constexpr char* LEFT        =  (char*) "jkl";
    6constexpr char* LOOP_START  =  (char*) "mno";
    7constexpr char* LOOP_END    =  (char*) "pqr";
    8constexpr char* OUTPUT      =  (char*) "stu";
    9constexpr char* INPUT       =  (char*) "vwx";
    10
    11constexpr int order_len = 3;

    このとき、コンパイル時定数は、型変換を明記しておかないと Warning が出てしまいます。

    なので、一応 (char*) のように、キャストしてあげましょう。

    また、実装のしやすさを考慮して、命令の長さも固定しておくパターンにします。

    mapのキーも文字列へ

    1map<string , void(*)(unsigned char*, unsigned int&, unsigned int&, string&, stack<int>&, unsigned int&)> bfs = {
    2        {INCREMENT, increment},
    3        {DECREMENT, decrement},
    4        {RIGHT, right},
    5        {LEFT, left},
    6        {OUTPUT, output},
    7        {INPUT, input},
    8        {LOOP_START, loop_start},
    9        {LOOP_END, loop_end},
    10};

    細かな調整

    命令をコードからどう切り取るか、コードポインタをどう進めるかも、修正していきましょう。

    1/* Brainfuck 解析 */
    2while (code_ptr < code_len){
    3    // もしキーが存在すれば
    4    string key = code.substr(code_ptr, order_len);  // [changed] substr()で命令を抽出
    5    if (bfs.count(key) > 0){
    6        bfs[key](memory, ptr, code_ptr, code, loops, code_len);
    7    }
    8    code_ptr += order_len;  // [changed]
    9}

    あとは、ループ処理の部分で、コードポインタの取り扱いを変更するだけとなります。

    1void loop_start(unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){
    2    loops.push(code_ptr);   // "["の位置を保存
    3    /* ポインタの値が0ならば "]" に飛ぶ */
    4    if (memory[ptr] == 0) {
    5        int depth = 1;  //! ループの深さ
    6        // 対応する "]" を探す
    7        while (depth > 0){
    8            code_ptr += order_len;  // [changed] コードポインタを進める
    9            // もしコード終端に来てしまったらエラー
    10            if (code_ptr >= code_len){
    11                cerr << "Error: Cannot find \"]\"." << endl;
    12                exit(-1);
    13            }
    14            // "[" と "]" を見つけたら深さを修正
    15            if (code.substr(code_ptr, order_len) == LOOP_START)  // [changed]
    16                depth++;
    17            if (code.substr(code_ptr, order_len) == LOOP_END)  // [changed]
    18                depth--;
    19        }  //  もしdepth=0であれば、対応する "]" が見つかったので抜ける
    20        loops.pop();  // ループ終わり
    21    }
    22}
    23void loop_end  (unsigned char* memory, unsigned int& ptr, unsigned int& code_ptr, string& code, stack<int>& loops, unsigned int& code_len){
    24    if(loops.empty()){
    25        cerr << "Error: Loop start order, " << LOOP_START << ", is not found." <<endl;
    26        exit(-1);
    27    }
    28    code_ptr = loops.top() - order_len;  // [changed] 対応する "[" に移動
    29    loops.pop();                 // 飛んだらまたスタックされるのでポップしておく
    30}

    これで OK です。

    試してみる

    実装の簡略化で、コードの空白と改行については、取り除く部分は書いていません。

    なので、それらがない Esolang コードを、読み取らせてみましょう!

    1abcabcabcabcabcabcabcabcabcmnodefghiabcabcabcabcabcabcabcabcghiabcabcabcabcabcabcabcabcabcabcabcghiabcabcabcabcabcjkljkljklpqrghistughiabcabcstuabcabcabcabcabcabcabcstustuabcabcabcstughidefstudefdefdefdefdefdefdefdefdefdefdefdefstujklabcabcabcabcabcabcabcabcstudefdefdefdefdefdefdefdefstuabcabcabcstudefdefdefdefdefdefstudefdefdefdefdefdefdefdefstughiabcstu
    1$ make
    2$ ./brainfuck 3byte_hello/bf
    3Hello, world!

    上のようになれば成功です!

    より難解な、オリジナル Esolang が出来上がりましたね!

    さいごに

    今回は番外編で、オリジナルの Esolang を作成してみました。

    もしかしたら、「少し難しい内容だった」という方も、中にいるかもしれませんね!

    ただ、もっと改良すれば、日本語のマルチバイト文字を使った Esolang も実現できてしまいます。

    余力のある方は、ぜひチャレンジしてみてくださいね!

    以上で、番外編含め本連載は終了になります。

    ここまでお付き合いいただき、ありがとうございました!

    第1回目はこちら!

    brainfuckを実装しながら学ぶC++2020.12.08【第1回】Brainfuckを実装しながら学ぶC++【Brainfuckとは】第1回目~Brainfuckを実装しながらC++学ぼう本連載では、「Brainfuck」の特性を理解しながら、実際に ...

    こちらの記事もオススメ!

    featureImg2020.07.17ライトコード的「やってみた!」シリーズ「やってみた!」を集めました!(株)ライトコードが今まで作ってきた「やってみた!」記事を集めてみました!※作成日が新し...
    featureImg2020.07.27IT・コンピューターの歴史特集IT・コンピューターの歴史をまとめていきたいと思います!弊社ブログにある記事のみで構成しているため、まだ「未完成状態」...

    ライトコードでは、エンジニアを積極採用中!

    ライトコードでは、エンジニアを積極採用しています!社長と一杯しながらお話しする機会もご用意しております。そのほかカジュアル面談等もございますので、くわしくは採用情報をご確認ください。

    採用情報へ

    広告メディア事業部

    広告メディア事業部

    おすすめ記事

    エンジニア大募集中!

    ライトコードでは、エンジニアを積極採用中です。

    特に、WEBエンジニアとモバイルエンジニアは是非ご応募お待ちしております!

    また、フリーランスエンジニア様も大募集中です。

    background