記号だけで brainfuck インタプリタ

Ruby 1.9 の新機能のひとつに「lambda { ... } を -> { ... } と書ける」というのがあります。この表記は反対意見が根強い *1 ですが、確実にすばらしい点があって、全部記号だということです。これによって Ruby が記号だけでチューリング完全になります *2 。
デモとして、brainfuck インタプリタを記号だけで書いてみました。

$___,@_,@__,$_=(@@__="")=~//,?#=~/$/,->(_){_<(__="####"=~/$/)**__&&(@@__<<
_;@__[_+@_])},[*$<]*@@__;@__[$___];$____,$_,@___,$__,@__=$_[@_+($_+?!=~/!/
)..-@_],$`,[],[],->(_){(__=$_[_];__=~/[><+\-\.,]/?$__<<$_[_]:__==?[?(@___,
$__=$__,[]):__==?]?$__=@___<<$__:__==$\?$\:_)&&@__[_+@_]};@__[$___];@___,
$_,@@_,@__=[],[],$___,->(_){$_[@@_]||=$___;({?>=>->{@@_+=@_},?<=>->{@@_-=
@_},?+=>->{$_[@@_]+=@_},?-=>->{$_[@@_]-=@_},?.=>->{$><<@@__[$_[@@_]]},?,=>
->{$____=~/^./&&($____=$';$_[@@_]=@@__=~/#{((__,=[*?/..?:]&[$&];__)||(__,=
[*?@...?[]&[$&];__)||(__,=[*?`...?{]&[$&];__))&&__!=?{?$&:'\\'+$&}/)},$\=>
->{$\}}[$__[_]]||->{$_[@@_]!=$___&&(@___<<[$__,_-@_];$__=$__[_];@__[$___]
*@___,($__,_)=@___);""})[]&&@__[_+@_]};@__[$___]

このとおり。

$ cat hello.bf
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

$ ./ruby punctfuck.rb hello.bf; echo
Hello, world!

プロの記号ゴルファーには常識かもしれませんが、ポイントだけ紹介します。

数字を作る方法

String#=~ を使っています。このメソッドは正規表現がマッチした先頭位置を返します。なので 1 を作るためには

"#"=~/$/

とかします。

標準入力を読む方法

• $< が標準入力の IO です (正確には ARGF) 。
• $<.to_a で読み込んだ各行を各要素にしたリストが得られます。
• 1.9 では [*ary] で ary.to_a と同じような効果があります。
• Array#* は Array#join と同じです。

以上をまとめて、

[*$<]*""

で $<.read と同じ文字列が得られます。

標準出力に書く方法

1.8 では $ > < < 65 とかで "A" が出力されていましたが、1.9 では "65" が出力されてしまいます。なので dict = "\x00\x01\x02...\xff" という文字列を作って、$ > < < dict[65] とする必要があります。dict を作るのは、普通に書けば

dict = ""
(0..255).each {|i| dict << i }

という感じですが、当然こんな風には書けないので、再帰で初期化します。

dict = ""
func = lambda {|i| (dict << i; func.call(i + 1)) if i < 256 }
func.call(0)

lambda は -> にして、Proc#call は Proc#[] にして、

dict = ""
func = ->(i) { (dict << i; func[i + 1]) if i < 256 }
func[0]

256 は 4**4 にして、後置 if は && にして、

dict = ""
func = ->(i) { i < 4**4 && (dict << i; func[i + 1]) }
func[0]

数字を String#=~ にして、

dict = ""
func = ->(i) { i < ("####"=~/$/)**("####"=~/$/) &&
(dict << i; func[i + ("#"=~/$/)]) }
func[""=~//]

変数名を全部記号にして、

_ = ""
__ = ->(___) { ___ < ("####"=~/$/)**("####"=~/$/) &&
(_ << ___; __[___ + ("#"=~/$/)]) }
__[""=~//]

空白を取り除けば

_="";__=->(___){___<("####"=~/$/)**("####"=~/$/)&&
(_<<___;__[___+("#"=~/$/)])};__[""=~//]

わけがわからなくなります。

飽きたのでこの辺で。

追記:
嘘がありました (shinh さんありがとう) 。1.8 でも 1.9 でも $ > < < 65 は "65" が出ます。あと $><<(""<<65) で十分でした。もはや標準出力のために dict を作る意味はないですが、標準入力を ASCII コードに直すのに一応使ってます。s="A" から 65 が欲しいときに dict=~/#{s}/ とかして。こっちもなんかいい方法あるかなあ。

*1:ruby-core:16611 から延々と続く議論とか。

*2:cf. Perl の「記号だけで eval」 。