• トップ
  • ブログ一覧
  • 【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう!後編】
  • 【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう!後編】

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

    IT技術

    Brainfuckを実装しながら学ぶC++」シリーズも、今回を含めて、残り2回となりました!

    ちなみに前回は、Brainfuck の実装にあたり、大枠を作っていきました。

    【第3回】Brainfuckを実装しながら学ぶC++【実装してみよう!中編】2020.12.22【第3回】Brainfuckを実装しながら学ぶC++【実装してみよう!中編】第3回~Brainfuckを実装しながら学ぶC++今回で、「Brainfuckを実装しながら学ぶC++」シリーズの第3...

    今回は、Brainfuck インタプリタの核となる部分を、実装していきましょう!

    メモリ操作命令「+ / - / > /<」の実装

    まずは、比較的実装が簡単な、「+ / - / > / <」の命令から実装していきましょう。

    値の加算命令「+」

    1case INCREMENT:
    2    memory[ptr]++;
    3    break;

    すごくシンプルですね!

    今ポインタが指しているメモリの値を、インクリメントしているだけです。

    Braunfuck では、値が255を超えた (オーバーフローした) 場合は、値を「0」にする必要があります。

    ですが unsigned char は、もともと「0~255」の範囲しか取りません。

    つまり、オーバーフローした場合は勝手に「0」になるので、そういった処理は書かなくても OK ですね!

    値の減算命令「-」

    1case DECREMENT:
    2    memory[ptr]--;
    3    break;

    コードは「+」とほとんど同様です。

    こちらもアンダーフローした場合、勝手に「255」になります。

    ポインタの加算「>」

    1case RIGHT:
    2    ptr = (ptr >= MEMORY_SIZE-1)? 0: ptr + 1;
    3    break;

    こちらは、オーバーフローの処理を、しっかりと記述してあげましょう。

    今回の実装では、三項演算子「?」を使用した形で書いています。

    これは、以下のコードと同様です。

    1case RIGHT:
    2    if (ptr >= MEMORY_SIZE-1)
    3        ptr = 0;
    4    else
    5        ptr++;
    6    break;

    ポインタの減算「<」

    1case LEFT:
    2    ptr = (ptr <= 0)? MEMORY_SIZE-1: ptr - 1;
    3    break;

    こちらも同様です。

    MEMORY_SIZE-1 は、セグメンテーション違反に気をつけましょう。

    入出力命令「 . / , 」の実装

    次に、入出力命令を実装していきます。

    C / C++ では、#include <cstdio> を使えば、とてもシンプルに書けます。

    1case OUTPUT:
    2    putchar(memory[ptr]);
    3    break;
    4
    5case INPUT:
    6    memory[ptr] = getchar();
    7    break;

    ここまででデバッグをしてみよう

    ここまで実装が終わると、ループを使わずに、Brainfuck コードを実行できるようになります。

    例えば、「A」を出力するコード。

    1# A
    2++++++++++++++++++++
    3++++++++++++++++++++
    4++++++++++++++++++++
    5+++++.

    そして、アンダーフローを使った「z」の出力もできると思います。

    1# z
    2--------------------
    3--------------------
    4--------------------
    5--------------------
    6--------------------
    7--------------------
    8--------------.

    他にも、ポインタの移動や入力も、自身で試してみると良いですね!

    例えば、入力された文字をそのまま出力するコードは、

    1,.

    です。

    ループ命令 [ ] の実装

    ここが、Brainfuck インタプリタ実装において、もっとも難しいところです。

    まずは実装する中で、考慮すべき点を列挙してみましょう。

    1. " [ " が来たら、それがあるコードポインタを保持しておく。
    2. " [ " の時点で、ポインタの指す値が0かどうかを確認する。
      → 0ならば、対応する " ] " の一つ後ろへ飛ぶ。
      → 0でなければ、そのままコードポインタを進める。
    3. " ] " が来たら、対応する " [ " へ飛ぶ。

    以上の3点です。

    ここで、ひと工夫が必要な部分は、ループのネストです。

    " [ " と " ] "の対応関係を上手く実装する必要があります。

    まずは、"[" のコードポインタを保持する配列を作りましょう。

    大枠を作る

    今回は、std::stack<> を使用します。

    その名の通り、LIFO (Last-In First-Out) なコンテナです。

    1#include <iostream>
    2#include <fstream>
    3#include <string>
    4#include <sstream>
    5#include <cstdio>
    6#include <stack>  // 追加
    7
    8/* 省略 */
    9
    10int main(int argc, char* argv[]) {
    11    
    12    unsigned char memory[MEMORY_SIZE];    //! 1Byte=8bit (0~255) で構成されるメモリを定義
    13    unsigned int ptr = 0;                 //! メモリポインタ (負の値は取らないのでunsigned)
    14    unsigned int code_ptr = 0;            //! Brainfuckコードのポインタ
    15    unsigned int code_len = 0;            //! Brainfuckコードの終端 (長さ)
    16
    17    stack<int> loops;                     //! [new]ループのネスト用スタック: "[" のコードポインタが格納される
    18
    19    /* 省略 */
    20}

    そうしたら、命令に対応した処理を実装していきましょう。

    ひとまず、「ポインタの値が0のとき」以外を作ります。

    つまり実装するのは、「 " ] " が来たら対応する " [ " に飛ぶ 」です。

    1case LOOP_START:
    2    loops.push(code_ptr);   // "["の位置を保存
    3
    4    /* ポインタの値が0ならば "]" に飛ぶ */
    5    if (memory[ptr] == 0) {
    6        // ...
    7    }
    8    break;
    9
    10case LOOP_END:
    11    if(loops.empty()){
    12        cerr << "Error: Loop start order, " << LOOP_START << ", is not found." <<endl;
    13        return -1;
    14    }
    15    code_ptr = loops.top() - 1;  // 対応する "[" に移動
    16    loops.pop();                 // 飛んだらまたスタックされるのでポップしておく
    17    break;

    " [ " から " ] "に飛ぶ処理を実装する

    先ほどの if 文の中身を、ここでは実装していきましょう。

    " [ " と " ] " の対応関係は、ループの深さを保持する、depth という変数を用いて実装していきます。

    1case LOOP_START:
    2    loops.push(code_ptr);   // "["の位置を保存
    3
    4    /* ポインタの値が0ならば "]" に飛ぶ */
    5    if (memory[ptr] == 0) {
    6        int depth = 1;  //! ループの深さ
    7
    8        // 対応する "]" を探す
    9        while (depth > 0){
    10            code_ptr++;  // コードポインタを進める
    11
    12            // もしコード終端に来てしまったらエラー
    13            if (code_ptr >= code_len){
    14                cerr << "Error: Cannot find \"]\"." << endl;
    15                return -1;
    16            }
    17
    18            // "[" と "]" を見つけたら深さを修正
    19            if (code[code_ptr] == LOOP_START)
    20                depth++;
    21            if (code[code_ptr] == LOOP_END)
    22                depth--;
    23
    24        }  //  もしdepth=0であれば、対応する "]" が見つかったので抜ける
    25
    26        loops.pop();  // ループ終わり
    27    }
    28    break;

    やっていることは、じっくりコード中のコメントを読むと、理解できるかと思います。

    あとは、もう一度ビルドして完成です!

    1$ cd build
    2$ make

    Brainfuck インタプリタが完成!

    お疲れ様でした!

    これにて、Brainfuck インタプリタが完成しました。

    「意外と簡単!」と感じたのではないでしょうか?

    最後に、動作確認もしてみましょう!

    Hello, world!

    以下のコードを、インタプリタに与えてみます。

    1+++++++++[->++++++++>+++++++++++>+++++<<<]>.>++.
    2+++++++..+++.>-.------------.<++++++++.--------.
    3+++.------.--------.>+.
    1$ ./brainfuck hello.bf
    2Hello, world!

    上手くいきましたね!

    皆さんはどうでしょうか?

    他にも、いろいろ試してみましょう!

    最短のHello, World!

    最短の「Hello, Wolrd!」コードです。

    1+[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+.

    アンダーフローへの対応と、多重ループの対応が上手くできていないと、しっかりと出力されないサンプルです。

    さらに、走査回数が17,896ステップと、比較的難解な Brainfuck コードでもあります。

    1$ ./brainfuck shortest_hello.bf
    2Hello, World!

    どうでしょうか?

    上手く実装できていれば、C++ なので、かなり高速に所望の出力が得られると思います!

    FizzBuzz

    おまけとして、有名な言葉遊びも。

    1++++++[->++++>>+>+>-<<<<<]>[<++++>>+++>++++>>+++>+++++>+++++>>>>>>++>>++<
    2<<<<<<<<<<<<<-]<++++>+++>-->+++>->>--->++>>>+++++[->++>++<<]<<<<<<<<<<[->
    3-[>>>>>>>]>[<+++>.>.>>>>..>>>+<]<<<<<-[>>>>]>[<+++++>.>.>..>>>+<]>>>>+<-[
    4<<<]<[[-<<+>>]>>>+>+<<<<<<[->>+>+>-<<<<]<]>>[[-]<]>[>>>[>.<<.<<<]<[.<<<<]
    5>]>.<<<<<<<<<<<]

    フィボナッチ数を延々と出力するコード

    メモリがオーバフローするまで、出力してくれるコードはこちら。

    1>++++++++++>+>+[
    2    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
    3        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
    4            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
    5    ]<<<
    6]

    番外編へつづく!

    お疲れ様でした!

    今回で、連載「Brainfuck を実装しながら学ぶ C++」のメインは、ひとまず終了になります。

    次回最後となる番外編では、「出来上がったコードを改造」してみたいと思います!

    本連載を通して少しでも、C / C++ に、そし て Brainfuck をはじめとする、Esolang にも興味を持っていただけたら幸いです。

    本コードは、最初に定数として宣言していた命令を少し変えるだけで、オリジナル Esolang が作れますよ

    ぜひ遊んでみてくださいね!

    では、次回もお楽しみ!

    最終コード

    1/*
    2 * Brainfuck interpreter
    3 *
    4 * @author RightCode Inc.
    5 * @cite https://rightcode.co.jp/
    6 */
    7
    8#include <iostream>
    9#include <fstream>
    10#include <string>
    11#include <sstream>
    12#include <cstdio>
    13#include <stack>
    14using namespace std;
    15
    16// 命令をコンパイル時定数として定義
    17constexpr char INCREMENT =  '+';
    18constexpr char DECREMENT =  '-';
    19constexpr char RIGHT =  '>';
    20constexpr char LEFT =  '<';
    21constexpr char LOOP_START =  '[';
    22constexpr char LOOP_END =  ']';
    23constexpr char OUTPUT =  '.';
    24constexpr char INPUT =  ',';
    25
    26constexpr int MEMORY_SIZE = 1024;  //! メモリのサイズ
    27
    28int main(int argc, char* argv[]) {
    29
    30    unsigned char memory[MEMORY_SIZE];    //! 1Byte=8bit (0~255) で構成されるメモリを定義
    31    unsigned int ptr = 0;                 //! メモリポインタ (負の値は取らないのでunsigned)
    32    unsigned int code_ptr = 0;            //! Brainfuckコードのポインタ
    33    unsigned int code_len = 0;            //! Brainfuckコードの終端 (長さ)
    34
    35    stack<int> loops;                     //! ループのネスト用スタック: "[" のコードポインタが格納される
    36
    37    // メモリの0初期化
    38    memset(memory, 0, sizeof(memory));
    39
    40    /* コマンドライン引数処理 */
    41    if (argc < 2){
    42        cerr << "Error: A Brainfuck code is not passed as a command-line argument." << endl;
    43        cerr << "Please pass an argument as the form, $ brainfuck [FILENAME]." << endl;
    44        return -1;
    45    }
    46
    47    ifstream file(argv[1]);     //! ファイル読み込み
    48    if (!file){
    49        cerr << "Error: The file, " << argv[1] << ", cannot be opened." << endl;
    50        return -1;
    51    }
    52
    53    /* ファイルの中身を取得 */
    54    stringstream buffer;        //! stringstream用のバッファ
    55    buffer << file.rdbuf();     // ファイルをバッファとして取得
    56    string code(buffer.str());  //! codeをstringとして取得
    57    code_len = code.size();     //! コードサイズ
    58
    59
    60    /* Brainfuck 解析 */
    61    while (code_ptr < code_len){
    62        switch (code[code_ptr]) {
    63            case INCREMENT:
    64                memory[ptr]++;
    65                break;
    66
    67            case DECREMENT:
    68                memory[ptr]--;
    69                break;
    70
    71            case RIGHT:
    72                ptr = (ptr >= MEMORY_SIZE-1)? 0: ptr + 1;
    73                break;
    74
    75            case LEFT:
    76                ptr = (ptr <= 0)? MEMORY_SIZE-1: ptr - 1;
    77                break;
    78
    79            case LOOP_START:
    80                loops.push(code_ptr);   // "["の位置を保存
    81
    82                /* ポインタの値が0ならば "]" に飛ぶ */
    83                if (memory[ptr] == 0) {
    84                    int depth = 1;  //! ループの深さ
    85
    86                    // 対応する "]" を探す
    87                    while (depth > 0){
    88                        code_ptr++;  // コードポインタを進める
    89
    90                        // もしコード終端に来てしまったらエラー
    91                        if (code_ptr >= code_len){
    92                            cerr << "Error: Cannot find \"]\"." << endl;
    93                            return -1;
    94                        }
    95
    96                        // "[" と "]" を見つけたら深さを修正
    97                        if (code[code_ptr] == LOOP_START)
    98                            depth++;
    99                        if (code[code_ptr] == LOOP_END)
    100                            depth--;
    101                    }  //  もしdepth=0であれば、対応する "]" が見つかったので抜ける
    102
    103                    loops.pop();  // ループ終わり
    104                }
    105
    106                break;
    107
    108            case LOOP_END:
    109                if(loops.empty()){
    110                    cerr << "Error: Loop start order, " << LOOP_START << ", is not found." <<endl;
    111                    return -1;
    112                }
    113                code_ptr = loops.top() - 1;  // 対応する "[" に移動
    114                loops.pop();                 // 飛んだらまたスタックされるのでポップしておく
    115                break;
    116
    117            case OUTPUT:
    118                putchar(memory[ptr]);
    119                break;
    120
    121            case INPUT:
    122                memory[ptr] = getchar();
    123                break;
    124
    125            default:  // 上記以外の命令はコメント扱い
    126                break;
    127        }
    128
    129        code_ptr++;
    130    }
    131
    132    return 0;
    133}

    番外編はこちら!

    【番外編】Brainfuckを実装しながら学ぶC++【改造編】2020.12.28【番外編】Brainfuckを実装しながら学ぶC++【改造編】番外編~Brainfuckを実装しながら学ぶC++さて前回で、「Brainfuckを実装しながら学ぶC++」シリーズの...

    第1回目はこちら!

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

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

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

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

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

    採用情報へ

    広告メディア事業部

    広告メディア事業部

    おすすめ記事

    エンジニア大募集中!

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

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

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

    background