むっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。

やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。

今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測したものなので、互いに相関があり、相関を利用しない普通の画像圧縮だけでは上位の成績にはなかなか追いつかないと思っています(後述しますが汎用画像圧縮で7位は取れていたと思います)。

次のピクセルを予測する

圧縮についてある程度の知識があれば、色んな情報から次のピクセルの値を予測して、当然予測は外れるので外れた分についてエントロピー符号、という方法を考えるかと思います。エントロピー符号はデータに偏りがあればあるほど圧縮率が上がるため、問題のドメインについての知識を利用して、データを偏らせることができれば圧縮率が高くなります。例えば、普通の画像は一般的に直前のピクセルと近い値を持っていると考えられるので、直前のピクセルと次のピクセルの差分を保存すれば値が0に近い値に偏るので良いのです。すぐ左のピクセルだけでなく、左と真上のピクセルの平均値であるとか、付近のピクセルを適当なわりあいで混ぜた数値であるとか、予測の精度を上げる方法は色々と考えられます。

今回の問題の場合、同じ波長を別の時間に観測した画像や、同じ時間に違う波長を観測した画像からもパラメータを拾ってくることができて、さらにこの予測の精度を上げることができます。これは、パラメータが複数あって一つの値を推定するので、普通にある種の機械学習と言えます。

私が使った方法は、参照画像からピクセルの値を推定して、その推定した値がさらにどれだけ現実とずれているかということを近傍のピクセルから推定する、という方法と、参照画像と近傍の両方からピクセルを推定する、という両方のアプローチを、かつ色んな参照画像に対してやってみて良かったやつ、という方法です。機械学習で忌み嫌われていると思っている ensemble 的な話です。本当は一気に推定する方法だけで行きたかったのですが、一気推定は当初の時間制限だと割とギリギリだったのと、参照画像との相関が低い画像で成績が悪い(特に全体の半分以上を占める一番大きい画像4枚で良くない)ので、最後まで残ってメンテナンスを困難にしていました。

実際のモデルは、単にパラメータ(つまり近傍や参照画像のピクセル値)を重みつけて線形和したもので、重みの推定は単なる最小二乗法でやりました。パラメータの二次以上の項を入れるのはほぼ逆効果で、まあそれは冷静に考えるとピクセルの値を2つかけ算した値に意味があるとは思えないわけですが、もう少し複雑なパラメータを入れることはありえたかと思います(例えば med(x,y) のような)。

最小二乗法は微分可能なおかげで解析解があって、お手軽高速に計算できるというのは大変良いのですが、後段のエントロピー符号的には無視しても良いはずの外れ値に優しい、という特性を持っているので大変よろしくないという認識でした。なるべく多くのピクセルをゼロ付近の極めて近いレンジの値に押し込むことによって圧縮したい、というモチベーションなので、稀に予測が大幅に外れる値がどういう値を持っているか、はたいして興味がないのです。実際ぐぐってみると、ロバストな最小二乗法というのが色々あって、やってみると良かったりもするのですが……実装が面倒だったり遅かったり、そもそもここがよくなることで得られるメリットが少なかったりとあって、放棄しました。要研究。

さてこの線形和のパラメータは画像の位置によって多少違うはず、ということで適当に大きめのブロックに分割したりしています。また、余分にパラメータを保存することを考えると、ほんの少しの差ですが、参照画像のピクセルの値によって使うパラメータを切り替えたりもしています。

予測から外れたぶんをエントロピー符号にかける

で、予測からのずれの量をエントロピー符号にかけることになります。エントロピー符号というやつは、ハフマン符号が一番有名で、例えば0012というデータを圧縮するなら、0は1と2よりよく出てくるので"0"という1ビットで表現して、1と2は"10"と"11"を使って表現しよう、というものです。ハフマン符号では各文字を整数ビットでしか符号化できませんが、算術符号やその一種のレンジコーダでは概念的に小数ビットを割り振ることができる……ような感じです。出てくる文字の確率分布で割り当てるビット数を決めるわけですが、その確率分布を動的に変えるものがadaptiveなやつで、ヘッダなどに確率分布を埋める必要がない、データの特徴の変化に対応できる、などの良いところがあります。ですが、何故か私は最終日前までadaptiveなやつを使うことを考えてなかったのでadaptiveじゃないやつを使ってます。まあadaptiveなやつはそれはそれで不利なところもあると思います、たぶん。

これ以上偏りが顕在化できない状態になったデータは、ハフマン符号でだいたい理論限界寸前まで圧縮できます。レンジコーダだとさらに進んで、まあもう理論限界だろってとこまで行きます。でこの理論限界てのがシャノンの限界というやつですね。となるとやること無さそうな気がするのですが、やれることがあります。前段で適当に予測したくらいではまだまだ偏りが顕在化しきっていないのです。

