【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう！後編】

メディアチーム

【第4回】Brainfuckを実装しながら学ぶC++【実装してみよう！後編】

メディアチーム

2020.12.22

IT技術

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

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

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 インタプリタ実装において、もっとも難しいところです。

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

" [ " が来たら、それがあるコードポインタを保持しておく。
" [ " の時点で、ポインタの指す値が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$ 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}

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

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

採用情報へ

メディアチーム

「好きを仕事にするエンジニア集団」の（株）ライトコードです！ライトコードは、福岡、東京、大阪、名古屋の４拠点で事業展開するIT企業です。現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。システム開発依頼・お見積もり大歓迎！また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」を積極採用中です！インターンや新卒採用も行っております。以下よりご応募をお待ちしております！ https://rightcode.co.jp/recruit