Brainfuckのインタプリタを作った話
タイトルの通り、Brainfuckのインタプリタを夏休みに作りました。
Brainfuckはプログラミング言語の一種で、インタプリタはコードを読み込んで実行してくれるやつです。
インタプリタを作るなんてすごい……と思うかもしれませんが、(Brainfuckなら)意外と簡単です。
インタプリタを作ろうと思ったきっかけ
遡るほど約一年前……
僕「プログラミング言語作ってみたい〜〜」
先輩*1「BrainfuckのインタプリタだったらB1の知識でも作れると思うよ」
僕「(こんなにシンプルなプログラミング言語あるとは…！)」
それから半年後(夏休みに入る)
僕「今年の夏休みこそは何かやろ」
ーーここでひらめくエフェクトーー
僕「！！(Brainfuckのインタプリタ作ってみるのいいかもしれない)」
という感じで僕のインタプリタ作成が始まりました。
実際先輩の言う通り、プログラミングの授業を受けたことのある人なら作れると思います。
Brainfuckの言語仕様がシンプルだからですね。
まずはBrainfuckの言語仕様などについて軽く話したいと思います。
Brainfuckの言語仕様
Brainfuck - Wikipediaを読めば言語仕様がわかります。
短くて本当に言語仕様これだけ！？と思う人もいるかもしれませんが、本当にこれだけです。
一応ここでも説明すると
データを保存するメモリと、メモリの書き込んだり読み込んだりする場所を指定するポインタがあります。
それに対応して、メモリの値を増減させる2つの命令、ポインタの値を増減させる2つの命令があります。
Brainfuckは8つの命令しかないので、この一行で既にBrainfuckの半分を理解したと言っても構いません。
あとは標準入力と標準出力、while文の括弧始め、括弧終わりがあります。
命令は以上の8つしかありません。
授業で使ったアセンブリ言語の方がもっと命令があって扱いやすいです……
これでBrainfuckの文法の説明が終わりました。
と言いたいんですが、実はBrainfuckには未定義動作があります。
例外的な感じなので必要があれば説明します。*2
Brainfuckの環境構築をして遊んでみる
文法を理解したあとは、早速インタプリタの作成に取り組みたいところですが、
実際に自分で動かせるBrainfuckのプログラムが書けないことには、作っているものが間違っていないかどうか確かめるのが大変です。
本末転倒感はありますが、Brainfuckを実行する環境を整えましょう。
僕は以下の記事を参考にしました。
Brainfuckやってみたい人は参考にするといいと思います。
Brainfuck-ikインタプリタ
使い方や仕様を説明した後に、実装の話を少ししたいと思います。
それでは僕の作ったインタプリタの登場です！！(ドドン)
READMEは書いていませんが、仕様はpydocか直接コメントを見ても確認することができます。
使い方
コードを直接入力して、実行が可能です。
いちいちコードをコピペして実行するのはめんどくさいですよね。
なので、コマンドライン引数としてファイルを渡しても実行できるようになっています。
実装を語る
言語仕様がシンプルなので、特に悩むこともなく実装ができると思います。
僕の作ったインタプリタの実装では、変数も5つしか使いませんでした。
なので、ここでは僕が書くときに少し詰まった箇所についてだけ語ります。
(明日テストでサークルも今日あるので、時間がないからというわけではないです)
標準入力を受け付けている際に改行するとまずい
「,」が実行されると、標準入力された最初の1文字を、ASCIIコードによって数値に変換しメモリに値を保存します。
僕の実装では、標準入力をinpt変数に保存し、その先頭一文字inpt[0]を保存します。
たぶん大抵の実装はそうなると思います。
ここで問題になるのは、改行された場合です。
input関数で入力を取る場合、改行されると改行コードではなく、空文字を返してきます。
この場合、inptは空文字ですからinpt[0]はエラーとなります。
…………あなたの言いたいことはわかります。
sys.stdin.readlineで入力を取れば、改行コード取れるから空文字にならないから大丈夫ではと。
今ブログを書いて僕もそう思ったので、年内には修正します！！
とはいえ、空文字が入力された場合に困ったことになることには変わりません。
そんなこと起きるの？と思う人もいるかもしれませんが、EOFを送れば入力は終了しますから、空文字を送ることができます。
対処法
対処法は簡単でif文などで条件分岐すれば解決です。
僕の場合だとinptが空文字列の際、メモリに0を保存します。
ブラケットの深さを記録しろ
Brainfuckの命令の一種に「[」、「]」というwhile文のようなものがあります。
Brainfuckの繰り返し処理も条件分岐もこいつのおかげでできるので、重要な命令になります。
「]」はプログラムの対応する「[」に飛ばすか、次の命令に行くかの分岐をします。
対応する「[」については、while文内に突入する際に、プログラム内の何文字目か保存されてあればその位置まで簡単に飛べるので、大きな問題は起きないと思います。
「[」についても、while文内に突入する際にプログラム内の何文字目か保存するだけなので、簡単です。
問題はポインタの指す値が0のとき、つまり「[」があるがwhile文内に突入せず、対応する「]」に飛ぶ場合の挙動です。
やってしまいがちな実装は、最初に見つけた「]」に飛んでしまうことです。簡単に書けるのでそう書いてしまうこともありますが、最初に見つけた「]」が対応するブラケットとは限りません。
プログラムの一番左の「[」を読み込んでいるとして
の場合なら、最初に見つけた「]」が対応するブラケットです。
しかし
[[]]の場合なら、最初に見つけた「]」が対応するブラケットではありません。
ネットでもこういう実装してしまっているのを見かけました。
僕もここで少し躓いてしまいました。
解決策
現在の深さを記録しましょう。
「[」を見つけたときは、深さを+1し、
「]」を見つけたときは、深さを-1します。
そうして、自分と同じ深さになるまで命令を飛ばし続ければいいのです。
感想
あまりプログラミングしてないので、久々にプログラミングできて楽しかったですね。
何かプログラミング言語を自作してみたいという気持ちもだいぶ満たされました。
自分で新しい命令を実装してみるのも楽しいと思います。
僕は結構ダラダラやってたので、3日ぐらいかけた気がしますが、
プログラミングがっつりやっている人が書けば1日もいらないと思います。
プログラミングしたいけど、何書いていいかわからない。という人はぜひBrainfuckのインタプリタを作ってみてください。*3
また僕のインタプリタをimportして、BF_interpreter関数にプログラムを渡すと、なんと実行してくれます。
使う方がいるかはわかりませんが、常識の範囲でご自由に使って大丈夫です。
最後にリポジトリを載せておきます。
*1:https://twitter.com/ie_Yoshisaur/status/1618653837296017408
*2:最大最小値の状態での値の減少増減は未定義動作となっています。