残ったデータは、まあおおむねゼロに近いところに頑張って叩き込まれてはいるのですが、部分部分で見ると、うまい具合にゼロ近辺に集まっていてくれているところと、予測器が苦戦して値がバラけまくっているところがあります。参照画像も現画像もほとんどデータが無くて動きが無いところとかは、ゼロ近辺の値に短いビット列を割り当てても良いし、逆に動きが激しいところはもう少しまんべんなくビット列を割り当てないといけません。

というわけで、画像をブロックに区切った上で近くの予想からのズレの量に応じて、使うレンジコーダを分けています。近辺の予想からのズレで使いわけるのは、近辺がズレてなければ次の値もあまりズレてないだろうという仮定があり、逆に近辺がズレているのなら次の値もゼロから遠い値の可能性が高いだろう、ということからです。これは私の理解ではLZMAが似たようなことをしているはずです。

区間で区切るのもまたこういう分類の効果を発揮してくれるというわけです。私の場合、単にゼロからのズレっぷりの平方根の和で得点をつけて、その得点が高いものほどバラけたデータに使う符号器、というようになっています。二乗和だとさっきも書いた通り外れ値に従ってしまうため、絶対値どころか平方根くらいが良いようでした。

圧縮 == 機械学習

で、なんかこういうことをやっていると、まるで機械学習なわけです。前段はいくつかの値から次のピクセルを予測する回帰をやっていて、後段は似た素性のデータには同じエントロピー符号器を選択するように、データをなんとなく分類するわけです。回帰と分類てモロに機械学習ですよね。

このコンテストの最初の頃は、「うーんこの最初二乗法で予測するとかなかなか面白いアイデアじゃないの？」とか思って、ぐぐってみると10年以上前のどうでも良さそうな論文が出てきます。まあ私が考えるようなことは普通に誰でも考えるよな、と思ってました。

そのうちに「これなんか本当に機械学習そのものじゃないの？そういえばオートエンコーダとか割と初歩的な深層学習よね」とか思いはじめてきました。で、そういうワードでぐぐってみると、色々と出てきます。そんなこんなしていて気付いたのが、FLIFというデータフォーマットで、これは実際圧縮が難しいデータに関しては私の圧縮といい勝負をするレベルの汎用圧縮でびっくりしました。それで特に感銘を受けたのが、FLIFの説明スライドでした。

http://flif.info/slides/FLIF_ICIP16/assets/player/KeynoteDHTMLPlayer.html#36

特にこの上記の KEY INSIGHT というページでは、モロに「Compression = Machine Learning」と言っていて、そうだよそう、その通りなんだよ、と思って感動しました。その次の "If you can (probabilistically) predict/classify,
then you can compress" も、まさにその通り、という感を受けました。しかし今にして思うと別に感動的でもなんでもなくて、当たり前だよなあという気がしてきてしまうんですけどね。最近の圧縮ではニューラル使うのもあるようですし。まあこの「なるほど！」→「当たり前じゃん」のプロセスを成長ということにしたいです。

機械学習といえば特徴量をプロが頑張って自力抽出、というのはオワコンで、なるべく特徴量も含めてメタな学習をするようなモデルを選ぶというのが主流という理解で、その現在での完成形の一つが深層学習という感じだと思います。FLIFでは深層学習では無いものの決定木を使って使うべき符号器を選んでるようです。

2週間ほどあれこれと人間の直感を駆使して特徴量を探しては圧縮率に一喜一憂する、という全くスケールしない(けど実は結構楽しい)作業に従事していた私としては、この知見には実になるほどなあというところで、最初からこの知識があれば、もっとadaptiveなアプローチを最初から指向していた(そしておそらく大失敗していた)ように思います。何故失敗するかというと、この手のマラソンでは最終的には一般的すぎる解より人間全力チューンが勝ちがちという経験則があるからです。ただ実際問題としてパラメータ増えすぎてコード整理や調整をしきれなかったという面があって、実際最後の方はパラメータ調整だけが実質的な伸びしろだったので、反省点とも言えます。

まとめ

楽しかった、勉強になった、しかし本当に悔しい

2017-09-10

Deep Learning Acceleration 勉強会

https://connpass.com/event/64632/

すごく面白かった。最近こういう会に行って感心することは多いのだけど、しかしなんか書きたいと思うレベルになかなか来ない、まあそれなりに年喰ったしな、とか思ってたんですが。低レイヤとか、自分がある程度既に知ってるところの話を聞くのも楽しいけど、自分が最近勉強してて理解しはじめたことの話を見聞きする方が楽しいよねえということかと思いました。まさににわかほど語りたがる現象で、実際懇親会とかで間違ってること結構言ってそうな気がする。

