brainfuckでサブルーチンは実装できますか？

Question

brainfuckでサブルーチンを実装することはできますか？

私は最近brainfuckを知って、少しかじってみたのですが書けなさそうな感じでした。brainfuckとサブルーチンで検索すると、サブルーチンを使えるようにするために言語拡張している人はいましたが、brainfuckでサブルーチンを書けないということを主張する人は見かけませんでした。

実際の所どうなんでしょうか？御指南のほどをよろしくお願いいたします。

Comments

[sakura_hana]

teratailとは無関係な質問かと思いますので、該当タグは外して頂けますでしょうか？

[anndonut]

了解しました。teratailタグは削除し、brainfuckタグ、brainfxxkタグ、assemblyタグを追加申請いたします。

[anndonut]

あれ？brainfuck上でDSLを実装したらサブルーチンにできるのかも。だけど[と]のループの外には絶対に出ることはできない。だから、switchのようなものを書いて、そこでやりたいことを書けば一応サブルーチンぽく見えなくはないのか。当然brainfuckはexport, importがないけど、テキストファイルなのでPerlなどをプリプロセッサとしてかませば別ファイルの中身を持ってくることもできなくはない。結局それは言語拡張になってしまうのだが。

Answer 1

brainfuckでサブルーチンを実装することはできますか？

"サブルーチン"を「あるプログラムの実行位置から呼出(call)され、後で同位置へと復帰(return)可能なコード片」と解釈すると、Brainf*ckそのものでは実現不可能と考えます。

サブルーチンを実現するには、Brainfckプログラムの現在の“実行位置”を保存しておき、後から“実行位置”を復元する必要があります。通常のプログラミング言語ではこの動作は暗黙的に行われますが、Brainfckに用意された条件付きジャンプ命令（[,]ペア）を用いてもこの動作を直接実現できません。

---

スタックとVMの仕組みを実装しなければならないので、もし実現できたとしても相当巨大なコードになると思います。

この規模のBrainf*ckプログラムをフルスクラッチ開発するのは現実的でないと思います。たぶん、普通の人類には。

たとえばELVMを利用することで、Brainf*ck上で（原理的には）任意のプログラム動作が可能となります。

• GitHub shinh/elvm, EsoLangVM Compiler Infrastructure
• ELVM Compiler Infrastructure について

このELVMは、C言語で記述されたプログラムをBrainfckプログラムにコンパイル（変換）します。たとえば「C言語で記述されたC言語コンパイラ」は、ELVMによって「Brainfckで記述されたC言語コンパイラ」へと変換できます。

Comments

[anndonut]

アドバイスありがとうございます。ELVMはちょっと詳しくないのですが、適当なLL言語（私の場合はCommon Lisp）にbrainfuckのコードを出力させることはできるのかと思います。今週の土日時間ができてしまったので、もしかしたら私の方で解決できるかもしれないです。牛歩かもしれないですけどね。

Answer 2

あれ？brainfuck上でDSLを実装したらサブルーチンにできるのかも。だけど[と]のループの外には絶対に出ることはできない。だから、switchのようなものを書いて、そこでやりたいことを書けば一応サブルーチンぽく見えなくはないのか。当然brainfuckはexport, importがないけど、テキストファイルなのでPerlなどをプリプロセッサとしてかませば別ファイルの中身を持ってくることもできなくはない。結局それは言語拡張になってしまうのだが。

スタックとVMの仕組みを実装しなければならないので、もし実現できたとしても相当巨大なコードになると思います。ちょっと自分で実装してみる気はしないです。やってみたい猛者がおりましたら、チャレンジしてみてください。または、やってみたけどダメだったという報告でもいいです。それをベストアンサーにします。