ErlangとQuine - no_orz_no

Quineとは自分自身を出力するようなプログラムです。出力結果と、元のソースを比較するとぴったり一致します。賢い人にしか書けないと思っていたので、私には縁がないと思っていたのですが、Google Code Jam Japan 2011 T-shirtによると、「Quine を書いたことが無いのなら、自分で書いてみることを強くお勧めする」とKen Thompsonが言っていたらしいです。artonさんの記事に触発されたこともあり、私もErlangのQuineにチャレンジしてみました。

Wikipedia(ja)と、Wikipedia(en)をざっと眺めて、おぼろげながら様子が分かってきたので、実際に書いてみました。printfの書式指定を使って簡潔に書く例があったな、という記憶を頼りに書いたのが以下のコードです。

main(_)->
S="~nmain(_)->~nS=~c~s~c,~nio:format(S,[34,S,34]).~n",
io:format(S,[34,S,34]).

実行するとなるとescriptの方がいいだろうと考えました。1行目はあけています。escriptはほとんど使ったことがないので、なぜ1行目をあけなければいけないのかは理解できていません。書き終わってから再度Wikipediaを見てみたらほとんどまったくそのまんまだったので、驚くとともに、試行錯誤にかかった時間を考えてちょっと泣きました。

簡潔に書く方法は分かったので、Wikipedia(en)にあるJavaのコードのようなアプローチを試してみます。Quineを作成する手順は、自分自身のコードを吐き出すための文字列(S)を作成する→それを使って出力する、となります。待ち受けている困難は以下のような感じでした。

自分自身のコードを吐き出すための文字列(S)、に含まれているコードには、自分自身(S)も含まれていることになりますので、ひと工夫しないといけません。
ダブルクォート自体を文字列に含めることが困難です。エスケープして使おうすると、出力結果の方にはエスケープがされてないものが出てしまうので一致させることができません。

前者は、Sの中身はコードには書かず(書きたくても書けませんが)、外側のプログラムで合成するようなロジックを書くことで回避できます。後者は、ダブルクォート以外の方法でダブルクォートと同等の働きをするものがあればそれを使えばいいのですが、Erlangでは適切なものが思いつかなかったので、シングルクォートで書いておいて、出力時にダブルクォートで置き換えるようにしてみました。

できあがったコードは下記の通りです:

main(_)->
S=[
"",
"main(_)->",
"S=[",
"@",
"],",
"print(S,S).",
"",
"replace(L,F,T)->",
"  replace(L,F,T,[]).",
"replace([],_F,_T,R)->lists:reverse(R);",
"replace([F|TL],F,T,R)->",
"  replace(TL,F,T,[T|R]);",
"replace([H|TL],F,T,R)->",
"  replace(TL,F,T,[H|R]).",
"    ",
"print(_S,[])->ok;",
"print(S,['@'|TL])->",
"  io:format('~s~n', [list_quoted(S,[])]),",
"  print(S,TL);",
"print(S,[H|TL])->",
"  io:format('~s~n',[replace(H,39,34)]),",
"  print(S,TL).",
"list_quoted([],R)->string:join(lists:reverse(R),[44,10]);",
"list_quoted([H|TL],R)->",
"  list_quoted(TL, [io_lib:format('~c~s~c',[34,H,34])|R])."
],
print(S,S).

replace(L,F,T)->
  replace(L,F,T,[]).
replace([],_F,_T,R)->lists:reverse(R);
replace([F|TL],F,T,R)->
  replace(TL,F,T,[T|R]);
replace([H|TL],F,T,R)->
  replace(TL,F,T,[H|R]).
    
print(_S,[])->ok;
print(S,["@"|TL])->
  io:format("~s~n", [list_quoted(S,[])]),
  print(S,TL);
print(S,[H|TL])->
  io:format("~s~n",[replace(H,39,34)]),
  print(S,TL).
list_quoted([],R)->string:join(lists:reverse(R),[44,10]);
list_quoted([H|TL],R)->
  list_quoted(TL, [io_lib:format("~c~s~c",[34,H,34])|R]).

手順を再度確認すると、以下のようになります。

プログラム全体をリスト化した文字列をSに入れます。
- ただし、S自体を定義する場所には"@"だけを入れておきます。
- また、文字列中の、本来ダブルクォートであってほしい部分はシングルクォートで代用しておきます。
mainの最後で、作成したSを出力するようにします。このとき、"@"をてがかりにしてS自体の定義を置き換えてゆきます。具体的には、以下のような流れになります。
- Sの各要素をシングルクォート→ダブルクォートに置換しつつ出力
  - "@"の行が見つかったら、Sを最初から最後まで出力しなおします。このときは、シングルクォート→ダブルクォートの置換を行わず、各行をダブルクォートで挟んだ上、カンマ→改行で区切って出力します。
- Sの残りの行について、シングルクォート→ダブルクォートに置換しつつ出力

実際にコードを書くときは、Sの定義以下の部分を、ダブルクォート→シングルクォートで置換した上で文字列として並べてゆけばOKです。

置換の処理は適切な関数が見つからなかったので replaceというものを作っています。なんだか随分長くなってしまいましたが、枠組さえ分かれば上記のように機械的に作ってゆくことができるので、あとは必要なものをどんどん実装(そして文字列を作成)してゆく手間だけの問題です。

問題といえばもう1つ、改行コードやダブルクォート、シングルクォート、カンマなどの文字コードを即値で指定しているため、これがどんな環境でも動くとは言えそうにないというのがあります。他の3つはともかく、改行コードくらいはどうにかしたいものですが...

さて、他の人が書いたErlangのQuineはないかな？と探してみました。
bkil's blog on science, programming, ecology, ...のQuineは鮮やかですね。~pと~sの違いを巧妙に利用しています。

思ったほど大変ではなかったというのが実際に作ってみた感想でした。今回書いたようなアプローチでは、言語ごとの有利/不利の差があるとしたら、文字列操作に関わる機能についてぴったり合うものがあるのかないのかという程度なのかな。そして、言語やライブラリの細かい仕様を把握している人ほど有利という意味ではcode golfに近いものがあるのかなと思いました(golfやったことないのに言うのも変ですが)。

(追記) shinhさんにanarchy golfにもErlangのQuineが投稿されてるよと教えてもらいました。140バイトの方はだいたい冒頭のやつと同じですが、104バイトのやつはすさまじいですね...

11> S="S=~p,io:format(S,[S])",io:format(S,[S]).
S="S=~p,io:format(S,[S])",io:format(S,[S])ok
12>

うーん、まったく思いつきませんでした。すごい。