ジャンルとして、他のCSのジャンルとかと違って、深層学習はとにかく論理的に確定できない話が多くて、あの論文はあやしいなあ、あれは説得力あるなあ、というような、口コミベースの情報が回してる面が、良くも悪くもあるのかなあ、という印象を持っています。

つーわけで口コミレベルの適当なことを、以下、書きます。(定型句)間違ってることが普通にいっぱいあると思います。(定型句)所属企業とは関係なく勝手に書いてます。定型句と書いたけどグーグルとしての感想では本当にないです。ちなみに僕はRNNしかいじったことないです

モデルアーキテクチャ観点からの高速化

僕はこれとても興味があったドメインだったので、早速すごい俺得と思いながら聞いてました。 factorization, squeeze, pruning とかの話の一部は自分でも試したことがあったのですが、自分のやった範囲ではうまくいかなかったという感想です。僕なりの考えを箇条書きにすると

このジャンル、まずトレードオフを明確にするべき(こういうのはハードウェアとかの人の方が得意であると思う)
少なくとも、クォリティ、学習スループット、推論レイテンシ、の3値があることは考えるべきで、どれか1つを狙うアプローチを他と混同すべきでない
もちろん上記3つ以外にもいろいろ考えることがある。例えばパラメータサイズは学習推論両方のメモリ使用量に効く、とか
あとこの発表はメインのターゲットはCNNだったと思う。CNNは正直よく知らないので間違ってたらホントすいません
conv WxH を factorization で別のに落とす、てのは意味的に別モデルを作ってる感があって、他のFCやらRNNでやるfactorizationは同じモデルだと思う
RNNだとfactorizationは悪くなるという印象。パラメータの数も減るし学習も早くなるのだけど、少なくともRNNだとembeddingの後の次元はほぼ完全に自由に決められるので全体の次元を落とすことは簡単で、それで同じパラメータ数で比べると余計なことしない方が計算量的に有利だった
なんかこの手の論文見てると正直、単にデータに対してパラメータ数過剰な状況で学習したモデルをベースラインとして、それに対して工夫するとクォリティ落とさずにパラメータ数減らせましたよ、というのがあると思った印象があります。そういうもののいくつは特に工夫しなくても単にオリジナルのモデルの次元を落とすだけでもっと効率良くパラメータを減らせるものがある印象
ただCNNてそんなに簡単にパラメータの数調整できるのか知らないので(画像サイズとかに依存するのかなと思いつつも単に平均色出してりゃいいんじゃねえのという感もあり)知らんす
この手のやつでは distillation の汎用性が高いという印象
正解データも一緒に入れるという話があるのだなあと知りました。過学習しそうというイメージがある

Convolutionの数理とアルゴリズム

なんかこの人すごい人だなあとなんとなく思ってたけど、なんかその思いが強くなった。数学強い人無条件に尊敬しちゃうよね。。。大学で数学で絶望していった時の感じ

まあまあマジメに聞いてたつもりだけど、正直きちんとわかってなかった。FFTに関しては、まあその場ではわかってないのだけど、「これはFFTするとこうやってオーダーが落ちますー」なるほどー、というのを数回やってるので、「もうなんかかけ算が足し算に変わるんやろわかったわ」、くらいでゴマかせました。中国なんとかは聞いたことあるけどはてさて、という感じだった

ウェブブラウザ向け深層学習モデル高速実行フレームワーク「WebDNN」

これはもう本当にプロジェクトのモチベーションが完全に正しいと思ってます。トレーニングしたグラフとモデルをさっさとデモできる環境がある、てのは完全に正しいモチベーションだと思う。

しっかしこんなのいくつかあるDNNプラットフォームの最大公約数を探してどうこうするのたいへんだよなあ(つまりTFで書こうがChainerで書こうが同じグラフIRに落ちてるという理解)…と。ぼんやり僕が唯一知ってるTFまわりをながめてると、 tf.while_loop の対応が無さそうだなあ、と思って聞くと、無いのは TF の設計思想のせいであると。すいませんという感じであった…

そういえば、最適化の方について結構語られてたけど、後で雑談した時は、もっとフロントエンド側に力を入れるべきというようなことをおっしゃっていたように思って、それもまた正しいなぁとか思いました。多少は遅くてもいいから、あまりいじらずに動く方が嬉しい、というか。

Using Raspberry Pi GPU for DNN

このひとゴルフ以外の話もすんですねえ…と思いました。しかしスキの無い簡潔十分な発表。僕が遊んだことがあるものでは、CellのSPEに近そうだなあとか思いました。

しかしラズパイの重要性をわかってない僕にとっては、うーんゴルフがんばったんだろうなーくらいの感しかなくてすいません。まあこの業務たまにやるぶんには楽しそう

