パイソン山中：「TypeScriptでAIに作らせる？そんな誰もが思いつくような安っぽい作り方はあなた(ライフゲーム)には似合いません。サブスクの代償としても対価に合わない。もっともフィジカルで、もっともプリミティブで、そしてもっともフェティッシュなやり方(Brainf*ck)でいかせていただきます。」
ということで、Brainf*ckというプログラミング言語に入門してみました。
入門した私はHello worldを試した後、ちょうどいい難易度に思えたライフゲーム(Conway’s Game of Life)を実装することにしました。当初、三日くらいで終わるかなと考えていたのですが、実際には2週間以上費やしてしまいました。
この記事では、2週間で学んだこととBrainf*ckによるライフゲームの実装を解説します。
Brainf*ckとは、Urban Müllerという人が開発したプログラミング言語で、>の8つのコマンドのみでチューリング完全を実現しています。
| メモリのインデックス | 0 | 1 | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 0 | 0 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
上記のように0で初期化されたメモリセルの配列とそのポインタを、下記の通りに操作することで動作します。
| コマンド | 処理 |
|---|---|
| > | ポインタをインクリメント |
| ポインタをデクリメント | |
| + | ポインタが指すメモリセルの値をインクリメント |
| – | ポインタが指すメモリセルの値をデクリメント |
| . | ポインタが指すメモリセルの値をASCIIコードに対応させて出力 |
| , | 入力から1バイト読み込んで、ポインタが指すメモリセルに代入 |
| [ | ポインタの指すメモリセルの値が0なら、対応する]までジャンプ |
| ] | ポインタの指すメモリセルの値が0でなければ、対応する[までジャンプ |
| 上記のコマンドのどれにも当てはまらない文字は全てコメントとして扱う |
例えば、下記のコードは>でポインタを1移動させ、移動後に72個の+によってメモリセルの値を72(HのASCIIコード)までインクリメントし、.で「H」を出力、最後にで元々ポインタが差していたメモリセルに戻るコードです。
>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
.
実行後、メモリセルの状態は下記のようになっています。
| メモリのインデックス | 0 | 1 | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 0 | 72 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
3*3サイズのライフゲームを作りました。
ライフゲームとは、生命の個体数や分布をシミュレーションする簡単なゲームです。
オセロの盤のようなフィールドで、フィールド上のセルはそれぞれ 「生」 か 「死」 の状態にあります。
それぞれのセルがお互いに下記のルールで影響を及ぼし合いながら生きたり死んだりを繰り返します。
ルール
誕生：死んだセルに隣接する生きたセルがちょうど3つの場合、次のステップでは生きたセルになる。
生存：生きたセルに隣接する生きたセルが2つまたは2つなら、生き続ける。
過疎：生きたセルに隣接する生きたセルが1つ以下なら、死ぬ。
過密：生きたセルに隣接する生きたセルが4つ以上なら、死ぬ。
私が作ったライフゲームでは、生きたセルを*、死んだセルを-で表現します。
ライフゲームでは、周期的に繰り返し同じ形になるパターンがいくつも存在し、振動子と呼ばれます。
振動子の中で代表的なものが、ブリンカーと呼ばれる縦に3つ生きたセルが繋がった状態と横に3つ生きたセルが繋がった状態で振動するものです。
これを、私が作ったライフゲームで試してみると下記のように出力されます。
-*-
-*-
-*-
---
***
---
# 以下決められたループ回数まで繰り返し
実装はこちらです。
迫力を出すために、コメントとインデントを外してみました。
この後詳しく解説するのでご安心ください。
>>+>>>>>>>+>+>>>>>>>>+>>>>>>>>+>>>>>>>+>+>>>>>>>>+>>>>>>>>+>>>>>>>+>+>>>>>>>>+
+++++[->[>-
>>>++++++++++++++++++++++++++++++++++++++++++.[-]>>>>>>>+>>>>>>>>>>>>>>>>+>>>>>>>>+
]>[->>>+++++++++++++++++++++++++++++++++++++++++++++.
[-]]+>>>>>>>[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
+>>>>>>>>>>>>>>>>+>>>>>>>>+>>>>>>>>+>>>>>>>>+
]>[->>>+++++++++++++++++++++++++++++++++++++++++++++.
[-]]+>>>>>>>[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
+>>>>>>>>>>>>>>>>>>>>>>>>+>>>>>>>>+]>[-
>>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]+>>>>>>>>>>>++++++++++.[-]
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]+
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>>>>>>>>>>>>>>>>+>>>>>>>>+
]>[->>>+++++++++++++++++++++++++++++++++++++++++++++.
[-]]+>>>>>>>[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]++
++>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>>>>>>>>+>>>>>>>>+>>>>>>>>+
]>[->>>+++++++++++++++++++++++++++++++++++++++++++++.
[-]]+>>>>>>>[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]+
++>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>>>>>>>>+
]>[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+>>>>>>>>>>>++++++++++.[-][>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
++>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+]>[-
>>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]+>>>>>>>[>-
>>>++++++++++++++++++++++++++++++++++++++++++.[-]+++
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+]>[-
>>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]+>>>>>>>[>-
>>>++++++++++++++++++++++++++++++++++++++++++.[-]++
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>[-
>>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]+>>>>>>>>>>>++++++++++.[-
]++++++++++.[-]
[->->>-->+
[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]>[->>--->+[+++[-]>-]>[-
+>>>>>]]+>>>>>>>[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-
+>>>>>]]>[->>--->+[+++[-]>-]>[-+>>>>>]]+>>>>>>>[->->>-->+[->->+
[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]>[->>--->+[+++[-]>-]>[-
+>>>>>]]+>>>>>>>[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-
+>>>>>]]>[->>--->+[+++[-]>-]>[-+>>>>>]]+>>>>>>>[->->>-->+[->->+
[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]>[->>--->+[+++[-]>-]>[-
+>>>>>]]+>>>>>>>[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-
+>>>>>]]>[->>--->+[+++[-]>-]>[-+>>>>>]]+>>>>>>>[->->>-->+[->->+
[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]>[->>--->+[+++[-]>-]>[-
+>>>>>]]+>>>>>>>[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-
+>>>>>]]>[->>--->+[+++[-]>-]>[-+>>>>>]]+>>>>>>>[->->>-->+[->->+
[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]>[->>--->+[+++[-]>-]>[-
+>>>>>]]+]
Brainf*ckをターミナル上で動かすのはとても簡単で、下記のコマンドでインタプリタをインストールするだけで完了します。
実行するには、.bf拡張子をつけてコードを保存した後brainfuckコマンドで実行します。
しかし、初心者がいきなりターミナル上で実行しながらコーディングするのはお勧めしません。ターミナル上に出力されるのは.で出力した文字のみであり、メモリセルの状態が分からないためデバッグが非常に難しいためです。
そこで、私はカチカチさんという方が公開している下記のインタプリタを使いました。
こちらのインタプリタは、#をブレークポイントとして使うことができ、メモリの状態を確認しながら実行できるので、ターミナルで実行しながら開発する時と比べてかなり楽になります。
注意
先ほど登場したライフゲームのコードはカチカチさん作成のインタプリタでは動きません。
おそらく使用するメモリの数が多すぎるためです。
動かしてみたい方はターミナルでお試しください。
+++++ // ループ回数(5)
[
-
// 繰り返したい処理はじめ
>+++
// 繰り返したい処理おわり
]
Brainf*ckでループを書くには、まずループ回数を保持するメモリセルを決めて、ループ回数分だけインクリメントします。
+++++ // ループ回数(5)
| メモリのインデックス | 0 | 1 | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 5 | 0 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
次に、[を使います。現在ポインタが差しているメモリセルの値は5（0でない）なので、対応する]に飛ばずループ内の処理が実行されます。
ループ内では、ループ回数を保持しているメモリセルの値を1デクリメントします。
// ループ開始
[ // ループに入る
- ループ回数をデクリメント
| メモリのインデックス | 0 | 1 | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 4 | 0 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
その後、ループ回数を保持しているメモリセルから移動し、繰り返したい処理を実行します。
今回は、一つポインタを移動した後そのセルの値3増やします。
// 繰り返したい処理はじめ
>+++
// 繰り返したい処理おわり
その後、ループ回数を保持しているメモリセルにポインタを戻します。こうすることで、ループ一周ごとにループ回数を保持しているメモリセルの値が減り、0になったところでループを抜けます。
| メモリのインデックス | 0 | 1 | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 0 | 15 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
豆知識[-]と書くことで、メモリセルの値が0以上のどんな値でも0になるまでデクリメントすることができるので、値をリセットしたい時に便利です。
+>+
[
[-]>-
// 対象のセルが0以外の時に実行したい処理はじめ
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
[-]
// 対象のセルが0以外の時に実行したい処理おわり
]>[
-
// 対象のセルが0の時に実行したい処理はじめ
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
[-]
// 対象のセルが0の時に実行したい処理おわり
>
]
Brainf*ckの分岐は、判定対象が0か、0以外かで判定を行います。
今回はインデックスが0のメモリセルを判定対象のセルとして、対象のセルの値が0以外の時は"A"、0の時は"B"を出力してみます。
まずは判定対象が0以外の時の解説をするので判定対象のセルに1を入れ、その隣のセル（以降フラグセルと呼ぶ）にも1をセットしてポインタの位置を判定対象のセルに戻します。
| メモリのインデックス | 0 | 1 | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 1 | 1 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
判定対象のメモリセルが0以外なので、一つ目のループに入ります。
ただし、入った直後にある[-]>-で判定対象のセルとフラグセルの値はどちらも0にリセットされます。
判定対象のセルの値が0になるということは、繰り返し回数が1のループです。Brainf*uckでの分岐は、ループの応用で作成します。
// ポインタは判定対象のメモリセル上からスタート
[
[-]>-
// 対象のセルが1の時に実行したい処理はじめ
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
[-]
// 対象のセルが1の時に実行したい処理おわり
]
| メモリのインデックス | 0 (判定対象) | 1 (フラグセル) | 2 | 3 | … |
|---|---|---|---|---|---|
| メモリの値 | 0 | 0 | 0 | 0 | … |
| ポインタの位置 | ^ | … |
判定対象のメモリセルが0の場合、最初のループには入りません。
そのため、最初のループの次に書かれている>の処理でフラグセルに移動します。フラグセルは、セットアップ時に1になっているので二つ目のループに入ります。
もし判定対象のメモリセルが0以外だった場合、一つ目のループ内の処理でフラグセルが0になっているので二つ目のループには入りません。感動です。
>[
-
// 対象のセルが0の時に実行したい処理はじめ
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
[-]
// 対象のセルが0の時に実行したい処理おわり
>
]
だいぶ迫力が減って、さらにリファクタリングの余地がありありなことがバレてしまってお恥ずかしいですが、コメントとインデントを戻したコードを見ながら解説します。
> ループ用のメモリを空ける
初期設定 size = 3*3
>+>>>> >>> x0
+>+>>>> >>> x1
>+>>>> >>> x2
>+>>>> >>> x3
+>+>>>> >>> x4
>+>>>> >>> x5
>+>>>> >>> x6
+>+>>>> >>> x7
>+>>>> >>> x8
74th cell
x0
ループ用のメモリへ移動
+++++ ループ回数を設定
[
-
>
====メインの処理====
print x0
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x1 x3 x4
>>>>> >>+
>>>>> >>>
>>>>> >>>+
>>>>> >>>+
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >> x1
print x1
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x0 x2 x3 x4 x5
+>>>> >>>>> 0
>>>>> >>+ 2
>>>>> >>>+ 3
>>>>> >>>+ 4
>>>>> >>>+ 5
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print x2
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x1 x4 x5
+>>>> >>>>> 1
>>>>> >> 3
>>>>> >>>+ 4
>>>>> >>>+ 5
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print LF
>>>>+++++ +++++.[-]
print x3
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x0 x1 x4 x6 x7
2
+ 1
+ 0
>>>>> >>>
>>>>> >>>
>>>>> >>>>
>>>>> >>+ 4
>>>>> >>> 5
>>>>> >>>+ 6
>>>>> >>>+ 7
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print x4
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x0 x1 x2 x3 x5 x6 x7 x8
+ 3
+ 2
+ 1
+ 0
>>>>> >>>
>>>>> >>>
>>>>> >>>
>>>>> >>>>
>>>>> >>+ 5
>>>>> >>>+ 6
>>>>> >>>+ 7
>>>>> >>>+ 8
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print x5
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x1 x2 x4 x7 x8
+ 4
+ 2
+ 1
>>>>> >>>
>>>>> >>>
>>>>> >>>
>>>>> >>>>
>>>>> >> 6
>>>>> >>>+ 7
>>>>> >>>+ 8
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print LF
>>>>+++++ +++++.[-]
print x6
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x3 x4 x7
5
+ 4
+ 3
>>>>> >>>
>>>>> >>>
>>>>> >>>>
>>>>> >>+ 7
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print x7
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x3 x4 x5 x6 x8
+ 6
+ 5
+ 4
+ 3
>>>>> >>>
>>>>> >>>
>>>>> >>>
>>>>> >>>>
>>>>> >>+ 8
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print x8
[>->>>++++++++++++++++++++++++++++++++++++++++++.[-]
increment x4 x5 x7
+ 7
6
+ 5
+ 4
>>>>> >>>
>>>>> >>>
>>>>> >>>
>>>>> >>>>
]
>
[->>>+++++++++++++++++++++++++++++++++++++++++++++.[-]]
+
>>>>> >>
print LF
>>>>+++++ +++++.[-]
print LF
>>>>+++++ +++++.[-]
74th cell
x0
update x0
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x1
update x1
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x2
update x2
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x3
update x3
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x4
update x4
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x5
update x5
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x6
update x6
[->->>-->+[->->+[++++++[-]>>-]>>[-+>>>>>>]]>[-+>>>>>]]
>
[->>--->+[+++[-]>-]>[-+>>>>>]]
+
>>>>> >> x7
update x7
[->->>-->+[->->+[++++++[-]>>-]>>[-