BfLazyK

Lazy K のオリジナルの配布物には bf2lazy.c というファイルが含まれていて Brainfuck プログラムを Lazy K にコンパイルできるのですが、逆に Brainfuck で Lazy K のプログラムを動かす方法はこれまで存在しませんでした。Lazy K で Brainfuck の配列のようなものは比較的簡単に実現できるのに対し、Lazy K の実行はポインタを含む小さなオブジェクトを作っては捨て、作っては捨て…という感じになるので Brainfuck で実現するのは明らかに大変そうです。現実的な速度で動かすのは無理かもしれません。

ところが id:shinichiro_h さんがなんと Lazy K どころか Lisp が動くインタプリタBrainfuck で作ってしまいました。16bit の仮想マシンを定義してそのアセンブリから Brainfuck に変換するというもので、便利なことに仮想マシンアセンブラコードを生成するCコンパイラまで使えます。

Lisp が動くなら Lazy K も動くだろ、ということで以前作った Lazy K インタプリタを仮想 16bit マシン環境で動くようにして Brainfuckコンパイルしてみました。

https://github.com/irori/bflazyk

手を入れたのは主にメモリ管理の部分で、ヒープ領域を固定にしたのと、値の表現でポインタか即値データかを下位ビットで判断していたのを数値比較にした(ビット演算が重いので)のが大きな変更です。 ヒープ領域は 48k ワードありますが、Copying GC のために2分割して片方しか使わないのでメモリ制限は厳しめです。どのくらい厳しいかというと剰余を使うアルゴリズムFizzBuzz を動かしたら 50 あたりでメモリ不足になってしまいました。

実行速度ですが、生成された .bf を bflisp 付属の bfopt.cc で C に変換して gcc で -O なしでコンパイルしたところ Hello, world が48秒、FizzBuzz が22分でした。

lazy2c スクリプトは Lazy K プログラムを埋め込んだインタプリタの .c ファイルを生成します。これを C → Brainfuckコンパイラと組み合わせることで、Lazy K から Brainfuckコンパイラとして使えます。さらに hs2lazy と組み合わせると Haskell から Brainfuck への(超非効率な)コンパイラになりますね。*1

*1:ちなみに Haskell から Brainfuck へ直接変換するコンパイラがあるようです http://www.xanxys.net/hs2bf/