TensorFlow XLAの可能性

この発表が僕的には目玉でした…というかXLAてのは正直社内でもかなりよくわからんので、誰かざっくり解説書かないかなーと思ってたら発表者の方が別の資料で説明を書かれていたというのもあり。

とはいえさすがに一応知らない話はあまし無かったような気がする。TF時代に入れたけどXLAになると使えなくなったりするのがあったりするのが微妙ではありますね。

今まではTFグラフをStreamExecutorていうタスクランナーで動かしてた。visitorパターン的な感覚で巡回してOp::Compute関数を実行してまわる感じ。

XLAだとグラフの一部なりグラフ全体なりをvisitorパターン的に巡回して、今度はOp::Compile関数を実行してコンパイルして、ノード群をコンパイルしたものに変えた上でStreamExecutorで実行する、て感じだと思う。

Googleが開発したニューラルネット専用LSI「Tensor Processing Unit」

一応つきあったことがあるというか現在進行形なので、言いにくいなあとかなんとか。とりあえず何喋っていいかはっきりしたのはありがたかった。

ChainerMN による分散深層学習

個人的な感覚だけで喋るなら、非同期学習オワコンは割と観測範囲の強そうな人たちが同期でいい感があると言ってる感があります。もっと言うならなるべくなら分散すらしたくないという雰囲気もあるような気がする。

後で話していたのですけど、分散すると弊社の場合、コンテナがある程度制御してるとはいえ、同じマシンで動いてる他のタスクの影響がどうしても出てしまって、同期+分散は遅いやつに性能がひっぱられがち、ということはあるとも思います。

TFが遅いとディスられてて、最初は使いかたが難しいせいかな？と思ったけど、まあそもそもTFのオープンソース版インターコネクトとマトモな感じじゃないよね、て話を思い出しました(たぶんgrpcを使っていて、この用途ではオーバーヘッドが許せる量が無いと思う)。

まとめ

まあとにかく勉強になった。なんか翻訳チームにうつってから1年ちょいたって、さすがに右も左もわからんということもない感じではあるけど、まだまだにわかほど語りたがる感じの状態です。

2017-05-29

10年ほど後のBinary Hacks

https://twitter.com/nalsh/status/869086098177146881

を見て、今ならどういうネタが書かれるかなぁとざっくり考えてみます。

perf

@nlashさんに指摘されていた通り、perfは重要だと思うんですが、書かれていたperf_event_openはptraceなんか目じゃないくらい使いこなしがムズいと思うので、素直にperfそのまま使えって感が強い気がします

ptrace

PTRACE_SYSCALL以外はあまり変わってないと思うんですが、PTRACE_SYSCALLはPTRACE_O_TRACESECCOMPでやるとずいぶん速くなるのでオトク

asan/tsan

valgrindのbinary translationでのinstrumentationてのはカッコいいけど、普通に考えるとコンパイラに手を入れる方が常識的ですよね……という

ELF

特に変わりが無い気がする

DWARF

よく知らないけど割と変わってて、-gsplit-dwarfとか-gzあたりは知っててもいい気がします

セキュリティまわり

mitigationは気休めなんで、ちゃんと2レイヤ以上セキュリティ機能使いましょう的な

angrとかqiraとか

CTF/セキュリティ系の人が作ったツールは色々面白そうだけどあまり知らない

glibcのrandomization

そういえば気がついたらプロセス内の関数ポインタ全部ランダマイズされるようになってたけど、たぶんここ10年な気がします

inotify

便利だと思う。特にinotifywaitコマンドが……fanotifyが何が違うかは忘れました

madvise

元々書いてなかった気がするとふと思い出しました

コンテナ

コンテナベースの仮想化とかは色々ありすぎて。cloneのオプションとかすごく増えた気がするけど、今見るとそうでもないか

x86の命令

_mm_cmpXstrYは使いどころ多いし使いやすいし良いものだという気がします。あとまぁAVXとかTSXとか？

ARMの命令

スマホの台頭を考えるとARMについてもなんか。thumbとか。

Android/iOS

スマホという意味ではこのへんで違うところとかも。これらだとglibcのローダと違って名前空間がフラットじゃないとか

まとめ

なんか結構あるなということと、最近知識がアップデートされてないから知らないだけで面白いことが起きていることがまだまだありそうだなぁということを思いました

2017-04-30

Very symmetric JavaScript code

だいぶ前に左右反転させてもだいたい同じに見えるコードを書いたのですが、もうちょっと進化させて、上下反転と、180度回転してもだいたい同じように見えるコードを書いてみました。

デモサイト: http://shinh.skr.jp/obf/very_symmetric_js.html

