downcase_quine.rb - 兼雑記

小文字英語(と空白)だけで書かれた、 ruby 1.8 で動く Quine (ただし 32bit 環境限定) 。久しぶりにおおーという感じのコードになりました。

http://golf.shinh.org/reveal.rb?Quine/shinh+%28downcase%2C+mame%29_1346029732&rb

追記: 32bit 環境限定じゃなくて短くなったバージョンも作りました。

http://shinh.skr.jp/dat_dir/downcase_quine.rb

このコードを作るのに考えたことなどを書いてみます。

id:ku-ma-me さんの方法

きっかけは id:ku-ma-me さんのこのスライドの話を聞いたことからでした。

http://www.slideshare.net/mametter/ruby-2012

ruby 1.9 で小文字英語だけでプログラムを書く方法として、2つ大変面白いテクニックを発見しておられました。

ひとつは

public
def each
  clear
  concat 112
  concat 32
  concat 49
  eval self
  exit
end
for i in inspect do
end

と書くことによって、 for で each を呼び出すことによって、 public な Object#each として定義しておいた関数を String を self として呼ぶ、というテクニックです。記号使わない縛りなので普通のメソッド呼び出しはできず、大文字が使えない縛りだと String#func を定義することもできないため、そう簡単には self のクラスを変えることはできないので、これは偉大な発見だったと思います。

もうひとつは

concat begin
  dup
ensure
  concat begin
    65 を作る
  ensure
    clear
  end
end

とすることによって self の先頭に任意の文字を一つつけることができるというイディオムで、 begin A ensure B end の評価順序をうまく使って、 = が使えないため変数が存在しない状態にもかかわらず、一時的に値を保管する場所を作るという、これまたかっこいいテクニックでした。

主にこの2つのすばらしい発見によって、 ruby 1.9 は任意のコードを英語小文字だけで書けるようになりました。私としては、これを Quine にしてゴルフ場に飾っておきたいなぁ、と思ったのですが、上記テクニックは2つとも ruby 1.8 では使えないため、別の方法を考える必要がありました。また、普通にやるとすごく長くなってしまうので、 10kB というゴルフ場の制限におさまる必要もありました。

理由としては、前者は String#each が ruby 1.8 では定義されてしまっているからでした。 String#each が定義されてしまっていると、 Object#each を定義してもデフォルトの String#each の方が呼び出されてしまいます。

後者の方は、 ruby 1.8 には String#clear が無いため、文字列を頻繁にカラにすることができないことと、単純にコードが長いというのも問題で、私のコードでは最終的には後者の方法は使いませんでした。

self を String にする

ここが最初の壁であり、そして一番悩んだところでした。既に書いた通り、 . を使ってメソッドが呼べず、 "class String" と書けない小文字縛りでは、 self を String にするのはすごく大変です。 String#each が明らかに邪魔なので、なんとかしてこの定義を除去できないかとも考えたのですが、これはどうも無理っぽい、という結論になりました。

次に考えたのは他の勝手に呼ばれる関数を使うことです。 Object#initialize を定義してやると .new で初期化した時にこっちが呼ばれるといいな…と色々ためしてみたのですが、 String#new が定義されてるためどうしようもありませんでした。もう一つは Object#=== を定義すれば case when を使うと間接的に呼ばれる、という案で、 String#=== は定義されてないのでできそうに感じたのですが、しかし === を定義するにはどうしても = という記号を使わなければならない、ということで無理そげ…と思いました。

最後に思いついたのが coerce でした。 coerce はたぶん数値を常識的な挙動にするためのもので、 coerce が定義されているクラスを右辺として Integer#+ などを呼んでやると、右辺の型を左辺の型にあわせて変えることができます。 String#coerce は定義されてない(されてたら 3+"4" が計算できてしまう)ので、これを思いついた時は、おおこれはいけそうだーと思いました。

