Unix v6 の C コンパイラが面白かった話
Unix v6 の C コンパイラをいじってみようと見てたのですが、これがなかなかすごい物体でした。
読んでて、「いやいくらなんでもこんな作りなわけが…」と思って説明文を探して、
http://plan9.bell-labs.com/7thEdMan/v7vol2b.pdf
の「A Tour through the UNIX C Compiler」に説明あるよと教えてもらって読んでみたら、本当にそんな作りだった、みたいな。
コンパイラの1段目はプリプロセスして構文木的なものをファイルに吐いて終わりです。2段目は構文木を読みつつコード生成していく。
構文木のノードの種類に対して switch してやること決める…的なものが、データドリブンな方法で書かれてます。データを保存するフォーマットは、 JSON とかではなく、時代が時代ですのでアセンブリです。こういうやつ
https://github.com/mortdeus/legacy-cc/blob/master/last1120c/regtab.s
ちなみにこれは v6 より古い時代のコードらしく、だいぶ v6 のやつよりシンプルですが、まぁ v6 も本質的にだいたいいっしょです。
たとえば 60 番 (これは == のノード番号) を見てみると、
60.; cr60
となってて、 cr60 の定義は
/ relationals cr60: %n,n HC I 2f clr R br 1f 2: mov $1,R 1:
です。
最初の %n,n みたいなやつは、構文木にぶらさがってる左右の子が何者か、を示してます。 n はなんでもいいよ、っていうやつ。例えば %n,z だと右の子が定数ゼロなのでちょっと良いコードを出力する…みたいなことができます。
そこからはちょっとした VM というかなんというかの命令列です。大文字は全部特殊な意味があって、それ以外はそのままアセンブリとして出力されます。
HC は構文木のこのノードを含めてここから下を評価して condition code に置いて、という意味です。 I は自分のノード番号に対応する命令を置いてね、という意味。対応する命令ってのは
https://github.com/mortdeus/legacy-cc/blob/master/last1120c/c1t.s
に表になっていて、
60.; 0f; 1f; .data; 0:<beq\0>; 1:<bne\0>; .text
とあるので 60 番は beq です(2番目のエントリは bne ですがこれはちょっと特殊な用途や、命令 I' で出力できます)。
余談ですが 61 は != で、これの定義のしかたとかはちょっと素敵です。
60.; 0f; 1f; .data; 0:<beq\0>; 1:<bne\0>; .text 61.; 1b; 0b
1b は後ろにある最初にある 1: ってラベル、ってやつなんで、 1b; 0b だと bne beq となって、なるほどひっくりかえってるんですね。この c1t.s を見てやると、同じ定数文字列を意地でも二度出現させない、という気遣いが見てとれるかと思います。
話を戻して、 R は今使ってるレジスタです。というわけで元のコードは、 == が成り立ってれば beq 2f で 2: に飛ぶので R=1 、そうでなければ R=0 、という感じのコードを吐く…という雰囲気がわかるんでないかと思います。
今は regtab.s というファイルを見ていて、 regtab がデフォルトのコード生成戦略なんですが、他にもスタックに置きたいときの sptab 、 condition code をいじりたい時の cctab 、副作用が欲しいだけなので式を評価した値はいらない時の efftab 、の4つの戦略があって、さっきの HC だと cctab を参照するように変化してたわけですけど、これが例えば HS だと sptab を見るようになるはずです。
てーいうことで HC は regtab を使ってたのを cctab に切り替える効果があり、その実体は
https://github.com/mortdeus/legacy-cc/blob/master/last1120c/cctab.s
の
/ relationals cc60: %a,z tstB1 A1 ... %n,z F tst R ... %n,n FS S cmp (sp)+,R
にあります。これは長いので少しだけ見てみると、 %a,z は片方が既に addressible (つまり operand にそのまま来れるってことですな)で、かつ片方がゼロの時。こういう時は tst 命令一発、と。 B1 は A1 に対応する物体が byte か word かで b がついたりつかなかったりするだけ。
%n,z の場合は一旦レジスタ R に来てもらって…みたいな感じ。
一番一般的なケースの %n,n は、 FS は左辺をスタックに置いてね、 S は右辺をレジスタに置いてね、という意味で、最後の cmp はスタックを pop しつつレジスタと比較してる感じ。そのまんまですな。
なんというか、言語処理系の実装って、作る人の好みもあってか、メタな感じの実装になりがちだよねえと思ってたんですが、最初のコンパイラからしてこういうメタな作りかたしてたんだなぁと思いました。あと DSL って、こんな超初期の C コンパイラの時代からあったんだなあと。アセンブラ使ってるあたりは時代を感じさせますけど。
こんな作りになってる理由については、特に書いてなかったように思うんですが、コンパイラ自体のサイズの節約ではないかな…と思ってます。 == と != なら上記のようなことをして…みたいなのを C で書くより、こういうデータドリブンぽいやりかたでやった方がサイズ節約になる気がします。まあでも間違ってるかもしれません。
ppencode2
Shibuya.pm で ppencode 2 についての話をしてきました。
http://shinh.skr.jp/slide/ppencode2/000.html
つうてもしかしはてなんの話したらいいんだっけ感があって、なんの話をしたんだっけ。。
しっかしまあ、できたんだなーよかったねー感はありますね。
おまけというかなふたつ
http://shinh.skr.jp/obf/yuine_kw.pl
http://shinh.skr.jp/obf/yuine_sym.pl
はまあなんかそれなりに面白い気がしないでもないが…
これはまあ通常、通常てのが何かは知らんが通常、よりは少し大変で。
なんだか quote に足りない文字があったりすりがたいしたことでもなく
まとめるとねむくてだるい
Python 2/3 で小文字アルファベットと丸括弧だけで Quine を書く
http://shinh.hatenablog.com/entries/2015/05/11
の続き。 @mametter が next(reversed(range(i))) で i-1 ができるということと、 @phoenixstarhiro が unichr(x)in(list(unichr(y))) で x==y ができるということを発見してくれたため、現実的なサイズで Quine が書けました。
https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.py
https://raw.githubusercontent.com/shinh/hack/master/alparen_py/alparen_quine.py3
今までいろいろクソコードを書いてきて、 http://shinh.skr.jp/obf/ にある程度まとめてたりしたんですが、最近全然アップデートしてないので、 github に新しい置き場を作ってみました。
思いついた時に適当に色々足していこうかと思います。
Python 2/3 で小文字アルファベットと丸括弧だけでプログラムを書く
http://d.hatena.ne.jp/nishiohirokazu/20120906/1346938523
を読んで、なるほどー、でもカンマが必要というのは説得力が弱いな、と思ったので頑張ってみました。任意の Python コードを小文字アルファベットと丸括弧だけに変換できます。
http://shinh.skr.jp/obf/ppencode_py.html
根っこの部分
は西尾さんのコードと同じ、つまり
print(bytearray((XXX)for(x)in(YYY)))
です。これ正直私の Python 力では自力では出てこないと思いますね。。
西尾さんは YYY の部分が大雑把に ASCII コードに対応する物体の tuple になってます。ここに tuple が必要だというのが、西尾さんの「カンマを使わずにイテレート可能なオブジェクトを作ろうとすると…」の元だと思うのですが、まぁ range/xrange はカンマ使わないわけです。
任意の数字を作る
さて、 range 使うとなると文字列長をあらわす数字が必要です。特に 256 までは任意の文字を表現するために必須と言えます。
西尾さんはタプルの長さを使ったりして、適切なサイズの文字列を作って len してました。カンマが無いと、単項演算しか無いわけで、だいぶやれることが減るのですが、いろいろ考えてると、数値を引数として数値をいじってかえす関数をいくつか作ることができます。例えば
len(repr(zip(bytearray(i))))
は i に入ってる数値を 6 倍する関数です。こういう感じで、 3 倍するであるとか、 4 倍して 14 足すであるとか、微妙な材料が色々得られます。 2 倍とか +X とか便利なものはありません。要は repr で文字列を伸ばしていて、その前にした演算によって伸びる率が違う、って感じです。あとは数値を減らす手段としては bin, oct, str, hex を使って、 len(oct(i)) などとするのが唯一だと思います。これらは底を 2, 8, 10, 16 とした log_k(i)+1 として機能します。
まあそんな連中でも 1000 程度までの数字なら作れてたみたいです。残念ながら 256 文字も使えば既にすごく遅いので、 JavaScript でのエンコーダでは 255 文字までしかサポートされてません。できあがったテーブルは
http://shinh.skr.jp/obf/alpha_paren_py2_data.js
にあります。
これで、大元の for の右っかわができそうな気配です
print(bytearray((XXX)for(i)in(range(YYY))))
YYY にこの方法で生成した数字をあらわす式を入れれば文字列長だけのループが回せるのです。
テーブルをひきたい
さて XXX の部分です。連番の数字を入力として、テーブル引きをしないといけないです。普通のテーブル引きは [] とか , を使う必要があると思うので、ダメです。唯一考えられたのはクソ遅い条件分岐の連打です。こういうやつ
if i == 0: return XXX0 if i <= 1: return XXX1 if i <= 2: return XXX2 ...
i <= 1 をしたい
が、 i <= 1 から先は簡単でないです。数値 i を受け取って、 i が k 以下なら 0 、そうでなければ非ゼロを返す関数を作りたいわけですが…難しいです。手持ちの材料にあるのは定数かけ算と log(i)+1 です。そしてどっちも絶対に 0 を返しません。
なんかゼロになるもの…なるもの…と考えたところ、 48 がありました。 48 は '0' の ASCII code なので、 int(chr(48)) は 0 になるのです。というわけで、 1 を受け取ると 48 になって、 2 を受け取ると 49 から 57 の数字になる(Python の int 関数は数値じゃないもの受けると例外投げます)関数を探せば良いです。ありました。
len(repr(zip(bytearray(len(bin(len(repr(list(bytearray(len(repr(zip(str(bytearray(i)))))))))))))))
長いです。
比較をしたい
i <= 1 的なものができました。文字列長256までをサポートするとして、 256 個の i <= k 的な条件が並ぶので、残りの 254 個の k をどうにかしないといけないです。これは i が k 以下なら 1 、 k 以上なら 2 になるような関数をプログラムで探索すれば良いです。
0 を作るのと違って、これは割と現実的な話です。ひたすらかけ算を繰り返していくと、どこかでケタ上がりするわけで、 k 以下ならまだケタ上がりしてないけど、 k 以上ならケタ上がりしている、みたいな関数を探索すれば良いのです。 bin, oct, str, hex の 4 種類が使えるので、 2, 8, 10, 16 進数のどれかでケタ上がりしてれば OK です。
例えば、 i <= 3 は、 3 倍する材料は発見されているので、 len(str(i*3)) で良いです。 i == 3 の時は i * 3 = 9 はまだ 10 進数で一桁で、 i == 4 なら二桁になってるわけです。
この探索は、適当に総当たりをしたので、かなり時間がかかりました。
1, 2 だけにしたい
上記みたいな方法で作ると、 k より大幅におおきな数字に対して、 3 よりおおきな数字を返すことがあります。例えばさっきの len(str(i*3)) は i == 34 あたりから 3 を返しはじめちゃいます。
これの対処は簡単で、 len(str(i*6)) を繰り返せば良いです。 1 を 6 倍すると 6 なので 1 ケタですが、それよりおおきな数字はいずれ 2 に収束します。というかこれは log ですごく高速に収束するので、小さいプログラムの範囲では 1 回以上必要ないです。
これでできた比較用のテーブルは
http://shinh.skr.jp/obf/alpha_paren_py2_data.js
を CMPS2 で検索すると出てきます。
おまけ
なんのこっちゃですがだいたいこれ組み合わせるとできます。
str(bytearray()) の結果が全然違うため、 Python2 と Python3 両方で動くコードを作るのはどうも至難の技ぽかったので、しょうがないので別々にジェネレータを作りました。
あと、なんか Python3 のバグ踏んだ気がするので回避しておきました。暇な時に本当にバグか見ておこうと思っています。
重複なしで Hello, world! を Ruby だけで
CodeIQ に Hello, world! を3つ以上の言語で書きなさい、ただしそれぞれで使われてる文字種に重複があったらダメ、という問題がありました。
http://nabetani.hatenablog.com/entry/codeiq_hwx3_q766
私の解答は6言語使ったものでした。
http://shinh.hatenablog.com/entries/2014/03/18
今回は Ruby だけを使って、4つの Hello, world! ができました。言語が一つしか無いと複数言語を使うより色々なことをする余地が減るので、当然大変なので6つとかはちょっと無理です。
5つも厳しいかなぁと思っていて、なんらかの文字を出力する方法が4つ以上思いあたらないからです。4つというのは
- puts/putc/print 系
- IO#<<
- eval
- ラムダを使った eval
の4つです。あとは単純に任意文字列を作る手段が足りなくなっていきます。順に見ていきます
ひとつめ puts+putc 使用文字種10種類: " +89;cpstu"
putc 9+9+9+9+9+9+9+9;putc 8+8+8+8+8+8+8+9+9+9+9+9;putc 9+99;putc 9+99;putc 8+8+8+8+8+8+9+9+9+9+9+9+9;putc 8+9+9+9+9;putc 8+8+8+8;putc 8+8+8+8+8+8+8+9+9+9+9+9+9+9;putc 8+8+8+8+8+8+9+9+9+9+9+9+9;putc 8+8+98;putc 9+99;putc 8+8+8+8+8+8+8+8+9+9+9+9;putc 8+8+8+9;puts
色々試しましたが、最終的に丸括弧を消費すると最後で詰むので、丸括弧を使わない、つまり .chr などを必要としない putc がありがたいと判断しました。 8 と 9 だけを使っているのは、後で8進数を使うのでこいつらだけは余るのです。 10 は 8 と 9 では作れませんが、そこは puts で。
ふたつめ IO#<< 使用文字種12種類: "\n$/<=DOSTUz~"
STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST STDOUT<<z=<<SS<<z=/$/=~<<ST SS zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz ST ...
このコードは長いので以降省略。やってることは単純に、長い文字列作って、その長さを /$/=~ で調べて、それが文字コードになってるから文字列に << してその後 STDOUT に << する、と。
二つの << の優先順位が同じなので、なんとかするために = を使ってます。まぁ正規表現の =~ にも使ってるから丁度良い。文字列は <
みっつめ eval 使用文字種16種類: "\t%01234567Q\\aelv"
eval %Q%\160\165\164\163\42\110\145\154\154\157\54\40\167\157\162\154\144\41\12\42%
なんというか、そのまんまです。数字をケチってきたのでラクできます。
よっつめ lambda 使用文字種26種類: "!\"#&()*,-.:>?VW[]^_doqrw{}"
->(__){->(&_){_["",:"#{__[?q.ord^?>.ord]}r#{__[?d.ord^?,.ord]}#{__[?d.ord^?).ord]}#{__[?r.ord^?!.ord]}#{__[?d.ord^?!.ord]}","#{__[?q.ord^?V.ord]}#{__[??.ord^?{.ord]}#{__[?q.ord^?:.ord]}#{__[?q.ord^?:.ord]}o,#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}#{__[?{.ord^?-.ord]}or#{__[?q.ord^?:.ord]}d!#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}",?w.ord^?W.ord,?w.ord^?}.ord]}[&:"#{__[?q.ord^?#.ord]}#{__[??.ord^?{.ord]}#{__[?d.ord^?).ord]}d"]}[[*?!..?}]]
知らないと意味不明ですが、 Ruby で記号だけで Turing complete にするための、 ->(&_){_["",:"eval","code..."]}[&:"send"] というイディオムを使ってます。ここに ->()[]{}#: などを残すためにこれまでで苦労してました。
追記。 () 残す必要は無かったでした。
->__{->&_{_["",:"#{__[?q.ord^?>.ord]}r#{__[?d.ord^?,.ord]}#{__[?d.ord^?).ord]}#{__[?r.ord^?!.ord]}#{__[?d.ord^?!.ord]}","#{__[?q.ord^?V.ord]}#{__[??.ord^?{.ord]}#{__[?q.ord^?:.ord]}#{__[?q.ord^?:.ord]}o,#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}#{__[?{.ord^?-.ord]}or#{__[?q.ord^?:.ord]}d!#{__[?_.ord^?[.ord]}#{__[?d.ord^?&.ord]}",?w.ord^?W.ord,?w.ord^?}.ord]}[&:"#{__[?q.ord^?#.ord]}#{__[??.ord^?{.ord]}#{__[?d.ord^?).ord]}d"]}[[*?!..?}]]
感想とか
どこに何を使うか、割と苦労したんですが、トリッキーなコードを書くとどうしても文字種消費しがちなため、完成してしまうと割とシンプルな4つになりました。難易度的にも言語バラバラ6種の方がやや大変でした。
5つ目は文字を出力する手段さえあれば、かなりキツいでしょうがなんとかなるかもしれません。ずるいですが `` を活用するとかも考えましたが、 1>&2 を使わずに出力できる気がせず。
Perl で同じことをすると、拡張正規表現での eval が使える少し古い Perl でも 3 種類が限度なんじゃないかと思っています。 id:ku-ma-me さんと Perl と Ruby がどっちが強いかみたいな話をしていたのですが、この問題なんかは割と象徴的な気がします。
ppencode 2 - 任意の Perl コードを予約語だけの Perl コードに変換する
@TAKESAKO さんが ppencode を作ってから 10 年経って、私が任意の Perl コードを小文字だけに変換するスクリプトを書いてからでも5年経つらしいですが、なんか任意の Perl コードを予約語だけの Perl コードに変換するスクリプトができました。
http://shinh.skr.jp/obf/ppencode.html
オリジナルの ppencode に敬意を表していろいろ雰囲気を似せておきました。割と色んな予約語が使われるようにしてみたりとか。
これは Perl が予約語だけあれば Turing complete ということなので、副産物として Quine もできました。
http://golf.shinh.org/reveal.rb?Quine/shinh+%28keywords%29_1431106882&pl
なんというか、 ppencode があれば後は print を eval に変えるだけちゃうん？という当然の疑問があると思うのですが、 ppencode より割と大変だったりします。 ppencode は要は
print chr 72 xor print chr 101 xor print chr 121 # Hey
みたいな感じで実現できて、数字の部分は length q q XXXX q とかしてやって XXXX の部分を q を含まないキーワードで適当に埋めてやれば OK です。
ただこれは文字数だけ print を呼べば良いからできる方法であって、 eval みたいに文字列を一旦まとめる必要があるとダメ。
小文字アルファベットしばり PerlやBase64 しばり Perlでは s//something/e を最初に連打することによって、好きな文字列を作ることができましたー、というのがこれまでのあらすじ。
これを予約語だけでやろうとすると、
s XX chr length ????? XYYY xor ... xor eval
の形になるとして、 X は 1 文字の小文字アルファベット、 YYY は e を含む文字列で正規表現の modifier として valid で、かつ、 XX と XYYY は予約語でないといけない、という条件になります。 XX と同じ文字が並んでる予約語は qq しか無く、 q ではじまって e を含む唯一の予約語である quotemeta は t が modifier として不適切です。
ああ、詰んだな、と放置してました。今回気付いたのは、1回の正規表現置換で無理なら2回やれば無理かなーということで、
s qq q s X X chr length ????? XYYY
の形、つまり最初に空白を足しておいてから、その空白を本命の文字に変えれば良いのではないかと。 X が連続してなくて良いので、 X の候補が m, q, s, x, y の5つに増えます。最初、 X = s, XYYY = sleep がうまくいきそうな気がしたんですが、 e が2つあると2回 eval されちゃって扱いにくいったらありゃしないのでもうちょっと眺めてると、 semop がありました。ありがとう POSIX 。まぁ splice とかも該当すると思いますが。
ここまで来るとあとはやるだけーと思ったのですが、空白を含んだスクリプトがうまく変換できません。一番最初にある空白を次の文字で入れ変えていくので、空白を詰めてしまうので。 print "Hey" だと
___________ # 最初に 11 文字空白を確保(_ で空白を示します) p__________ # 1文字ずつ空白が置きかわっていく pr_________ pri________ prin_______ print______ print______ # 空白を空白に置き変えてる print"_____ # 詰められてしまった print"H____ print"He___ print"Hey__ print"Hey"_
というように変換されていく感じ。 JS コード中の ppencode_core がこの変換をしてます。
こういう場合はまあ、空白が無い、評価すると空白を含んだ Perl コードになる Perl コードを作って、 2回 eval すれば良い…とのことで例のごとく version string に活躍してもらいました。
print "Hey" だと
$_="";v112.114.105.110.116.32.34.72.101.121.34
というコードを ppencode_core でエンコードして、これを2回 eval すれば良い、と。最初の $_=""; は $_ をいじってるとあまり厳密な変換じゃないな…と思ったからつけただけです。
長い間、「普通にできんじゃねーの？」→「あれ、できないな。。」を定期的に繰り返してたので解決して良かったと言えます
Base64 decoder/encoder in Perl
http://shinh.skr.jp/obf/b64_dec.pl
dXNlIE1JTUU6OkJhc2U2NDtwcmludCBlbmNvZGVfYmFzZTY0IGpvaW4nJyw8PjsKX19FTkRfXwo+ s//v62/e+s//v60/e+s//v44/e+s//v39/e+s//v39/e+s//join/+s//v32/e+s//base64/ss+ s//v95/e+s//decode/+s//v32/e+s//print/+s//v59/e+s//Base64/+s//v58/e+s//v58/e +s//MIME/+s//v32/e+s//use/s/eval
この Base64 ぽく見える物体は Perl コードで、実行すると引数で指定したファイルに対する base64 デコーダとして機能します。
$ perl b64_dec.pl b64_dec.pl > b64_enc.pl
元々のコードは Base64 でもあったので、 Base64 デコーダによって復元できました。復元されたスクリプトは Base64 エンコーダになってます。よって、
$ perl b64_enc.pl b64_enc.pl dXNlIE1JTUU6OkJhc2U2NDtwcmludCBlbmNvZGVfYmFzZTY0IGpvaW4nJyw8PjsKX19FTkRfXwo+ s//v62/e+s//v60/e+s//v44/e+s//v39/e+s//v39/e+s//join/+s//v32/e+s//base64/ss+ s//v95/e+s//decode/+s//v32/e+s//print/+s//v59/e+s//Base64/+s//v58/e+s//v58/e +s//MIME/+s//v32/e+s//use/s/eval
で元に戻ります。