コード: https://github.com/shinh/hack/blob/master/very_symmetric_js/very_symmetric.js

普通のJS記号ゴルフと比べるとクォートが無いのが多少めんどくさく、あとは左右は一行コメントがあるから簡単なんですが、上下反転と180度回転のコードをコメントですっとばすのがパズルという感じでした。何も考えずに実行するコードの最後に /* と入れただけだと、180度回転した部分に */ が現れてしまってコメントが終わってしまうという。

2017-02-19

drdr

オレオレワークフローエンジン作りたくなる病というのがあって、例えば make 系なんかだと Wikipediaに色々書いてあったりします。ワークフローエンジンと総称するのが正しいのか知りませんが、依存グラフを順ぐりに並列に実行していくようなもの、色々あるわけですけど、目的も粒度もバラバラですが以下のようなものは割と似たようなものに見えてます。

thread pool
Tensorflow
make
Digdag

閑話休題。なんか微妙に10秒程度待ち時間があるような処理があって(クラウドストレージに対する例えば ls とか)、その ls の結果全てに対してまた10秒程度時間がかかるコマンドをまとめて実行、終わったら結果を集計、みたいなことをしたりすることが最近多いです。1週間から1ヶ月ほど10回とか100回使うんだけど、でもそのうち捨てる系のコード。私の場合、よくやる解決と問題点は

shell script で並列化したいところはバックグラウンド実行+waitで散らして、最後の部分は ruby かなんかで書く: shell script と ruby の2つを管理するのがうっとうしい。多少ややこしいパイプラインを作るの大変
ruby かなんかでスレッドプール作ってやる: 分散部分のコードがめんどくさい。多少ややこしいパイプラインを作るのがかなりめんどくさい
make を使う: 動作は理想的なことが多いけど、コードがめんどくさくて、あと宣言的な記述になって、シーケンシャルな記述じゃなくなるので、読みにくく編集しにくい

欲しいことを考えると

CPU並列は無くても良い
パフォーマンスは最適でなくて良い
コマンドが手軽に実行できると良い
コマンドが失敗したら即座に止まると良い
shell はミスりやすいから嫌だ
処理の後半部分のやりなおしとかのためにチェックポイントを仕込めると良い

で、まあなんか作りはじめてみましたというのがこれ。

https://github.com/shinh/drdr/

あまり良い例が思いつかなかったのですが、自分のスライドのディレクトリにあるスライド全部に対して、それぞれページ数を集計するサンプルがこんな感じ。

URL = "http://shinh.skr.jp/slide/"
drdr {
  # スライド一覧のところを読んできて、 list.ckpt に保存しておく
  # これ以降のスクリプトに書き損じがあっても、再度ネットワークアクセスは発生しない
  cmd("curl #{URL}", ckpt: 'list.ckpt') | task{|l|
    # ここから list.ckpt に依存した処理で、 Apache の directory index を適当にパース
    l.scan(/href="([a-z].*?)\/"/).map do |m|
      name = m[0]
      # スライドのページ数を適当に取ってくる。このコマンド実行は並列に走る
      cmd("curl #{URL}#{name}/ 2> /dev/null") | task{|l|
        last_page = 0
        l.scan(/(\d+)\.html/) do
          last_page = [$1.to_i, last_page].max
        end
        [name, last_page]
      }
    end
  } | task{|a|
    # 全部終わったら CSV として出力
    a.each do |name, max_page|
      puts [name, max_page] * ","
    end
  }
}

などなど。妄想したほど使い勝手良くなってない気がするのですが、しかし自分が使える程度のものにはなってるような気がします。しかし一般的にこういうのはどういう感じで処理してるもんなんでしょうか。なんかいい方法あったら教えてください。。

あと Guild が実装されると計算も並列に走るようになっていい気がしますね

2017-02-12

tanlog

最近、 tanlog というのを作って使っていて、割と便利なので紹介してみます。

https://github.com/shinh/test/blob/master/tanlog.rb

元々は同僚と、なんか端末に出たもの前もって lv とか tee に入れておくのって、忘れることあるし、 lv とか tee に流すと isatty が false になって色出ないのうざいよねえ…みたいな話をしてたように思います。 grep については fake_isatty とか作ったりしたんですが、この時 soda さんに仮想端末作ってやる方法があると教えてもらったのを思い出して、 script とかで記録しておいたら…とか話していました。

結果、その同僚は zenlog というのを作って便利になった、とか言ってたのですが、なんか Perl と bash 混じってるとか、コマンドの切れ目をプロンプトで教えるとか微妙…ということで自作したものです。 zenlog に対して tanlog なのはコマンド起動ごとになんかするからです。まあこういうのは人の作ったものを使うというよりはみんな勝手に作ればいい…

