【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう！後編】
2021.12.20
第4回～Brainfuckを実装しながら学ぶC++
「Brainfuckを実装しながら学ぶC++」シリーズも、今回を含めて、残り2回となりました！
ちなみに前回は、Brainfuck の実装にあたり、大枠を作っていきました。
今回は、Brainfuck インタプリタの核となる部分を、実装していきましょう！
メモリ操作命令「+ / - / > /<」の実装
まずは、比較的実装が簡単な、「+ / - / > / <」の命令から実装していきましょう。
値の加算命令「+」
1 2 3 | case INCREMENT: memory[ptr]++; break; |
すごくシンプルですね！
今ポインタが指しているメモリの値を、インクリメントしているだけです。
Braunfuck では、値が255を超えた (オーバーフローした) 場合は、値を「0」にする必要があります。
ですが unsigned char は、もともと「0～255」の範囲しか取りません。
つまり、オーバーフローした場合は勝手に「0」になるので、そういった処理は書かなくても OK ですね！
値の減算命令「-」
1 2 3 | case DECREMENT: memory[ptr]--; break; |
コードは「+」とほとんど同様です。
こちらもアンダーフローした場合、勝手に「255」になります。
ポインタの加算「>」
1 2 3 | case RIGHT: ptr = (ptr >= MEMORY_SIZE-1)? 0: ptr + 1; break; |
こちらは、オーバーフローの処理を、しっかりと記述してあげましょう。
今回の実装では、三項演算子「?」を使用した形で書いています。
これは、以下のコードと同様です。
1 2 3 4 5 6 | case RIGHT: if (ptr >= MEMORY_SIZE-1) ptr = 0; else ptr++; break; |
ポインタの減算「<」
1 2 3 | case LEFT: ptr = (ptr <= 0)? MEMORY_SIZE-1: ptr - 1; break; |
こちらも同様です。
MEMORY_SIZE-1 は、セグメンテーション違反に気をつけましょう。
入出力命令「 . / , 」の実装
次に、入出力命令を実装していきます。
C / C++ では、 #include <cstdio> を使えば、とてもシンプルに書けます。
1 2 3 4 5 6 7 | case OUTPUT: putchar(memory[ptr]); break; case INPUT: memory[ptr] = getchar(); break; |
ここまででデバッグをしてみよう
ここまで実装が終わると、ループを使わずに、Brainfuck コードを実行できるようになります。
例えば、「A」を出力するコード。
1 2 3 4 5 | # A ++++++++++++++++++++ ++++++++++++++++++++ ++++++++++++++++++++ +++++. |
そして、アンダーフローを使った「z」の出力もできると思います。
1 2 3 4 5 6 7 8 | # z -------------------- -------------------- -------------------- -------------------- -------------------- -------------------- --------------. |
他にも、ポインタの移動や入力も、自身で試してみると良いですね！
例えば、入力された文字をそのまま出力するコードは、
1 | ,. |
です。
ループ命令 [ ] の実装
ここが、Brainfuck インタプリタ実装において、もっとも難しいところです。
まずは実装する中で、考慮すべき点を列挙してみましょう。
- " [ " が来たら、それがあるコードポインタを保持しておく。
- " [ " の時点で、ポインタの指す値が0かどうかを確認する。
→ 0ならば、対応する " ] " の一つ後ろへ飛ぶ。
→ 0でなければ、そのままコードポインタを進める。 - " ] " が来たら、対応する " [ " へ飛ぶ。
以上の3点です。
ここで、ひと工夫が必要な部分は、ループのネストです。
" [ " と " ] "の対応関係を上手く実装する必要があります。
まずは、"[" のコードポインタを保持する配列を作りましょう。
大枠を作る
今回は、 std::stack<> を使用します。
その名の通り、LIFO (Last-In First-Out) なコンテナです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> #include <fstream> #include <string> #include <sstream> #include <cstdio> #include <stack> // 追加 /* 省略 */ int main(int argc, char* argv[]) { unsigned char memory[MEMORY_SIZE]; //! 1Byte=8bit (0~255) で構成されるメモリを定義 unsigned int ptr = 0; //! メモリポインタ (負の値は取らないのでunsigned) unsigned int code_ptr = 0; //! Brainfuckコードのポインタ unsigned int code_len = 0; //! Brainfuckコードの終端 (長さ) stack<int> loops; //! [new]ループのネスト用スタック: "[" のコードポインタが格納される /* 省略 */ } |
そうしたら、命令に対応した処理を実装していきましょう。
ひとまず、「ポインタの値が0のとき」以外を作ります。
つまり実装するのは、「 " ] " が来たら対応する " [ " に飛ぶ 」です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | case LOOP_START: loops.push(code_ptr); // "["の位置を保存 /* ポインタの値が0ならば "]" に飛ぶ */ if (memory[ptr] == 0) { // ... } break; case LOOP_END: if(loops.empty()){ cerr << "Error: Loop start order, " << LOOP_START << ", is not found." <<endl; return -1; } code_ptr = loops.top() - 1; // 対応する "[" に移動 loops.pop(); // 飛んだらまたスタックされるのでポップしておく break; |
" [ " から " ] "に飛ぶ処理を実装する
先ほどの if 文の中身を、ここでは実装していきましょう。
" [ " と " ] " の対応関係は、ループの深さを保持する、 depth という変数を用いて実装していきます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | case LOOP_START: loops.push(code_ptr); // "["の位置を保存 /* ポインタの値が0ならば "]" に飛ぶ */ if (memory[ptr] == 0) { int depth = 1; //! ループの深さ // 対応する "]" を探す while (depth > 0){ code_ptr++; // コードポインタを進める // もしコード終端に来てしまったらエラー if (code_ptr >= code_len){ cerr << "Error: Cannot find \"]\"." << endl; return -1; } // "[" と "]" を見つけたら深さを修正 if (code[code_ptr] == LOOP_START) depth++; if (code[code_ptr] == LOOP_END) depth--; } // もしdepth=0であれば、対応する "]" が見つかったので抜ける loops.pop(); // ループ終わり } break; |
やっていることは、じっくりコード中のコメントを読むと、理解できるかと思います。
あとは、もう一度ビルドして完成です！
1 2 | $ cd build $ make |
Brainfuck インタプリタが完成！
お疲れ様でした！
これにて、Brainfuck インタプリタが完成しました。
「意外と簡単！」と感じたのではないでしょうか？
最後に、動作確認もしてみましょう！
Hello, world!
以下のコードを、インタプリタに与えてみます。
1 2 3 | +++++++++[->++++++++>+++++++++++>+++++<<<]>.>++. +++++++..+++.>-.------------.<++++++++.--------. +++.------.--------.>+. |
1 2 | $ ./brainfuck hello.bf Hello, world! |
上手くいきましたね！
皆さんはどうでしょうか？
他にも、いろいろ試してみましょう！
最短のHello, World!
最短の「Hello, Wolrd!」コードです。
1 | +[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+. |
アンダーフローへの対応と、多重ループの対応が上手くできていないと、しっかりと出力されないサンプルです。
さらに、走査回数が計17,896ステップと、比較的難解な Brainfuck コードでもあります。
1 2 | $ ./brainfuck shortest_hello.bf Hello, World! |
どうでしょうか？
上手く実装できていれば、C++ なので、かなり高速に所望の出力が得られると思います！
FizzBuzz
おまけとして、有名な言葉遊びも。
1 2 3 4 5 | ++++++[->++++>>+>+>-<<<<<]>[<++++>>+++>++++>>+++>+++++>+++++>>>>>>++>>++< <<<<<<<<<<<<<-]<++++>+++>-->+++>->>--->++>>>+++++[->++>++<<]<<<<<<<<<<[-> -[>>>>>>>]>[<+++>.>.>>>>..>>>+<]<<<<<-[>>>>]>[<+++++>.>.>..>>>+<]>>>>+<-[ <<<]<[[-<<+>>]>>>+>+<<<<<<[->>+>+>-<<<<]<]>>[[-]<]>[>>>[>.<<.<<<]<[.<<<<] >]>.<<<<<<<<<<<] |
フィボナッチ数を延々と出力するコード
メモリがオーバフローするまで、出力してくれるコードはこちら。
1 2 3 4 5 6 | >++++++++++>+>+[ [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[ [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<- [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>> ]<<< ] |
番外編へつづく！
お疲れ様でした！
今回で、連載「Brainfuck を実装しながら学ぶ C++」のメインは、ひとまず終了になります。
次回最後となる番外編では、「出来上がったコードを改造」してみたいと思います！
本連載を通して少しでも、C / C++ に、そし て Brainfuck をはじめとする、Esolang にも興味を持っていただけたら幸いです。
本コードは、最初に定数として宣言していた命令を少し変えるだけで、オリジナル Esolang が作れますよ！
ぜひ遊んでみてくださいね！
では、次回もお楽しみ！
最終コード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | /** * Brainfuck interpreter * * @author RightCode Inc. * @cite https://rightcode.co.jp/ */ #include <iostream> #include <fstream> #include <string> #include <sstream> #include <cstdio> #include <stack> using namespace std; // 命令をコンパイル時定数として定義 constexpr char INCREMENT = '+'; constexpr char DECREMENT = '-'; constexpr char RIGHT = '>'; constexpr char LEFT = '<'; constexpr char LOOP_START = '['; constexpr char LOOP_END = ']'; constexpr char OUTPUT = '.'; constexpr char INPUT = ','; constexpr int MEMORY_SIZE = 1024; //! メモリのサイズ int main(int argc, char* argv[]) { unsigned char memory[MEMORY_SIZE]; //! 1Byte=8bit (0~255) で構成されるメモリを定義 unsigned int ptr = 0; //! メモリポインタ (負の値は取らないのでunsigned) unsigned int code_ptr = 0; //! Brainfuckコードのポインタ unsigned int code_len = 0; //! Brainfuckコードの終端 (長さ) stack<int> loops; //! ループのネスト用スタック: "[" のコードポインタが格納される // メモリの0初期化 memset(memory, 0, sizeof(memory)); /* コマンドライン引数処理 */ if (argc < 2){ cerr << "Error: A Brainfuck code is not passed as a command-line argument." << endl; cerr << "Please pass an argument as the form, $ brainfuck [FILENAME]." << endl; return -1; } ifstream file(argv[1]); //! ファイル読み込み if (!file){ cerr << "Error: The file, " << argv[1] << ", cannot be opened." << endl; return -1; } /* ファイルの中身を取得 */ stringstream buffer; //! stringstream用のバッファ buffer << file.rdbuf(); // ファイルをバッファとして取得 string code(buffer.str()); //! codeをstringとして取得 code_len = code.size(); //! コードサイズ /* Brainfuck 解析 */ while (code_ptr < code_len){ switch (code[code_ptr]) { case INCREMENT: memory[ptr]++; break; case DECREMENT: memory[ptr]--; break; case RIGHT: ptr = (ptr >= MEMORY_SIZE-1)? 0: ptr + 1; break; case LEFT: ptr = (ptr <= 0)? MEMORY_SIZE-1: ptr - 1; break; case LOOP_START: loops.push(code_ptr); // "["の位置を保存 /* ポインタの値が0ならば "]" に飛ぶ */ if (memory[ptr] == 0) { int depth = 1; //! ループの深さ // 対応する "]" を探す while (depth > 0){ code_ptr++; // コードポインタを進める // もしコード終端に来てしまったらエラー if (code_ptr >= code_len){ cerr << "Error: Cannot find \"]\"." << endl; return -1; } // "[" と "]" を見つけたら深さを修正 if (code[code_ptr] == LOOP_START) depth++; if (code[code_ptr] == LOOP_END) depth--; } // もしdepth=0であれば、対応する "]" が見つかったので抜ける loops.pop(); // ループ終わり } break; case LOOP_END: if(loops.empty()){ cerr << "Error: Loop start order, " << LOOP_START << ", is not found." <<endl; return -1; } code_ptr = loops.top() - 1; // 対応する "[" に移動 loops.pop(); // 飛んだらまたスタックされるのでポップしておく break; case OUTPUT: putchar(memory[ptr]); break; case INPUT: memory[ptr] = getchar(); break; default: // 上記以外の命令はコメント扱い break; } code_ptr++; } return 0; } |
番外編はこちら！
第1回目はこちら！
こちらの記事もオススメ！
書いた人はこんな人
- 「好きを仕事にするエンジニア集団」の（株）ライトコードです！
ライトコードは、福岡、東京、大阪の3拠点で事業展開するIT企業です。
現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。
いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。
システム開発依頼・お見積もり大歓迎！
また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」「WEBディレクター」を積極採用中です！
インターンや新卒採用も行っております。
以下よりご応募をお待ちしております！
https://rightcode.co.jp/recruit
ITエンタメ10月 13, 2023Netflixの成功はレコメンドエンジン？- ライトコードの日常8月 30, 2023退職者の最終出社日に密着してみた！
- ITエンタメ8月 3, 2023世界初の量産型ポータブルコンピュータを開発したのに倒産!?アダム・オズボーン
- ITエンタメ7月 14, 2023【クリス・ワンストラス】GitHubが出来るまでとソフトウェアの未来
関連記事
採用情報
\ あの有名サービスに参画!? /
バックエンドエンジニア
\ クリエイティブの最前線 /
フロントエンドエンジニア
\ 世界を変える…！ /
Androidエンジニア
\ みんなが使うアプリを創る /
iOSエンジニア
