2024年12月12日追記：0～255の間に値を収める処理に関して、バグ報告がありましたので修正しました。また、手抜き非効率なプログラミングがバレてしまった見つかりましたので、こちらも修正しました。TKIさん、@fujitanozomuさん、ありがとうございました。
はじめに
前回の記事で、難解プログラミング言語の1つである「HQ9+」について、日本語プログラミング言語「なでしこ」でインタプリタを実装してみた。しかし、「HQ9+」はチューリング完全でない（言語仕様からして自明）、という欠点があった。
チューリング完全
チューリング完全とは、理論上、（ほとんど）どんな計算問題でも解ける能力を持っている状態のことを指す。多くのプログラミング言語はチューリング完全であり、日本語でプログラムを作成でき、Webブラウザ上でも実行できるプログラミング言語「なでしこ」も、チューリング完全である。
一方で、難解プログラミング言語の中にも、チューリング完全なプログラミング言語が存在する。その代表例が「Brainf**k」である。
以下に示すように、Branif**kは様々な言語で、インタプリタやコンパイラが作成されている。
ということで、今回は「なでしこ」を用いてBrainf**kのインタプリタを作成してみる。
実装
Brainf**kには、計8つの命令が存在している。しかし、他の言語のインタプリタ作成記事でも述べられている通り、「>」「<」「+」「-」「.」「,」までは、比較的、簡単に実装できるが、残りの「[」「]」の実装が少し難しい。ということで、ここでは、まず簡単な6つの命令を実装することとした。
「Brainf**kのソースコードを入力...」と尋ねる。
それを「」で区切って《ソースコード》に代入。
《ソースコード》から「,」を配列検索。
もし、それが0以上なら、
「入力ストリームは？(ASCII文字)」と尋ねる。
それを「」で区切って《入力》に代入。
ここまで
《メモリ》に空辞書を代入。
《ポインタ》に0を代入。
《ソースコード》を反復
それで条件分岐
「>」なら、《ポインタ》に1を足して《ポインタ》に代入。ここまで。
「<」なら、《ポインタ》から1を引いて《ポインタ》に代入。ここまで。
「+」なら、1だけポインタ値変更処理。ここまで。
「-」なら、-1だけポインタ値変更処理。ここまで。
「.」なら、《メモリ》@《ポインタ》のCHRして、継続表示。ここまで。
「,」なら、
《メモリ》@《ポインタ》に0を代入。
もし、(《入力》の要素数)が1以上なら、
《入力》の0から1を配列取り出して、《入力値》に代入。
《入力値》のASCだけポインタ値変更処理。
ここまで。
ここまで。
ここまで。
ここまで。
「」を表示。
関数 (《変更値》だけ)ポインタ値変更処理とは
《メモリ》@《ポインタ》をNAN判定。
もし、それが真なら、
《メモリ》@《ポインタ》に0を代入。
ここまで。
《メモリ》@《ポインタ》に《変更値》を足す。
それと255のANDを、《メモリ》@《ポインタ》に代入。
ここまで
前回の記事で作成したプログラムを少し改造し、6つの命令が動作するようにした。入力されたソースコードを1文字ずつ区切って、配列変数《ソースコード》に代入し、これを反復して、条件分岐していくプログラムである。
工夫した点としては、（仕様としてどうかとは思うが）《メモリ》を辞書型にすることで、マイナス番目のメモリにもアクセス可能とした部分である。なお、検証していないので、「なでしこ」ではどうなのか分からないが、JavaScriptだと、配列に負の値を指定した場合、面倒なことになるらしい。
また、関数ポインタ値変更処理内では、255とのANDを《メモリ》@《ポインタ》に代入するよう、している。これは、例えば.+[.+]といったBrainf**kのプログラムに対応するため（オーバーフローの動作を再現するため）である。
参考ページ
実装（つづき）
と、ここまでプログラムを書いて、反復だと、順番に取り出すことは出来ても、戻ったり進んだり、という処理が出来ないことに気づいた。そこで、変数《実行箇所》を追加して、どこを実行するのか管理することとした。
また、「[」と「]」の実装が難しいのは、どこにジャンプすればいいのかが分かりにくい点にある。そこで、関数対応箇所発見処理を作成し、対応する「[」もしくは「]」の位置を求められるようにした。
「Brainf**kのソースコードを入力...」と尋ねる。
それを「」で区切って《ソースコード》に代入。
《ソースコード》から「,」を配列検索。
もし、それが0以上なら、
「入力ストリームは？(ASCII文字)」と尋ねる。
それを「」で区切って《入力》に代入。
ここまで
《実行箇所》に0を代入。
《メモリ》に空辞書を代入。
《ポインタ》に0を代入。
《実行箇所》が0から(《ソースコード》の要素数)の範囲内の間、
《ソースコード》@《実行箇所》で条件分岐
「>」なら、《ポインタ》に1を足して《ポインタ》に代入。ここまで。
「<」なら、《ポインタ》から1を引いて《ポインタ》に代入。ここまで。
「+」なら、1だけポインタ値変更処理。ここまで。
「-」なら、-1だけポインタ値変更処理。ここまで。
「.」なら、0だけポインタ値変更処理して、CHRして、継続表示。ここまで。
「,」なら、
《メモリ》@《ポインタ》に0を代入。
もし、(《入力》の要素数)が1以上なら、
《入力》の0から1を配列取り出して、《入力値》に代入。
《入力値》のASCだけポインタ値変更処理。
ここまで。
ここまで。
「]」なら、
もし、《メモリ》@《ポインタ》が0と等しく無いなら、
《実行箇所》の対応箇所発見処理を、《戻り先》に代入。
《実行箇所》に《戻り先》-1を代入。
ここまで。
ここまで。
「[」なら、
もし、《メモリ》@《ポインタ》が0なら、
《実行箇所》の対応箇所発見処理を、《実行箇所》に代入。
ここまで。
ここまで。
ここまで。
《実行箇所》に1を足して、《実行箇所》に代入。
ここまで。
「」を表示。
関数 （《現在地》の）対応箇所発見処理とは
《移動方向》に0を代入。
《移動先》に《現在地》を代入。
《ゴール》に「」を代入。
もし、《ソースコード》@《現在地》が「[」なら、
《移動方向》に1を代入。《ゴール》に「]」を代入。
違えば、
《移動方向》に-1を代入。《ゴール》に「[」を代入。
ここまで。
《移動先》が0から(《ソースコード》の要素数)の範囲内の間、
《移動先》に《移動方向》を足して《移動先》に代入。
もし、《ソースコード》@《移動先》が《ゴール》なら、《移動先》を戻す。
もし、《ソースコード》@《移動先》が《ソースコード》@《現在地》なら、
《移動先》の対応箇所発見処理を《移動先》に代入。
ここまで。
ここまで。
無限大を戻す。
ここまで。
関数 (《変更値》だけ)ポインタ値変更処理とは
《メモリ》@《ポインタ》をNAN判定。
もし、それが真なら、
《メモリ》@《ポインタ》に0を代入。
ここまで。
《メモリ》@《ポインタ》に《変更値》を足す。
それと255のANDを、《メモリ》@《ポインタ》に代入。
《メモリ》@《ポインタ》を戻す。
ここまで。
関数対応箇所発見処理では、スタックを使って（「なでしこ」には配列ポップと配列プッシュという命令がある）どこに戻れば良いか、検索することも考えられたが、「なでしこ」のプログラムが長くなってしまい、ややこしかったので、再帰を用いることとした。例えば「[」から順に後ろへ、検索をしていき、「]」を見つけたら、その場所を返却する。一方で、「[」を見つけたら、その位置を起点として、対応箇所発見処理を実行するという具合である。こうすることで、多重ループ（例えば++++[.->+++[.-]<]のようなBrainf**kのコード）も正しく、実行位置を戻すことが出来るようになった。
試してみる
こちらのサイトに掲載されているサンプルプログラムを試してみた。384ステップとされている以下のコードは正常に動作した。
+++++++++[->++++++++>+++++++++++>+++++<<<]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.
また、453ステップとされている、以下のコードも正常に動作した。
>++++[<++++++++>-]>++++++++[<++++++>-]<++.<.>+.<.>++.<.>++.<.>------..<.>
.++.<.>--.++++++.<.>------.>+++[<+++>-]<-.<.>-------.+.<.> -.+++++++.<.>
------.--.<.>++.++++.<.>---.---.<.> +++.-.<.>+.+++.<.>--.--.<.> ++.++++.<.>
---.-----.<.>+++++.+.<.>.------.<.> ++++++.----.<.> ++++.++.<.> -.-----.<.>
+++++.+.<.>.--.
一方で、10000ステップを超えるようなソースコードについては、応答なしとなってしまった。
よく考えると、「なでしこ3」は、JavaScriptに変換して実行している。そのため、「Brainf**k」→「なでしこ」→「JavaScript」の順に変換しているので、処理が遅くなっても当然であろう。
さいごに
もっと短い量でインタプリタを書けそうな気がしたが、それはコードゴルファーにでも任せようと思う。
（ところで、「なでしこ」でコードゴルフしてる人なんて居るのだろうか？）
以上。
【追伸】
プログラムのミスがあれば、コメントください m(__)m