Brainfuck interpreter in Ruby's Regexp
Ruby の正規表現だけで Brainfuck インタプリタを作ることができました。正規表現の実行は =~ だけなので、ループなども正規表現の内部で実行してます。
https://github.com/shinh/hack/blob/master/bf_rb_reg/bf.rb
つまりどういうことができるかというと、 BF_REG という Regexp と BF_SUFFIX という文字列定数があって、 bf という文字列に格納された Brainfuck のコードを
BF_REG =~ bf + BF_SUFFIX
で実行することができます。出力は $~['o0'], $~['o1'], ... に入っているので、
output = '' 256.times do |i| o = $~["o#{i}"] break if !o output += o end
的なコードで取り出すことができます。入力は ! の後に続いてる文字列を入力とする形式。Ruby の正規表現は Turing 完全でないので、無限ループはできないようになっています。
仕様の一覧を並べると
- 8bit Brainfuck
- 入力の終端は -1
- メモリは255番地まで
- 出力文字数は256まで
- 入力文字数は256まで
- Brainfuck命令以外の文字があると正規表現がマッチに失敗する
- 無限ループがあると正規表現がマッチに失敗する(正確には1つのループが256回連続回ったら止まるという仕様なので、本当は止まるコードもマッチ失敗することがありえます)
など。256まで、という制限は実装をラクにするためなので、本質的な制限ではないです、が無限にはできないです(入力文字数は無限にできるかも?)。この程度の制限があっても十分に実用的(?)で、例えば cal.bf も動いています。
$ echo 2016 10 | time ruby bf.rb cal.bf 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ruby bf.rb cal.bf 1147.54s user 0.26s system 99% cpu 19:07.91 total
ただすごく遅くて、 cal.bf の実行に19分とかかかってました。1命令10msとかその程度だと思います。 + とか - が実に遅い。
こんなことできるとはつい最近まで思ってなかったのですが、 HITCON CTF で正規表現力の研鑽を積んだ結果、なんかできるような気がしてきて、やってみたらできました。
今思うに、一番重要なことは後方参照を更新できる、ということだったのかなと思います。 \g で呼び出された中にある後方参照は、呼び出されるたびに値が変わっていくという。