irbrc を書いたら ruby 1.9 とだいぶ和解できた話
いつも言ってることだけど、 ruby 1.9 からの m17n のせいで、バイナリツールとしての ruby が色々不便になって、参っていました。特に、 'a' の ASCII code を知るのに、
irb(main):001:0> 'a'[0] => "a"
とかやるクセがついてて、これで "a" と出るとか、そういう比較的どうでもいいところで参ってました。
しかしまぁどの環境も ruby 1.9 以降になってるわけで、なんとかしないとなーということで、 IRB の inspector いじって色々やってみて、結果として 1.8 時代より便利になって、最近は割と普通に使えている。
https://github.com/shinh/test/blob/master/.irbrc
何をしてるかというと、評価した結果が文字とか数値だった場合に、補助情報を色々出すようにしてある。で、
irb(main):001:0> 'a' => a (97) irb(main):002:0> 99 => 99 (0x63 'c') irb(main):003:0> 2**25 => 33554432 (0x2000000 33M) irb(main):005:0* 0xf7e04000 + 0x41060 => 4158935136 (0xf7e45060 4158M)
などなど。最初の2つは文字と数字の変換結果がついでに出てて便利みたいな話。3つ目は 33M など、数字のだいたいの大きさが出ると便利という話。最後のはアドレス計算とかで特に最近こういうのよくやるので、 16 進数出てると便利。
それ以外にも色々歴史的にちょっとずつ足している機能があって、よく使うのだと、
irb(main):016:0> (99999*29999).cint => -1295097295 (0x..fb2ce6231)
31bit overflow してる時に、 C の整数だといくつ、ってのが意外とぱっとわからなかったりするので。 cuint もあるけど、まぁそっちはあまり使わない。
irb(main):010:0> asm("xchg eax, edx")
000000 92 >.<
000001
=> nil
irb(main):011:0> disasm("\x55\x57\x31\ff")
/tmp/irb_disasm20140904-6135-1vk633j: file format binary
Disassembly of section .data:
00000000 <.data>:
0: 55 push %ebp
1: 57 push %edi
2: 31 0c 66 xor %ecx,(%esi,%eiz,2)
=> nil
HITCON CTF 2014
CTF ていう、セキュリティコンテスト的なやつ、前から少し気になってたんだけど、おすすめしてもらったこともあって初参加してみました。結果は 20 位。大変たのしかった。
リポジトリ: https://github.com/shinh/hitcon-ctf-2014
vash 10
練習的なやつ。いきなりホームディレクトリに flag てファイルがあるので、それの中身を提出してみるが、ダメ。おかしーなーと find とかして他のファイルを探してみるけど、特に何もなく。
そのうちわかるだろう、と、あまり気にせず次へいった。真相は運営のアレコレでまだ submit が動いてなかったらしい。 TLE とか ICFPC とかの脱力運営に慣れてるので、こういうのでハマらない…
rsaha
RSA を解け的な問題。ただし、通常 m^e mod n だけしか教えてもらえないはずなのに、 (m+1)^e mod n もわかる。
これは3次の項が消えるので、 e が phi(n) と互いに素という条件を満たせてなくて、ダメってことかな…と思った。正しいかは知らない。そうだとして、はてこの間違った e を選んだ時の破りかたなんてわからないぞ…と考えてた。
ついでに web service を攻撃する系も見てみるが、よくわからない…と考えてるうちにバイナリ問題が追加されたのでそっちへ。
rsbo 150
ディスアセンブリ見てると心がいやされるなーと。いやされる。なんだか知らんが、おもむろに flag のファイルを読んだあと、メモリをクリアしてから意味不明な入出力をする、という素晴らしいプログラムらしい。
入力の部分、 0x70 確保してから最大 0x80 読むとかしてて、少しだけあふれちゃっているようなので、ありがたく return address を書き換えさせていただこうと思う。しかしあふれてる量が少なすぎるので、これどーしたもんかなーと考えてた気がする。あと RWX な領域もないし、 RELRO も入ってた…と思う。
しかしまぁ案ずるより生むがやすしで、実際はじめてみると、 0x80 読む関数に一段階目でもう一回飛んで、今度は大幅に色々書けるので、 return to libc で適当に open から return した先が引数の stack ぶん捨てて ret するコード片で、そこから read に行って引数捨てて write に飛ぶ、みたいな経路を作ってやった。
都合の良いコード片は ROPgadget というやつを見つけたので、それを使って探してみた。これ便利だな。
あたり前のように書いてるが、人生二度目の buffer overflow で実際に攻撃してみた経験なので楽しかった。
ここで vash も投稿できると気付いて2問。 3:42 (3時間42分経過という意味)
ty 150
rsbo やってる最中に増えてたバイナリ問題をやる。 Aarch64 です。 Aarch64 の objdump とかは入れてあったんだけど、 gcc とか qemu の使う lib とかがセットアップされてなかったので、入れながら他の問題眺めたりとか。
この問題は、なんか入力を受けて、そのコードを実行してくれます、と。ただし、実行する前に /dev/urandom からの入力との xor を取るので、ランダムなコードを実行することになって死ぬ。
ええとどうやったんだっけ。これまたオーバーフローさせれるんで、 /dev/urandom を open した fd の入ってるスタックの中身を 0 に変えてやって、 stdin からゼロを流し込んで xor を no-op 化する、て感じだったと思う。
あとは Aarch64 のコードを頑張って書いてやる感じ。 Aarch64 てことを除けば前の問題の方が難しかったと思う。しかし data 領域が実行可能ってのは、もはや馴染みがなくて、違和感があるっていうか、最初はどうやって protect 外そうとか無駄なこと考える感じになっていた。 6:52
tarmful 128
他の問題にハマってる間に、 tarmful という雑用ぽい問題が増える。単に 1024 回、ヘンなファイル名とか経由しながら圧縮されてるファイルを展開するだけ。適当なスクリプトで解決。 9:32
hop 350
ハマってた問題だと思う。 Windows バイナリがあって、 flag を入力すると Correct! てでるようになってるんだけど、単に strcmp してくれてるわけじゃなくて、入力1文字ごとに jmp table でどこかに飛んで、ってのを繰り返して判定しているらしい。 jmp table の関係を探らないといけない。
さて Windows バイナリですよ…ということで WINE を使っていたものの、イマイチ不便で、 cygwin64 などをセットアップしてみたり、しかし Windows というやつも不慣れで不便だなぁ…となる。このあたりでパスワードをチェックする部分は特にシステムの関数とか呼ばない気がしてた。
それなら比較的お得意のやつですなーと、 Linux 上で Windows バイナリ内のそのチェックする部分をロードしてみてやる。うまく動く。こうなりゃしめたもんと、 jmp table の連鎖になってることとか、そういう構造がすぐわかる。
でー、 jmp table の連鎖からグラフ構造ができたのだけど、しかしこのグラフ構造、最短経路を取れば正解というわけではなく、ちょうど40文字で到達できるパスが正解という感じ。どうすればいいんだこれは、とはまる。
バイナリの内容わかってから解けないのはくやしいなーと思いながら寝る。
起きてから、アレコレとやってるうちに、それぽい単語が頻繁に出たりしてくるので、それを正解と仮定してアレコレ調整…みたいなことをやってると、正解に辿りつく。 15:05
TLE でもこういうのあった気がするなー。
mid
これはハマって解けなかった問題。 ACM ICPC 形式の問題ということで、長い数値列の median を求めよと。ただしメモリ制限が厳しいので頑張ってね、と。
んー pipe かな、てことで pipe にデータを置いてやるプログラムを作る。しばしバグとか取って、んーこれでいいと思うんだけどなーというものが全然通らない。
最初は bss 領域使うとなぜかメモリリミットが実は越えてたとかで、そっちも修正したり。でも最後まで通らなかった。終わったあとの話によると pipe でいいらしいし、 return まで行ってから sleep すると 1 秒余計に消費するので、答えが間違ってたってことですかねえ…しかしテストケースはそれなりにあるんだけど。
polyglot 500
mid や callme 、あるいは他の問題に無駄な時間を使ってるあいだに、 polyglot という問題が追加される。超得意分野なので、俺を誰だと思ってる的な余裕で瞬殺。いや、それなりには苦労した。 Haskell, Python, C は意外と polyglot 力が低い言語なんですよ。
この問題は最初の解答者だったらしく、主催からどんな解答だったん? みたいなメールが来る。このあとたしか寝た。 22:25
sha1lcode 300
callme と 24 にハマりすぎてたので、他のバイナリぽいの見るか…と見る。なんだこれは得意分野じゃないか。
自由な入力を、 SHA1 してコード領域に置いてから実行する、って話。適当にランダムな SHA1 結果のコードを見てみるも、当然ながら使えそうなものは無い、からもっとちゃんと狙ってやらないといけない。
高度な数学とか使わなくても、適当に探せば 2,3 bytes のコード片は見つかることは、 ShaFuck を潰した時 にもやったので、同じことをやる。
今回は、先頭に次の code chunk の終端 2,3 bytes 前に jmp するコード片と、終端でなんか 1 命令実行するコード片を探した。 36:38
ducky 250
なんか (){}; を使わずに C コードを書けという、どこかで見たような話が…技を借りるぞーということで kik さんの技を使って倒す。 37:34
24 256
いやーハマっていた。与えられた4つの数字と、四則演算子を組み合わせまくって Python3 で eval して、その結果を 24 にするクイズを 24 回解けというもの。
普通に Ruby で書いて、累乗とか // も必要かーと足して、色々足して、でも最後の問題が解けない。最後はヘンな工夫がいるのかなーとずっと考えていた。
しかしどうも結論としては Ruby で書いてたせいで、 Python のシミュレーションが不十分だったらしく、手であれこれやってるうちに、アレっこれ Python は複素数出るからこれかな…とかやってるうちに、複素数使わず手で解けた。
反省としては、嫌いでも Python 使いましょう。 39:49
callme 350
長い時間考えてた問題。ほぼ諦めて日曜の深夜に寝て、月曜の朝起きてから、解法らしきものが見つかって、なんとかまにあった。
sprintf での buffer overflow があるんだけど、 stack smashing protector がかかってるので、 return address を書き変えたところで、 ret するまでに __stack_chk_fail する。
しばらく勘違いしてたんだけど、この問題はよく見ると RWX なページはあるし、 RELRO もかかってない。つまりなんでもいいから RWX なとこに飛べばそれで勝ちで、そこが問題の本質なんだなぁとか考えるもわからない。
しょうがないので起きてからやったのは等価ぽい C のコードを書いてみたりして。生システムコールで入出力してるとかが気になったりしたけど、たぶん関係なかった。
でまぁ C のコードながめてると、 sprintf に渡してる書き込み先は stack なんだけど、よく考えると format 文字列自体も stack のだいぶ高位のアドレスなんだよな、と気付く。つまり sprintf で書いてる最中に format 文字列が変化して、当初の予定よりどんどん伸びていく…技が可能だ。つまり、 "%s%s\n\0" みたいな format だったはずなのに、自由に設定できる2個目の %s を解決してみると、 "aaaa%d%d%d.." みたいな感じで書きかわってるーみたいなことができると。
あとは、なんであるか不明機能であるところの %n を使って、 __stack_chk_fail の GOT をいじって RWX な自由な空間に飛ばしてやる。思うに __stack_chk_fail の GOT とか、もうちょい防衛してやってもいい気がするんだけど。
あと、これで死ぬ時に行く先である、 __fortify_fail は stack の argv[0] を出力しようとするから、書き変えてやれば memory exposure になる とか知って少し脱力した。今回 SSP に対する攻撃手段を色々調べていて、今回は全く役に立たなかったというかむしろ混乱したけど、しかし勉強になった。
あとは時間に間に合うかーという感じで、あれこれやって、あわてて shell code 書いて、なんとか通った。 shell code くらいはいい感じのを自分で作っておくと良いんだろうな。 46:50
感想
たいへん楽しかった。普段は守る側…に自分が直接いるわけではなく、しかし守る側の人を比較的近い距離で眺める、みたいなことが多いだけに、知ってる知識を逆側に使えるのは楽しい。曖昧な理解になってるところがハッキリするのも良い。
MD5 とか RSA とか、暗号系も興味があるんだけど、全く手が出なかったのは残念だった。まぁ一人だと時間的にもキツいが、それでも勉強しておきたい感はある。ネットワーク系も手が出なかったんだけど、しかしそっちはそもそも興味があまりなくて…
あと一人は楽しいものの、やはりキツい。問題が増える速度の方が解く速度より圧倒的にはやい。チームでやってる人は、何人くらいでやってるのかなぁ。こういうルールだと、組んでやるのもやってみたくはある。
ICFPC 2014
総じておだやかに楽しかった。
https://github.com/shinh/icfpc2014
1日目
初日、21時から問題を読む。んー普通だなーと思いつつとりあえず寝る。
起きて Lambda-man の AI を書きはじめる。普通だと思ったけど、 Lisp マシンってこういうふうな感じなんだなぁ、と、知らなかったので普通に勉強になった。とりあえず思った通りに動くものを作ろうということで、アセンブラを Ruby 上の DSL として書く。オペランドの数と型のチェックと、ラベルの解決をするくらいのやつ。
なんとなく何ができるかわかったところで、これはアセンブラ直書きは大変だし変更に弱い…ってことで、そのアセンブラの上に高級言語を作る必要を感じる。素直に Lisp でもいいけど、あまり Lisp 書き慣れてないので、 Ruby 上の DSL をもう1レイヤ重ねることにした。あとは beflisp の知見を生かして、 LLVM bitcode からの変換ってのも考えたんだけど、そういうのがしたければ複数人がいないとな、て感じ。
きちんと理解する時間がもったいなかったので、 Lisp マシンぽいところなのか、難しそうな命令は無視して、 store 命令を使いまくって、普通にローカル変数をいじりまくるような作りにした。こういうのは書き慣れてるので、割とするっと書ける。引数用に用意された frame だけではローカル変数を置けないなーと思ったので、全ての関数は引数と local 変数を置けるもっと広い frame を作ってから、実際の実装に関数 call する、ってことにした。関数呼び出しのオーバーヘッドが大きくなるけど、関数をあまり呼ばない作りにすれば問題ない。コードサイズの制限はゆるいし、命令キャッシュとか無いわけで、 Ruby のレイヤで関数作ってやれば、 template みたいな感じでコードサイズが大きくなる方向でコードの再利用はできるし。
で、できた DSL で、とりあえず時間とともに移動方向を順番に変えるような AI を作ってみた。これは書きにくいなーということで、 AI を書きながら、色々書きやすくしたりした。まぁそれほど良いものでは無いけど、これで最終日まで戦えるかな、って程度にはなった。
各地点への最短距離を調べるコードを DSL 上で書く。配布されてた3つのマップはクリアできるようになった。よく死ぬのが微妙なんで、敵をある程度避けるようにした。直線上で向きあう動きと、2マスだったかそのくらい接近するのを避けるようにする。
最短距離を調べるコードは getXY とか setXY 的な処理をしまくっていたので、デカいマップで不安だった。これは無理かなぁと思いつつデカいマップで試してみると、当然ダメ。
しょうがないので、最短距離調べるアプローチより弱くなるだろうな…と思いつつ、スコア源に引かれる重力モデルを実装してみる。これでもデカいマップはきつかったけど、速度的にはかなり良くなってたので、見る範囲をしぼったりして対処。しかしやはり弱くなる。
ていうかヘンなところにひっかかったりする。なるべく1ターン前のところに戻るのはイヤがるようにしたりすると、まぁまぁ動くようになる。しかしやはり弱くなったように感じる。
あと1時間くらいでライトニング終わるなーというところで、あ、自分からの近距離だけの map に対してだけ最短距離調べるようにして、それとのハイブリッドにしたらいいんじゃね、と気付いて実装したらかなり良くなった。ただこの時のコードには、左端と上端にいる時に動作が不審になるバグがあったと最終日に気付いた。
この Lambda-man の DSL は Ruby のコードと DSL ぽい部分が混じりまくって (Ruby のループの中で DSL の whileP とかいうループが回ったりしている) 見た目がすごいことになってるのだけど、割と私一人が書くぶんには大丈夫程度のものが、割とスルっと書けたので満足することにした。
うーん ghost の AI も書くのかーとなるとシミュレータも書かないとだなー盛り沢山だなぁ、シミュレータの言語は何にしようかなぁ、と寝る。
2日目
2日目にシミュレータを書く、ってのは割と恒例ではある。言語は GC が欲しいな、ってことで Go にした。 D 言語と悩んだけど、既に入ってた Go に軍配が上がった。 Go はまぁちょくちょく触れるけど、書きやすいよね。 Google 社員的にはノリにすごい慣れてるんだよな。 C++ でもこんな感じのコード書いてるよなあ、っていう。あ、 Chrome とかはだいぶ違うけど。
で、 ghost や lambda-man の処理系は、拍子抜けするくらい簡単に作れたのだけど、そこからがこれも恒例の、ゲームロジックの挙動が微妙に違う祭り。ひとつひとつ仕様の読解/理解ミスを正していく。これはいつも以上にドキュメントが量も多くて細かいところに不明なところが多くて大変だった。途中である程度あってりゃいい気もしてやめようかと思ったけど、まぁ信用できない部品を放置するのは ICFPC ではやばい、っていう経験則からがんばった。
最後はリファレンスインプリのバグまで再現して、あとまあ同時にイベントが起きた時のコーナーケースにミスはあるだろうけど、ってあたりまでやって、終了。しかし、途中で、リファレンスインプリのバグはご丁寧に修正されてしまったので、リファレンスインプリと不整合な結果を返すのは我慢して戦うことになってしまった…
次は ghost を書いてみる。今度は Lambda-man 用のアセンブラをちょっといじって ghost アセンブラを Ruby 上に作る。んーなんか 256 instruction くらいならこれでいいんじゃね、ってことで、それで良いことに。
どういうのがいいのかなぁと考える。素直に襲いかかるやつと、一箇所をひたすら防衛するやつ、とかを考えた。後者はいかにも弱そうなので、襲いかかるやつを作ってみた。適当に作ると、これが結構強い。 Lambda-man が虐殺されている様を見るに、あーこれは効率良く pill を集めるとかよりは、避けゲーかなーと思う。
ただ、適当に作った素直に襲いかかるやつは、最初のサンプルマップの初期位置にひっかかる。あたりまえである。というわけでランダム要素とかをちょっと入れてみる。だいぶ良くなるが、まだみんな同じ行動しがちで意味がない。他の AI の案が思いつかなかったので、もうちょっと散らすことにした。具体的には本家パックマンを参考に Lambda-man が向かってる先を目指す、っていうヒネりが無いやつ。
このへんで、はて一通り提出できる体裁はととのったが、はてどこに力を入れるべきか…と考えつつ寝る。
3日目
なにすっぺかなーと考えつつ、細かいバグとかをなおす。感覚としては、 Lambda-man にもっと高度なプログラム的に賢いことをさせるべきだ、ってのがあった。例えば ghost をシミュレーションして短期間の未来予測をするとか、グラフ構造を作って危険な道とか安全な道とか考えて動かすとか、そういうの。
ただこれは与えられてる clock cycle であるとか、自分のアルゴリズム知識的なことと、あとそもそも ghost は適当に襲いかかるだけでも Lambda-man には結構脅威、ってことから、なんかやってみるかなー別にいいか…ってのを繰り返してるうちに終了した。まぁやんなくて良かったんじゃないかなーと思ってるが、謎。
というわけで、なんか割と作りたい雰囲気のものができてしまっているので、細かい完成度上げに使った地味な一日になった。あと途中で昼寝した。 ICPFC 中に5回寝たのはたぶん新記録。
地味なんだけど、結構 AI の細かい作りこみみたいなの、わりと好きなようで、1日だけだと結構たのしい。
まず、 ghost 強すぎ…ってことで Lambda-man の回避装置をちょっとマシにしてみる。いまいち。ていうか Lambda-man 死ぬ時はだいたい挟まれてるのよね。未来予測とかグラフ作りをそれなりにやらないと、たぶん不幸な未来を避けるのは難しい。ていうかこれ普通に考えると運ゲーにならねー、でも賢い人はこの状況で Lambda-man 生かせるのかな…とか思う。
さて死ぬのは諦めた。しかし怯えてる ghost は得点が高いし、 fruit も得点が高いので、こいつらを優先的に喰うことにしよう、てなことをやる。このへんから一人イタチごっこがはじまる。
あ、私の ghost 、 Lambda-man に襲いかかりすぎるあまり、殺すのはいいんだけど得点渡しすぎてる…と思ったので、怯えモードの時は行くところの優先順位を逆転させてやる。逃げ AI 。
うーん ghost 食いにくくなったのかな、と power pill の隣に待機して、 ghost が近寄ってきたら power pill を食って ghost を食べる、ってのを実装する。いくらなんでも無限に待つとザコ AI 相手に power pill の隣でウロウロしてるだけで終わってしまうので、timeout なんかを実装してやりつつ。
あ、私の ghost 、待ちラムダーマンにやられて、標準 AI より得点渡してる…と気付いたので、 Lambda-man が power pill に近い時には怯えモードにしてやる。逃げる逃げる。
なんとなく Lambda-man の生存率が高くなってる。あたりまえだが怯えモードの時に画面の端までいってしまうので、 Lambda-man の power pill 隣待機作戦は、 ghost 喰うのには成功しないものの、その後しばらく安全に移動できるようになっちゃってるぽい。なるほどということで Lambda-man から遠い時は襲いかかるモードにする。
こういう感じの細かい調整をまぁいろいろ。 Lambda-man が一手で ghost を食える時は喰うとか、なるべくがんばって fruit は喰うであるとか、 ghost も最初の頃に入れたランダムな挙動が Lambda-man に近付いてる時とか逃げてる時に出す必要は無いなーとやめてみたりとか、そういうの。
感想
面白かった、と思う。評判があまり芳しくないぽいのはまぁわかる。問題に面白みは足りないと思う。まぁ L:tG とかと比べるのは酷。ただ、分量は多いので、こういうのは一人でやってると無理ゲー感はあるものの、楽しい。 ICFPC って、結構終わってから、誰かと組みたかったな…と思う年はあるのだけど、今回はそうではなかった。ま、そんなに成績は良くないだろうけど、あーなんか色々やったなー的な充実感があった。
あと今回結構、色んなところで(私が一人でやるという前提に立てば)正しい選択を結構できたのではないかな…という感はある。まぁ、このへんは毎年、あーがんばったなーと思いつつ、他の人の思いもよらない作戦に、あーこのくらいは思いつけるべきだった…って思ってるんだけど。まぁ、今回はそういう裏技が思いつきにくい、割と素直な問題だったと思うんだけど…
2D Lisp
beflisp.bef が 1次元 Lisp しかサポートしてないのはけしからん、と言われてその通りだなぁと思ったので、 lisp2d.c てのを書いて beflisp2d.bef を生成してみました。 bc2bef.cc は全くいじる必要がありませんでした。 Befunge コードが C 書くだけで作れるってのはラクチンですね…
で、こんなコードが動きます。2次元であることに面白い意味を持たせるアイデアが無かったので、単に 2D レイアウトできるようになっただけです。 Befunge 同様コードが交差できるのは少しオシャレ。気をつけないと括弧のつもりで使った v が文字列の一部になったりするので、書くのはかなり大変
(defun fizzbuzz ^ (fizzbuzz 1) @
^ zzuB ( 0 (5 n dom)
i ^
f v ^ q
( eq ^
^ fi) ^ v m
e o
q l f d
i i
n (mod n 15) 0) Fizzbuzz v n
1 q 3
0 e v
1 (if v
v 0
t v
n n
i i F
l r i
p ^ z
(if v ^ z
1
n
v
n v
v
+ v
v zzubzzif )
beflisp.bef と LLVM Befunge backend
https://github.com/shinh/beflisp
Lisp インタプリタを作りました。今度は Befunge で。
https://github.com/shinh/beflisp/blob/master/beflisp.bef
コードを見ればわかりますが、手書きは諦めました。 前回の sed と違って Befunge は数値演算は素直に提供してくれてるので、アドレス計算なんかをするプリミティブが提供しやすいです。ただ、 Befunge-93 は文字列とか関数コールという概念が無いので、手動でフロー管理するのは地獄でしょうね…
ということで、 C で lisp を書いて、それを clang で LLVM bitcode に変換してから、トランスレータで Befunge に変換、という構成になっています。
実装
トランスレータは任意の C コードを Befunge に変換できるようなレベルには全然達していません。例えば型は全部 32bit 決め打ちです。内部実装知ってないとどういう C コードなら通るかとかわかりにくいでしょうし、内部実装知ってる私にもあまりわかってません。ていうかなんで動いてるんだろうっていう感じ。全体的に投げ槍な実装なんで。
LLVM bitcode からトランスレートされた Befunge コードってのは、あたりまえですが割とデバッグが大変です。しょうがないので小さな C プログラムを一つずつ動くようにしていく感じでやりました。あとデバッグしやすいように元に bitcode を実行しない領域に置いてあります。
大変だったのはまずブランチとかですかね。立体的にコード配置するのはデタラメに大変に決まってるので直線的に実行したいので。スタックトップが真ならスタックの2番目を採用、偽なら3番目を採用、ってことができるプリミティブを作ってそれをあちこちで使う感じにしました。ブランチといえば当然 PHI もダルいったらありゃしない。
LLVM のバックエンドの書く作法を調べるのが面倒だし、 LLVM のバックエンド用の共通基盤が Befunge みたいな素頓狂な実行モデルにうまいこと適合するとは思いがたかったので、 bitcode 読んでからは全自力です。レジスタアロケーションだけやってもらえたりするとラクに生成されたコードを小さくできるんですが…
機能としては前回の sed と同じはずです。前回のテストコードは全部パスしてますし、 FizzBuzz on Lisp on Lisp on Befunge も動いています。すごく遅くて、半分で 1 時間とかかかってますけど。
TODO
レジスタアロケーションをやるってのと、ブランチの高速化、ってのがあります。このふたつやればもう少し実用的な速度になるんでないかなぁと。
というのは、前者は、現状 SSA の結果は全部スタックに残していっていて、スタックがまあまあ遠いところにあるんでアクセスにかかる命令数が多いということがあり。
後者はもっとひどい話で、現状どこかで jmp や call があると、必ずプログラムの一番先頭まで戻ってから次に実行する場所を線型探索してます。そうでなくてちゃんと差分だけ動くようにすれば、近くへの jmp とかが劇的に速くなるかと思います。
あとは free が実装されてないってのがひどいんですけど、当然のことながら実装するとすごく遅くなっちゃうと思われるので、だるいかなあと。
まとめ
Befunge はまともな言語
sedlisp.sed
https://github.com/shinh/sedlisp
https://github.com/shinh/sedlisp/blob/master/sedlisp.sed
README に書いた通り、それなりにややこしいプログラムも動く気がします。具体的には eval.l として、 eval の無いところで eval を実装しました。で、その上で FizzBuzz なんかが動きます。これはつまり S 式のパースは省略した Lisp のインタプリタと言って良いので、 sed で書かれた Lisp の上で Lisp が動いて、その上で FizzBuzz が動いてることになります。ちなみにもう一段かますことはできませんでした。 Ruby で書いた実装でも動かないので、 eval.l がとりあえず循環できない作りになってしまってるみたいですが、デバッグできないので何が間違ってるのかよくわかってません… (追記: id:Irori さんがなおしてくれました! FizzBuzz on Lisp on Lisp on Lisp on sed が動く!)
正直疲れたんで s/// 以外の sed script 書くのやめようかと思いますね…なんか途中から ruby で等価なプログラムを書いてテストしはじめたのですが、 ruby の実装は 1 時間もかかってないのに対して、 sed の方は 40 時間くらいはかかってるんでないかなーと思います。
あとは実装について
加減乗除
加算減算は何度か書いたのでやるだけ作業です。動作の説明は
http://shinh.skr.jp/slide/mederu/048.html
などにあります。
乗除はめんどくさいので Lisp で組み込み関数として書きました。 neg? という関数だけ sed で実装して、割り算の実装に使っています。
次に実行する場所
関数しか無ければ、中から実行すればいいので、最左にある、その中に括弧の無い括弧の組を実行すれば良いです。正規表現で書くと ([^()]*)
大変なのは special form というやつです。 if とか defun とかは、中を先に実行しちゃまずくて、外から実行していく感じになります。これは最左の括弧の組を一旦 @ に変換しておいて、 @ より左に special form があれば、そっちを先に実行、という方式でやりました。
(+ 2 (if t (+ 3 4) 5))
みたいな式があると、 (if t (+ 3 4) 5) だけを取り出す必要があるわけですが、これも正規表現ってやつはご存知の通りネストした括弧の組を取り出すとかできないので、かなりめんどくさいです。
具体的には (if の中の括弧の組を @ で取り出していって、 (if の中に括弧が無くなれば @ を復元、というようにやりました。
この方式では defmacro の実装はありえないくらいめんどくさいことになります。当然実装してません。
スタック
次に実行する場所を切り出せたら、切り出した以外の場所をスタックに保存しておかなければなりません。これは以前にもやったことがあって、切り出した部分を @ に置換しておいて、その @ を含んだ式をスタックに置いておきました。
さっきの if 文なら
(+ 2 @)
のようなものがスタックに積まれて、 (if ...) の評価が終わると結果を @ と置換して実行を続けます。
sed にはスタックなどという便利なものは無いんで、ホールドスペースの末尾に一行ずつ書いていくことにしました。
define と defun
define で変数を定義すると、ホールドスペースの先頭の変数を置く空間に書きます。
(define foo 42)
は
;foo;42;
などと定義されます。
変数の展開は、変数一覧をパターンスペースに持ってきてから、正規表現の後方参照でやります。
s/^\([^\n]*[ ()]\)\?\(\S\+\)\([ ()\n].*\n;\2;\([^;]*\)\)/\1\4\3/
というような感じで…と言ってもなんのこっちゃわからんかもしれませんが、
$ echo '(func foo)@;foo;42;' | sed 's/^\([^@]*[ ()]\)\?\(\S\+\)\([ ()@].*@;\2;\([^;]*\)\)/\1\4\3/'
などとすると foo が 42 に置換されるので、そういうもんです。 (\n は @ に置換しておきました)
defun は単に define と lambda のシンタクスシュガーです。
quote と lambda
このコードの全域で値の区切りとして空白を使っているので、 quote や lambda にある空白は厄介、というかそのままでは全く取り扱えないです。あと括弧も残ってると絶望的です。
しょうがないので、内部的に括弧と空白を別な文字に置換して取り扱ってます。 (quote (4 5)) は [4,5] に、 {lambda_{n_m}_{+_n_m}}$ に置換してあります。 lambda の末尾についている $ は、 lambda を関数適用する時に lambda が引数として渡されたりすると大変なことになるので、ターミネータが必要だと気付いて足したものです。
lambda の適用は、特に引数の処理はだいたい変数の展開と同じです。
print 関数はこのへんをそのまま出力するので、
(print (lambda (n m) (+ n m)))
などとすると内部表現が見られます。
まとめ
他にもいろいろハックでごまかしてる部分などがあって、大変でした。 evalify した sort とかよくうごいてるなーという感じ。
