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年ちょいたって、さすがに右も左もわからんということもない感じではあるけど、まだまだにわかほど語りたがる感じの状態です。

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のローダと違って名前空間がフラットじゃないとか

まとめ

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

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度回転した部分に */ が現れてしまってコメントが終わってしまうという。

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 が実装されると計算も並列に走るようになっていい気がしますね

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 みたいなの作りたいなぁとかいうことを割とずっと思っています。

ELVM Compiler Infrastructure について

はじめに

言語実装 Advent Calendar 2016 用です。

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

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

• Perl: http://qiita.com/mackee_w/items/5397d6b9215f41c41db1
• Tex: http://hak7a3.hatenablog.com/entry/2016/11/13/153418
• Tex: http://hak7a3.hatenablog.com/entry/2016/12/03/124632
• Vim: http://rhysd.hatenablog.com/entry/2016/12/02/030511
• C++ (constexpr): http://kw-udon.hatenablog.com/entry/2016/12/03/201722
• Unlambda: http://irori.hatenablog.com/entry/elvm-unlambda-part1

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

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

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

ELVM Compiler Infrastructure

最近作ってたオモチャがだいたいまとまってきました。

https://github.com/shinh/elvm

第12回 kernel/vm 勉強会で発表した時のスライド:

http://shinh.skr.jp/slide/elvm/000.html

これは何かというと、前作った bflisp を改良したり整理したりしたもので、 C 言語をシンプルな中間言語 (EIR) に変換する改造 8cc と、その中間言語を Brainfuck をはじめとした他言語に変換するバックエンドから成り立っています。 bflisp との差分は、 Brainfuck 以外のバックエンドを追加しやすくしたり、バックエンドを C で書いて、完全に Brainfuck だけで 8cc.bf を再現することができるようにしたり、という感じです。

特に興味深いであろうバックエンドとしては、 Brainfuck, Unlambda (id:irori さん作), Piet, C-INTERCAL, Befunge, Whitespace などがあります。例えば Lisp を Piet で動かしたりもできるようになりました。 lisp.png を gimp で開いてスクリーンショットを撮ったこの画像なんかは結構お気にいりです。

JavaScript に変換することもできるので、デモサイトは ELVM を使って作った JS で作られています。

http://shinh.skr.jp/elvm/8cc.js.html

スライドにも書きましたが、「チューリング完全な言語互いに等価だからうんぬん…」というような、理論ではそうなんだけど…というようなことが実際確認されるのを見るのはなかなか楽しかったです。コンパイラいじり、 esolangs での計算プリミティブ作成パズル、最小限の libc 作り、など好きなトピックがたくさんあるという意味でも楽しくて良かったです。