coerce を発動させるためには、左辺を数値にして + などの二項演算を呼んでやる必要があって、 + はもちろん記号なので、記号を使わない二項演算を探す必要がありました。探してみると、都合よく quo という関数があるようでした。(後で気付いたのですが fdiv なんかもありますね…後述しますが使ってるアルファベット的にこっちの方が良い選択肢だったように思います)

あとは quo の左辺を数値にする必要がありますが、これは mame さんの発見された Object#each を定義する方法で、 Integer#each を呼んで self を Integer にしてやれば解決です。具体的なコードはこういう感じです。

public
def each
  # ここでの self は Integer 。 inspect は String をかえすので Integer quo String
  quo inspect
end
def coerce b
  # self が文字列になっている!
  p self
end
# Integer#each を呼ぶ。数値を適当に取ってくる手段として id を使う
for i in id
end

任意の文字列を作る

mame さんの二つ目のテクニックを使うためには、文字列を clear できる必要があるのですが、 ruby 1.8 には String#clear が無いため、他の方法を考える必要がありました。空文字列を得る手段としては delete self などがあるのですが、これは破壊的変更をしないため、得られた空文字列を self にする手段が必要になります。 Integer#each を経由している関係で、 String#coerce に好きな文字列を渡すことができなかったので、これはどうも無理、という結論になりました。いや、方法はありそうなんですが、それでも長くなりそうな気がしました。

というわけで、 concat に渡す数値をなんらかの関数のかえり値として得る方法があると考えました。 String#coerce が呼ばれた段階ではゴミ文字列が入っているのですが、これは Kernel#id のかえり値を文字列化したもので、要は数値なので、最初に改行を入れてやれば eval 中では問題なく無視できます。

考えてみるとこれは(他に比べると)比較的難しくなくて、

def i n
  def each
    yield succ
  end
  for r in n
  end
  r
end

などという関数を定義してやれば良いことに気付きました。これは (到底そうは見えないでしょうけど) 引数に与えられた数値を 1 インクリメントしてかえす関数で、これも同じく Integer#each を呼ぶ手法と、 for 文のループ変数が for の外に出た時もスコープが生きてることと、 Integer#succ を利用して実現しています。

この関数があると、

concat i i i size

などとすることによって、文字列の現在長+3 の ASCII 文字を文字列の末尾に追加することができます。最初にはったコードを見ると、かなりの部分のコードがひたすら i i i i i ... やら d d d d ... と続いていることがわかるかと思います。ちなみに d はデクリメントする方の関数です。

size の初期値は id.to_str のサイズで、これが 32bit と 64bit で違うので 32bit 限定になってる理由です。どっちでも動くようにするのは、まぁ別に難しくないと思います。

長すぎる!

これによって最初の一行のゴミ+任意の文字列を self にセットすることができたのですが、 Quine 本体のロジックをこの方法でエンコードしてしまうと、明らかに長すぎるという問題がありました。 10kB を越えるとゴルフ場は受けつけないので、このエンコードでは1文字エンコードするだけで 100B くらい消費してしまうので、本体が 100B もあればアウトです。これは問題ですし、美的にも良くないです。

ということで、最初に eval するコードは最小限のコードにして、 eval の中でもっと効率的な方法でエンコードされたデータを展開して、もう一回 eval してやろう、という方針になりました。この手の多段 eval は他の Quine でもやったことがあったので、まぁ割と自然な発想ではありました。

エンコードする方法としては、どうせ英語小文字しか使えないので、識別子の名前にしてやるのが良いだろう、と考えました。識別子は例えばローカル変数名として埋め込んでやれば local_variables で取ってこれます。識別子の中では英語小文字しかないので、必要な記号は、使ってない英語小文字から tr で置換して作ってやるとして

q=local_variables[1]
eval q.tr'gjkmwx','=.+" 
'

のようなものを eval で最初に呼ばれて、2段目の eval を起動するコードにしました。ローカル変数は for で作っていて、