tanlog は screen/zsh と一緒に使うことが想定されていて、 preexec で tanlog start して precmd で tanlog end します。 tanlog start は screen のログファイルを指定して /tmp/tanlog/RAW の下に端末出力をダンプしはじめます。 tanlog end はその端末出力を綺麗にして /tmp/tanlog の下にコピーします。

このディレクトリの構造は適当に便利なようになっていて、

/tmp/tanlog/2017-02-12: ログの実体がある場所
/tmp/tanlog/TODAY: 今日のディレクトリへのシンボリックリンク
/tmp/tanlog/TODAY/P: さっき実行したコマンドのログへのシンボリックリンク
/tmp/tanlog/TODAY/PP: その前実行したコマンドのログへのシンボリックリンク
/tmp/tanlog/make: makeコマンドのログへのシンボリックリンクがこの下にころがっている
/tmp/tanlog/make/P: さっき実行した make のログへのシンボリックリンク

などと適当に便利そうなものが入っています。えーと llvm ビルドした時の cmake コマンドはどんな感じだったかな…とか思ったなら

wgrep llvm /tmp/tanlog/cmake/P*

なんてやってます。 wgrep てのは grep を w3m でラップした何かです。

あとは tanlog paths てすると最近実行したコマンドに含まれるパスとかURLぽいものがだーと出るので、それを w3m に喰わせる wl ていうのも使ったりしてます。コマンドが URL 出してくれたけど、それマウスとか screen とかでコピペするのめんどい、て時に使ってます。

https://github.com/shinh/test/blob/master/wl

そのまま他の人が使えるような形にはなってないと思いますが、 screen のログ機能なり script なり使って、とりあえずコマンドの実行結果を全部残しておく、てのはなかなか良いのではないかと思っています。 lv か tee 通すべきかな？とか一瞬逡巡するのが無くなります。実現がハッキーになりすぎるのが残念なところで、こういうことを色々便利にやってくれる screen つき shell みたいなの作りたいなぁとかいうことを割とずっと思っています。

2016-12-22

ELVM Compiler Infrastructure について

はじめに

言語実装 Advent Calendar 2016 用です。

ELVMは、コンパイラをフロントエンドと中間言語とバックエンドにわけて、多言語多CPUに対応しよう……というようなLLVMの考え方を、パロディと言っていいレベルにまで単純化したものです。結果として実用性は全くないが、C言語から他言語へのトランスレータを極めて簡単に書け、 Brainfuck などのような難しい言語のコードもC言語を書くだけで生成できる、というようなことを主目的としています。

本当は ELVM のバックエンドを一つ足して、 Brainfuck とかのような難しいターゲットでなければ、こういう感じで手軽に足せますよーということを書こうかと思っていました。しかし、ありがたいことにそういう趣旨だったり、あるいはもっと難しいターゲットについても、既にあれこれと書いていただいたのでした。例えば

など。上のリストは、おおざっぱに、上の方に簡単な雰囲気をつかむのに向いてそうな記事、下の方に謎テクニックを楽しむのに向いてそうな記事を並べてみました。いずれにせよ、こういう記事は中身をよく把握してる私自身より、試行錯誤していただいた他の人達が書いた方がわかりやすいでしょう……ということでなんか違うことを書いてみます。

具体的にはどういうふうに作業を進めたりした…てことを雑に書いていこうかと。技術的な概要は一つ前のこのポストとそこからリンクされてるスライドに書いたので、そっちを参照してください。

http://shinh.hatenablog.com/entry/2016/10/18/095437

sedlisp, beflisp, makelisp, bflisp

色々あって、Esolangですごく簡単なLisp処理系を書く、というのがマイブームになったことがありました。 GNU sed と GNU make は完全手書きでした。sedlisp を書いた時から、 @rui314 さんは「手書きじゃなくて中間層を介して変換した方が良いのではないか」と言っていたのですが、 sed や make だと、計算モデルが違いすぎるので直接書く方がラクかなということと、結果できたものが遅くなりすぎそうだったので、直接書きました。

ですが、 Befunge の時はなにか中間に入れないとキツいと感じたので、 LLVM bitcode から雑に変換する、という方法でやりました。といっても、 LLVM bitcode は任意のものを許すわけではなく、変換器がサポートしてる命令しか吐かないように注意深く書かれた lisp.c を LLVM bitcode にして、そこから Befunge に変換する、というようなやり方でした。

で、 Brainfuck もやってみるかなぁと思った時に、これは自明に Befunge 以上に大変なわけで、まあなんかから変換するしか無いわけです。でも LLVM bitcode て以外に命令セットでかいということは Befunge の時に感じてたので、あまりつきあいたくなかった。じゃあなんかオレオレ中間コードを作るのが良いかな、と考えました。

