python で Google Quine を再現させてみた
先日（といっても2ヶ月以上前ですが）参加した Google Code Jam Japan 2011 ですが、おかげさまで入賞することが出来、右の写真の通り、記念Tシャツを頂くことが出来ました。主催された方々、参加された皆さん、楽しい時間をありがとうございました。
ところで、このTシャツにプリントされたAAですが、これは ruby のスクリプトになっていて、これを実行すると自分自身のソースコード(つまりこのAAそのもの)を出力するという変わった性質をもったコードになっています。このようなプログラムのことを quine と呼ぶのだそうで、このTシャツのコードの作りかたは、Code Jam Tシャツについてに詳しく書かれています。
今回は、この Google Quine を ruby ではなく python で再現させてみよう、というネタです。
(余談ですが、このTシャツを受け取ってネタを思いついた翌日にはがっつり時間をかけてコードを完成させていたのですが、ブログのエントリへのまとめは2ヶ月も放置していたという……)
目標とするのは
- きちんと Quine になっていること
- 元ネタと(可能な限り)同形であること
- 元ネタと同等の機能(HTMLカラー出力オプション)を持っていること
です。
Python をご存知の方は判ると思いますが、Pythonはこのようなコードを書くのには全然向いていない特徴を持った言語です。やる前はかなり無謀な気がしていたのですが、いざやってみたらなんとかなってしまって、機能拡張も出来てしまいました。
今日の記事は完成品の紹介と、このネタをやるうえで障害となったPythonの特徴やそれに対するテクニックの紹介の紹介です。
完成品
先に完成形を出しておきましょう。こんなかんじです。
\ q='''f=l ambda (l,r),(p,m):( l+d(m )+r[: p],r[p :]); v=(_ _im port __(' s ys') .arg v+[0])[1 ];c=chr; s=c(32); n=c( 10);y=x TM =c(9 2);l=c(60) ;g=lambda( n):c(27)+' [%sm '%(n+30*( n!=0 ));d ,t=( (lam bda( n): '',' '),( g,' '),(l ambd a(n) :l+' fon t'+s+'co lor =%s> '%['black ','r ed','g ree n','yell ow' ,'b lue '][n ],l+'pr e>') )[(v=='-h') *2+ (v= ='- e')] ;pri nt(t +y+ n+red uce( f,z ip(( 20,1 4,13 ,11,7,11 ,3), (4,1 ,3,4, 2,1, 0))* 15+[( 990, 4)], ('',s *8+' q='+" '" *3+q+"'"*3+";" +s*6+"8;" +y+n+s*46 +"exec" +s*6+ "(''"+n+ s*47+"+''.j oin(q ."+n+s *48+"split ()))" ))[0]+ d(0)) ;88; '''; 8;\ exec ('' +''.join(q. split()))
このコードは Python 2.x用です。元ネタと同様、そのまま実行で自分自身を出力し、引数に-hを渡すと色付きHTMLで出力されます(元ネタみたく大量のタグを出したりしないので、Firefoxでもきちんと表示できます)、ついでに、-eでANSIエスケープシーケンスによる色付きテキストを出す機能も付けました。
形に関しては、1行目のバックスラッシュ1文字以外は元ネタと完全に一致するようにしています。それぞれの機能確認方法はこんなかんじ：
(元ネタと同様、quine となっているか) $ diff -u google_quine.rb <(ruby google_quine.rb) $ diff -u google_quine.py <(python google_quine.py) (元ネタと同形になっているか) $ diff -ub <(sed 's/[^ ]/x/g' google_quine.py) <(sed 's/[^ ]/x/g' google_quine.rb) (HTMLの出力が出来ているか) $ python google_quine.py -h > tmp.html $ firefox tmp.html $ diff -ub google_quine.py <(w3m tmp.html) (エスケープシーケンスでの色付けが出来ているか) $ python google_quine.py -e $ diff -u google_quine.py <(python google_quine.py -e | sed "s/\x1b[^m]*m//g")
インデントに意味がある
python はインデントで制御構造を表すため、インデント量には非常に強い文法的制約があります。
元ネタのように、コードの殆どを文字列定数に埋めてしまうにしても、「少くとも最初の1行は必ずインデント無しで始める」必要があるのです。
色々考えてはみたものの、さすがにこれだけは仕方が無いので、極力目立たない最小の表現に留める事で妥協しました。
方法は幾つかありますが、結局採用したのは、完成形で示したように、頭にバックスラッシュを1文字だけ追加する形です。このようにすれば、このバックスラッシュの位置が最初の論理行のインデント量を指定することになるため、次の物理行は先頭に幾つスペースが入っていても問題無くなります。
\ print "ここの物理行の字下げ量は自由"
他の手段としては、開き括弧を置いて暗黙の継続行とする方法があります。ただ、妥協した部分に必要以上の機能を持たせたく無いのと、括弧の中では「Statementが書けない」のを嫌って、バックスラッシュの方を採用しました。
代入など、多くの構文が Statement である
多くの C 言語 like な言語では、代入文は「副作用のある式(expression)」ですが、 python の代入文は statement です。そのため、「代入しつつ何かをやる」という表現が出来ません。また、printもpython2ではstatementですし、evalはexpressionである変わりにexpressionしか実行できないので、statement版のexecという別構文があります。
本家の解説で使われている
eval(q="puts q")
も、同じ事をするには
q="print q";exec q
と、2文に分けて書くことになるわけです。
改行を含む文字定数は専用の書式が必要
元ネタの方では ruby の "%p" というフォーマット文字列を使用していますが、python にも同等機能の "%r" という物があります。
>>> print 'quoted(%r)' % 'test' quoted('test')
文字列に対してこの書式として出力されるのは上記の通り「単一のシングルクオートで囲んだ文字列」です。ところが、このプログラムで出力したいのは複数行に渡る文字列定数なので、引用符で三重に包んだpython独特の記法で出力してやる必要があります。
これに対しては、%r を使わず、データ処理で必要な出力を得る事にしました。
>>> print 'quoted('+"'"*3+'test'+"'"*3+')' quoted('''test''')
この制限は一見するとquineを作る上でのデメリットに見えますが、文字列定数の中のコードでシングルクオートもダブルクオートも使えるようになる(三重にさえしなければ)ので、メリットでもありますね。
アルファベットのキーワードが多い
読みやすさが正義のPythonは、構文に記号が少ない事でも有名です。例えば論理和や論理積を使った演算は C では
result=a&&b;
のようになるところが、pythonでは
result=a and b
となり、文字数がかさみがちなうえに、普通に書くとキーワード間にスペースを入れなければなりません。
また、print文も、Python 2.x では expression ではなく statement なので、例えば文字列変数 a を出力しようと思ったら、普通はこう書くでしょう。
print a
ところが、元ネタを真似て、「ソースには整形用のスペースを埋めて、実行時にはそれを取り除いてevalする」という作戦で行くためには、文法上スペースが必須の構文を含めるわけには行きません。
このような場所でスペースが必要になるのは、変数名や関数名、アルファベットのキーワードなどが隣り合っている所で、字句解析上区別さえ付けば間のスペースは省略できますので、変数を括弧を挟むなど工夫してスペースを無くしました。
result=(a)and(b) print(a)
lambda 式の仮引数や、リスト内包表記なども同様です。
lambda a,b:a+b # スペースあり lambda(a),b:a+b # スペースなし [x**2 for x in range(10)] # スペースあり [x**2for(x)in(range(10))] # スペースなし
(なお、lambda(a,b):a+b だと意味が変わってしまいます(引数がタプル1個という事になる)。reduceなどの引数に渡すには不適切です。)
今回のコードを書く上では、殆どはこの対策で十分ですが、唯一、import 文だけはこの手が使えません。
import sys
import 文に書くモジュール名は代入の左辺値でも文字列でも無いので、勝手に括弧で括ったりする事は出来ません。import を使わないで済めば良かったのですが、元ネタと同じ機能にするためには起動時の引数を参照するために sys.argv が必要です。
これに対しては、 http://www.nishiohirokazu.org/blog/2006/08/python_12.html の「import文を式にする」を参考にして、下記のような表記を使う事でスペース無しで記述するようにしました。
v=__import__('sys').argv
制御構造文が使えない
Pythonでワンライナー的なコードを書こうとすると、制御構造文(forやifなど)は厄介です。
print 文などと同様にすれば 1行で書く事も出来なくは無いですが、ループの終端や、else節の終端を指定できないので、特殊なケースを除き、使用できません。
for(x)in(range(10)):print(x);print"end"; # endは10回表示される
とはいえ、今回作成するのは、プログラムのフローとしては単純な物で、分岐は引数処理のみ、反復も文字列処理だけなので、対処は容易です。
for文は意味を考えてリスト内包表記などに置き換えれば良いでしょう。
print"".join(str(x)for(x)in(range(10))),"end"
条件分岐は、and/or による振り分けか、3項演算子を用いることで表現できます。
(condition)and"TRUE"or"FALSE" "TRUE"if(condition)else"FALSE"
キーワードがアルファベットなので、各項は括弧で括るなど、スペース削除対策は必要です。
ただ、今回のプログラムでは、プログラムの引数に応じて3分岐(引数無し = そのまま。"-h" = HTML 出力。 "-e" = エスケープシーケンス出力)となるので別の方法を使いました。
Python では「論理式の評価結果である bool 型は int の派生型で、True = 1, False = 0 と評価出来る」という定義なので、この特徴を利用して以下のような形で処理しました。
(d,t)=( (引数無しの時にdに設定したい値, 引数無しの時にtに設定したい値) ("-e"の時にdに設定したい値, "-e"の時にtに設定したい値) ("-h"の時にdに設定したい値, "-h"の時にtに設定したい値) )[(v=="-h")*2+(v=="-e")];
条件によって変わる所を変数化しておいて、その変数をテーブル引きで一気に設定するわけです。
(なお、最終プログラム中では d は色換えコードの出力関数(lambda式)で、t は先頭に静的に出力するヘッダ文字列です。)
文字列の色付け加工処理
文字列に色を付ける際には、文字の色を付けたい所に適宜、HTMLタグなりエスケープシーケンスなりを埋めるわけですが、このような加工処理は関数型言語(Lisp とか)みたく、lambda式によるフィルタを行うつもりで書くと、大抵簡潔なワンライナーになります。
たとえば、こんな関数を定義してやれば、
f=lambda(l,r),(p,m):(l+m+r[:p],r[p:])
これは「タプル(l,r)に対して、lの後ろにmを足したうえで、rの先頭c文字をlに移す」というフィルタ関数なので、
>>> f(("","testing"),(3,"+")) ('+tes', 'ting') >>> f(f(("","testing"),(3,"+")),(2,"-")) ('+tes-ti', 'ng')
という風に多段に適用することで、文字を少しずつ加工しながら進めていけますし、さらにタプルのかけ算と reduce 関数を使えば
>>> reduce(f,((3,"+"),(2,"-"))*4,("","sample long string"))[0] '+sam-pl+e l-on+g s-tr+ing-'
と、繰り返しの加工処理も簡単に書けてしまいます。
仕上げ
変数qに包まれていない最初と最後のコードは配置の制約が厳しいので、先に調整しておいて、それ以外の場所は適当なまま一通りの機能を実装させたのがコチラです。
\ q=''' s=chr(32); n=chr(10); y=chr(92); l=chr(60); v=(__import__('sys').argv+[0])[1]; h=v=='-h'; e=v=='-e'; g=lambda(n):chr(27)+'[%sm'%(n+30*(n!=0)); d,t=( (lambda(n):'',''), (g,''), (lambda(n):l+'font'+s+'color=%s>'%['black','red','green','yellow','blue'][n], l+'pre>') )[h*2+e]; f=lambda(l,r),(p,m):(l+d(m)+r[:p],r[p:]); r=y+n+s*8+'q='+"'"*3+q+"'"*3+";"+s*6+"8;"+y+n+s*46+"exec"+s*6+"(''"+n+s*47+"+''.join(q."+n+s*48+"split()))"; r=reduce(f,[(2,0)]+[(20,4),(14,1),(13,3),(11,4),(7,2),(11,1),(3,0)]*15+[(999,4),(0,0)],('',r))[0]; print(t+r); '''; 8;\ exec ('' +''.join(q. split()))
この状態で quine としては成立していますが、まだ微妙に文字数をオーバーしているので、変数をインライン展開したり、細かな表現をかえたりして文字数内に収め、整形すれば完成です。
このプログラムで、これまでの所で説明していない細かい点を挙げるとすると
- argvの長さチェックは大変なので、末尾にゴミを足してチェックを不要に
- スペース、改行、バックスラッシュ、HTMLタグの不等号などは、そのまま書くわけには行かないので、chr 関数で生成
- 文字定数にかけ算で繰り返しを表現(スペースを沢山並べるのに使用)
ぐらいでしょうか。
こうして眺めれば、大したことはやっていないのが判ると思います。
python 3 だとどうなる？
ちなみに、このコードは python 3.x では動作しません。
python 3 と聞くと print 文の関数化あたりを思い出す方も多いと思いますが、このプログラムではスペース文字削除の都合で、print文の引数を括弧で括っているので、そのままで OK です。
じゃぁどこが問題か、というと、Python 3 では reduce がビルトイン関数では無くなったのと、lambda式の仮引数でタプルをアンパックしてくれなくなった所が原因です。
- http://diveintopython3-ja.rdy.jp/porting-code-to-python-3-with-2to3.html#reduce
- http://diveintopython3-ja.rdy.jp/porting-code-to-python-3-with-2to3.html#tuple_params
reduce は import すれば使えるとはいえ、文字数がかさんでしまいますし、lambda式の方はスペース文字の削除が不可能になってしまうため、根本的に考えなおす必要があります。
言い換えると、この辺りの機能は読みやすさを信条とする python として、公式に邪教認定されたという事なので、真似して使ったりしないようにしましょう(笑)。
なぜ制限が厳しいのに機能を増やせたのか？
python は ruby にくらべると、このような曲芸コードを書くのには向かない、文字効率が悪くて制限の多い言語なわけですが、rubyで書かれた元ネタよりも python で書かれたこちらの方が高機能な物が書けてしまいました。
それはなぜか。
それは、整形の処理に対するコードの方針が大きく異なったからです。
元ネタの方はTシャツに印字された物を手打ちしてもきちんと動作しますが、私の物の方はスペースを厳密に入力しないとおかしくなるので、印刷されたスペース文字を心眼で読める人以外はTシャツからの再現は出来ません。元ネタの方はこの弱さを嫌ってわざと面倒な方針をとったのではないかと考えられます。
元ネタの解説でも、このブログのエントリでも、その部分は詳しくは書いていませんので、気になった方はそれぞれのコードを解析してみるのも良いかと思います。
といったところで、今回のエントリはこれまで。たぶん年内はこれが最後の投稿になります。皆様よいお年を。