for putsmpublicxdefwiwnxdefweachxyieldwsuccxendxforwrwinwnxendxrxendxdefwdwnxdefweachxyieldwpredxendxforwrwinwnxendxrxendxdefwcoercewbxconcatwsizemxhgmwmjsizexighkhxikgikhxikgixifwtruexngselfjslicewixforwvwinwhjjixngnjpredxendxifwnggnjabsxdgmiwmxelsexforwvwinwnknjjjhxngnjsuccxendxngnjpredxdgmdwmxendxogmconcatwmxforwvwinwhjjnxokgdxendxputswokmsizemxendwuntilwnotwselfjslicewikghxputsmforwmkqkmwinwselfxendxevalwselfxendxdefweachxquowinspectxendxforwiwinwidxendmx in self
end

という部分がエンコードされた 2段目の eval のコードになっています。よく見ると普通にコードっぽいことがわかるかと思います。

しかし今気付きましたが、 local_variables というのは長いので、 methods が使える def で関数名を定義してやるのが良さげでしたね…まぁ、 Kernel に既に定義されている関数の数に methods[XX] としてひっぱってくる部分の数字が依存してしまうので、こっちの方がクリーンではあります。

26文字種しばりプログラミング

2段階目の eval で呼ばれるコードは、英語小文字の文字列から tr して得られるものなので、 26 種類までしか文字が使えないことになります。最初は 60 種類とか使っていて、大丈夫かなぁ、と思っていたのですが、あれこれいじっているうちになんとか 26 種類におさめることができました。使った記号は =.+" と空白改行の 6 種類だけだったようです。

この結果が

puts"BOOT_HEAD"
h=" ".size
i=h+h
i+=i+h
i+=i
if true
n=self.slice i
for v in h..i
n=n.pred
end
if n==n.abs
d="i "
else
for v in n+n...h
n=n.succ
end
n=n.pred
d="d "
end
o="concat "
for v in h..n
o+=d
end
puts o+"size"
end until not self.slice i+=h
puts"for "+q+" in self
BOOT_FOOT"

というコードでした。 BOOT_HEAD と BOOT_FOOT は Quine のコード先頭部分と後半部分を出力する部分で、それぞれ適切な文字列に置換されます。ゴルフ的に不自然に長くなっている部分、例えば n=-n が

for v in n+n...h
n=n.succ
end
n=n.pred

などとなっているところは、 - を使いたくなかったため、という感じになっています。 quo より fdiv の方が良かった、と書いたのは、 f, d, i, v はいずれにせよ必要な文字種で、 quo は q が必要なのはここだけだったからです。これだと文字種にひとつ余裕ができるので、例えば - を使うようにすればほどほどに短くなるかとは思います。まぁ 1 段目の eval がサイズをだいたい決めている感じなようなので、あまり意味はないですけど。

コード

今回のコードは

http://shinh.skr.jp/dat_dir/gen_downcase_quine.rb

http://shinh.skr.jp/dat_dir/downcase_boot.rb

http://shinh.skr.jp/dat_dir/downcase_trampoline.rb

http://shinh.skr.jp/dat_dir/downcase_main.rb

として置いてあります。最初のコードが Quine を生成するコードで、同じディレクトリに置いた残り 3つをデータとして使います。残り3つはそれぞれ最初のコード、 1段目に eval される関数、 2段目に eval される関数、となっています。

コードサイズが 6582B とかあって、ゴルフ的にはまだまだ縮みそうではあるのですが、縮めるのも面倒なのでこんなところで良いかな、と思います。色々と問題があったものの、じっくり考えてあれこれするとほど良い時間 (と言っても coerce に至るところとかは 2日くらい考えてた気がしますが…) でなんとかなって、大変楽しい問題でした。考えるきっかけと重要なピースを作ってくれた id:ku-ma-me さんに感謝です…