bfs

で、 bfs という中間形式をデッチ上げました。これは今の ELVM の EIR と同じなんですけど、最初は Brainfuck だけが想定ターゲットだったので、 Brainfuck Assembly 的な理由でこういう名前になっていました。ややこしいんで今後 EIR で統一します。中間形式をでっち上げるのは、まあ適当に決めるだけなので簡単です。

で形式が決まるとCコンパイラをいじることになります。 main しか無いような簡単なコードを書いてみて、x86-64のコードを出力してる部分を順に EIR を吐くように変換して、うまくいったらreturn 42;とか1+2;とか、命令を足しては出てきたx86-64のコードを等価な EIR のコードに変換していく感じでした。

すごく短いプログラムをコンパイルできるようになったら、 EIR のシミュレータを書いたかと思います。命令数が少ないので、 Brainfuck のインタプリタを書く程度プラスアルファくらいの手間でできます。途中、ああ命令だけじゃなくてデータも書けないといけないな、ということで.dataセクションを足したりもしました。

この段階で重要だったのは、C言語で書いたコードをx86-64に変換して実行した結果と、EIRにコンパイルしてシミュレータで動かした結果が同じ、ということをきちんとテストすることでした。なにかまだサポートできてないCの機能を見つけるたびに、C言語でテストを書いて、makeと叩けばx86-64で実行した結果とシミュレータの結果が同じであることをチェックできるようにしてたと思います。

bflisp

C言語→EIRが一通りうまくいってるぽくなってくると、次は EIR を Brainfuck に変換する部分です。これはまあ……大変です。定数ロードとかをかけ算でやるとかは大変だし遅いBF処理系では全く通用しないので、8bitセルのBFで複数セルを使って1byte (当時は1byte==16bit) の情報を扱います。つまり単なる加減命令とかでも、繰上がり下がりの計算がはさまることになって……めんどくさいです。がまあ加減くらいは序の口で。

一番キツかったのは比較命令だったかと思います。上位セルが大きかったら下位は無視してーとか、0と比較する時だけおかしいとか、下位が0の時だけおかしいとか、そういう謎の現象が起きまくりました。load/storeも結構大変だったのですが、比較の後だったから慣れていたというのと、あまりコーナーケースが多くなかったこともあって、どっちかというとどういうレイアウトにするか、っていうデザインが大変だったような気がします。

こういうわけわからない有象無象をデバッグするために、EIRのシミュレータと、EIRからBrainfuckを出力した時のコードに、トレース出力をつけました。具体的には1命令ごとにレジスタの状態を出力する感じです。これでできた巨大なトレース出力を diff していると、喰い違いが出てくる部分がでてきて、そこを見ればバグの原因がわかるので、小さいテストを書いて修正する……というのを繰り返しました。これはオモチャ CPU 作った時にも使ったアプローチで、CPUの時はエミュレータに実行トレースをつけたものと、iverilogでトレースを出してたものを比較してました。でまぁ、なんかうまくいきました。

あとは、C言語→EIRの時に使ったテストケースを、順にEIR→Brainfuckの変換でも正しく動くかをテストしていった感じでした。そんなこんなで lisp.c が Brainfuck の上で動きました。

8cc.bf

さて、lispが動くならCコンパイラ自体もBrainfuckで動かしたいな、ということで色々試しはじめます。まずわかったのは16bitのメモリ空間では、命令もデータも足りない、ということでした。命令の方は、「実際のCPUじゃないんだから、1命令ごとにPCひとつ使う必要ないよね」ってことで、 basic block ごとに PC が変わることになりました。 VLIW と考えても良いかもしれないです。いや良くないでしょうけど。

データの方はちょこざいなこともできなくて足りないので、素直に24bitに拡張しました。命令も拡張しても良かったんでしょうけど、前述の basic block ごとに命令をまとめる作戦は、単純に実行速度の向上にも貢献するのでいずれにせよやって良かったと思います。

あとは少しバグをつぶしたらEIR→Brainfuck側はだいたいできました。足りない libc 関数の用意と、 8cc 側の EIR としてサポートできない記述の修正です。 libc は ARC やオモチャ CPU のために書いたコードや、 Bionic から必要なものをひっこ抜いてきたり自分で書いたりして準備しました。 8cc 側の困った記述というのは、 signed が無いので value >= 0 とかが常に true とか、あとはビットシフトと浮動小数の撤去でした。

そんな感じで 8cc が Brainfuck 上で動きました。5時間ほどかかってセルフホストができて、おおーと思いました。

ELVM

このへんでだいたい満足してたのですが、2点ほど思っていることがありました。

