メディアチーム【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう！後編】
メディアチームIT技術
「Brainfuckを実装しながら学ぶC++」シリーズも、今回を含めて、残り2回となりました！
ちなみに前回は、Brainfuck の実装にあたり、大枠を作っていきました。
今回は、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 インタプリタ実装において、もっとも難しいところです。
まずは実装する中で、考慮すべき点を列挙してみましょう。
- " [ " が来たら、それがあるコードポインタを保持しておく。
- " [ " の時点で、ポインタの指す値が0かどうかを確認する。
→ 0ならば、対応する " ] " の一つ後ろへ飛ぶ。
→ 0でなければ、そのままコードポインタを進める。 - " ] " が来たら、対応する " [ " へ飛ぶ。
以上の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$ makeBrainfuck インタプリタが完成！
お疲れ様でした！
これにて、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}番外編はこちら！
第1回目はこちら！
こちらの記事もオススメ！
ライトコードでは、エンジニアを積極採用中！
ライトコードでは、エンジニアを積極採用しています！社長と一杯しながらお話しする機会もご用意しております。そのほかカジュアル面談等もございますので、くわしくは採用情報をご確認ください。
採用情報へ
「好きを仕事にするエンジニア集団」の（株）ライトコードです！ ライトコードは、福岡、東京、大阪、名古屋の４拠点で事業展開するIT企業です。 現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。 いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。 システム開発依頼・お見積もり大歓迎！ また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」を積極採用中です！ インターンや新卒採用も行っております。 以下よりご応募をお待ちしております！ https://rightcode.co.jp/recruit