id:irori さんが Unlambda への変換を実現させて、 8cc.unl を作ってくれたのですが、こういう感じでもっとターゲットを増やすと面白いのではないか
EIR→Brainfuckの変換はRubyで行なっていたので、完全なセルフホストではなかった。これでは人類からBrainfuck インタプリタ以外が失われた時に対応できない

でまあ、一番大変な 8cc.bf というのはすでに動いてたので、だるいなーと思ってたのです。がまあある日、2つとも一気に解決しよう、で ELVM とかいう景気のいい名前をつけよう、とか思い立ちました。名前とか決まるとやる気出ますね。

でまあ、まずはEIR→ターゲットの部分をCにしつつ、ちゃんとフレームワークぽい感じにしました。実装量はあったけどまあやるだけ。

他の部分は適当ですが、ターゲットを増やすのは割とやりやすくなってるのではないかと思います。なんか適当に周りの言語のコピペしてると、だいたいおかしいところが少しずつ見えてきて、インクリメンタルに作業できるんじゃないかと。特に Makefile がよく書けてると自負してまして、バックエンド書く人は少し Makefile に追記したら make hoge だけで hoge バックエンドに対するテストがたくさん走る感じになってます。

バックエンドを増殖させる

基本部分ができるとバックエンドを増殖させていきました。色々足していると、基盤部分にあった方がいい共通部品なんかが見えていったりしました。

Esoteric 方面の言語だと、 Befunge 、 sed 、 Piet 、 C-INTERCAL あたりはなかなか大変なバックエンドでした。特に経験が無かった C-INTERCAL と、あと Piet はなんか色々大変でした。

Piet はこう、 Befunge みたいな感じでできるかな…と思ってたのですが、コード変換と2次元レイアウトを同時にやるのが大変で、一旦 PietInst とかいう構造体の列にして、それからレイアウトを決めて色を配置する、みたいなことをやりました。つまりもう1つ中間言語を介してるわけです。

INTERCAL はこう、方言多すぎ、仕様多すぎですね。色々やってたのですが、結局 C-INTERCAL がまともに動きそう、ということでこれになりました。 add とか sub とか無いんで、このへんはパズルチックにプリミティブを作ってく感じでした。

反応など

当初は「ヘンなことやってるなあ」くらいに思われる程度だと思っていたのですが、予想以上に反応をいただいて、PRでバックエンドを足していただいたりして嬉しい誤算でした。現状28バックエンド中13バックエンドはPRでいただいた、というのはなかなかなもんだなと。最初の方に Unlambda, Vim, TeX バックエンドを書いてくだださった iroriさん rhysd さん hak7a3 さんには特に感謝する感じです。紹介記事書いていただいたのも後に続く人を増やしていただけたんでないかなと。

その後の展開としては、 C++ constexpr バックエンドのバズりっぷりがなかなか愉快でした。 @llvmweekly や Bjarne Stroustrup がコメントしたりと。あと、チューリングマシンバックエンドを書いていただいた、ND-CSE-30151というアカウントは、どうもこれノッテルダム大学の講義用のアカウントらしく、この講義のテーマにチューリング完全などがあるため、少なくとも授業で紹介くらいはしてくれるのでないかと思います。ジョークプロジェクトが大学の授業で紹介されるというのは、なかなか胸熱です。

あと、 id:irori さんの EsoLang vi のような方向性も面白いですね。改造 8cc が処理できる C 言語で書かれたソフトであれば、 Unlambda やら Brainfuck に変換できちゃうわけです。

まとめ

スライドにも書いたのですが、理論上できるに決まってることでも、実際動かしてみるのは大変だったりして、でも動いたりすると嬉しいもんだなと。どうも私は発見とかがしたいんじゃなくて、そんなのやってどうすんのってこととか、理屈はわかるけどそれ本当に現実的な話としてできるの、てことをやるのが好みなのかなぁと、最近思います。セクシーボイスアンドロボというマンガの主人公が、「私がしたいのは世界にちょっとしたドリームを与えるような、そういうこと」とか言ってたんですが、なんかたぶん、そういうことが目指すところな気がします

言語処理系、文法とかそういう表の部分に注目しがちですけど、バックエンドやそれ以降も面白いですよ、と。たとえば世の中の言語作者はもっとデバッガとかに興味持ってあげて欲しいと思ったりします。

あとはこう、なんか世の中にあるもののパロディーというか似たようなものを適当にでっちあげるというのは、なんかとりあえずやる、ってテーマとしては良いなと思ったりしました。なんか趣味コード書くかっていって、まぁいきなりデカいオープンソースに飛び込むとかすごい有用なもの作る、っていって手が動く人はいいんですけど…

PRは随時募集という感じなので、冬休みの暇潰しなどに、ぜひバックエンドを足してみてください