非同期処理の「その後」の話。goto、継続、限定継続、CPS、そしてコールバック地獄。 2015-04-25 非同期 CPS 継続 限定継続 # 非同期処理の「その後」の話 ---------------------- ## goto、継続、限定継続、CPS、そしてコールバック地獄 <!-- .slide: class="center" --> === # About Me ---------  <!-- .element: style="position:absolute;right:0;z-index:-1" --> + κeen + [@blackenedgold](https://twitter.com/blackenedgold) + Github: [KeenS](https://github.com/KeenS) + 渋谷のエンジニア + Lisp, ML, Shell Scriptあたりを書きます === # 同期処理とは ------------- 通常、外部とやりとり(I/O)する時に待ち時間(ブロック)が発生する。  === # 非同期処理とは --------------- 待ち時間に(ブロックせずに)別の処理をしようという発想。  === # 非同期処理の裏側 ----------------- 処理Aと処理Bの他にいつどっちを動かすかを決めるスケジューラが存在することが多い  === # どうやって戻る問題 ------------------- * 一時停止した後「その後」の処理にどうやって戻るか  === # 「その後」とは ----------- ```C ... fputc(c); // ここの処理でI/Oが入る // 再開する時にここに戻ってきたい printf("Work done"); ... ``` === # GOTO ------ `goto` を使えば戻れる ```C ... fputc(c); // ここの処理でI/Oが入る // 再開する時にここに戻ってきたい RESTART: printf("Work done"); ... ``` === # GOTOの問題 ------------ こういうコードだとGOTOでは困る ```C if ((c = fgetc(f)) != -1) ... ``` === # GOTOの問題 ------------ こんな区切り方をしたい  === # GOTOの問題 ------------ * 式の途中に入れない * 値を返せない * I/Oが終わった「その後」が思ったより複雑 === # "継続"という概念 ----------------- * continuation * ここで言ってる「その後」に名前をつけたもの * その後に行なわれる全ての処理のこと * 全ての言語に存在する === # (限定)継続を値として扱える言語 ------------------------------ 値としての継続はちょっとリッチになったGOTO程度。 * Scheme * OchaCaml * SML/NJ * (Ruby) * etc. === ## 正確には限定継続 ------------------ * 細かい話だが継続と言うと処理Aとスケジューラ全てを含んでしまうので 今回欲しいのは処理Aの中に限定した限定継続 * 継続を値として扱えれば限定継続を[実装出来る]()ので今回はそこまで深く違いを気にする必要はない === ## 正確には限定継続 ------------------  === ## 正確には限定継続 ------------------  === # 限定継続を使った非同期処理の例 ------------------------------ Cの例をSchemeに翻訳してみる ```scheme (if (/= (read-char f) -1) ...) ``` === # 限定継続を使った非同期処理の例 ------------------------------ `lambda`は限定継続を`k`として受け取り、関数として使える。(今回はコールバックとして使っている) `reset`、`shift`、`lambda`、`k`を無視すれば以前のコードと一致する。 ```scheme (reset (if (/= (shift (lambda (k) (async-read-char f k))) -1) ...)) ``` === # 限定継続を使った非同期処理の例 ------------------------------ `lambda`は限定継続を`k`として受け取り、関数として使える。(今回はコールバックとして使っている) `reset`、`shift`、`lambda`、`k`を無視すれば以前のコードと一致する。 ```scheme (if (/= (async-read-char f ) -1) ...) ``` === # 限定継続を使った非同期処理の例 ------------------------------ `lambda`は限定継続を`k`として受け取り、関数として使える。(今回はコールバックとして使っている) `reset`、`shift`、`lambda`、`k`を無視すれば以前のコードと一致する。 ```scheme (if (/= (read-char f) -1) ...) ``` === # ここまでのまとめ ----------------- * 非同期処理を行なう時に継続という概念が出てくる * 継続を値として扱える言語もある * 値としての継続は1引数関数として振る舞う * そのような言語ではユーザレベルで非同期処理をサポート出来る === # 継続を値として扱えない言語での非同期処理 ---------------------------------------- * 先に言ったように全ての言語に継続が存在する * マシン語レベルでjump命令とほぼ同じ * 言語処理系レベルで継続を取り出せば使える * 要は組込み機能 === # 継続を値として扱えない言語での非同期処理 ---------------------------------------- * 処理系にそこまで求めるのは酷 * バグり易い * デバッグし辛い * 処理系はもっと別のことに専念すべき * 機能が追加修正される度に処理系をアップグレードしないといけない 実は継続を値として扱えない言語でもユーザレベルで継続を値として取り出す方法がある === ## Continuation Passing Style <!-- .slide: class="center" --> === # CPS ----- * 日本語にすると「継続渡し形式」 * 継続を関数として切り出して引数に渡す * 継続のために全ての関数の引数が1つ増える * 継続渡し形式に変換することを「CPS変換という」 * CPS変換は機械的に出来る === # CPS変換 ------------ 先は ```scheme (if (/= (read-char f) -1) ...) ``` が ```scheme (reset (if (/= (shift (lambda (k) (async-read-char f k))) -1) ...)) ``` になった。 === # CPS変換 ------------ 今回は ```scheme (if (/= (read-char f) -1) ...) ``` が ```scheme (async-read-char f (lambda (c) (if (/= c -1) ...))) ``` になる === # CPS変換 --------- * パっと見限定継続のコードの`lambda`の外側と内側が入れ替わる * そんなり分かりやすくない === # もっとCPS変換 --------------- 階乗関数の例 ```scheme (define fact (n) (if (<= n 1) 1 (* n (fact (- n 1))))) ``` === # もっとCPS変換 --------------- 階乗関数の例 ```scheme (define fact (n c) (if (<= n 1) (c 1) (fact (- n 1) (lambda (c) (* n c))))) ``` === # CPS変換まとめ -------------- * とりあえず機械的に変換できる + 実際、CPS変換をサポートする言語はいくつかある - Haskellのdo記法とか * むしろ機械がやるべきで人間がやることではない === # コールバック地獄の正体 <!-- .slide: class="center" --> === # コールバック地獄の正体 ----------------------- 先のCPS変換のコードをJSで書くと分かるかも ```javascript async_read_char(f, function(c){ if(c === -1) { ... } }) ``` === # コールバック地獄の正体 ----------------------- 先のCPS変換のコードをJSで書くと分かるかも ```javascript function fact(n, callback) { if(n <= 1) return callback(n); else return fact(n - 1, function(c){return n * c;}) } ``` === # コールバック地獄の正体 ----------------------- * 人間が手でやることではない"CPS変換"を手でやらせた結果 * altJSは内部でCPS変換を行なうことで非同期プロミスなどを実現している + DeNAのJSXとか === # 非同期処理の実装まとめ ------------------------ 下に行く程抽象度/汎用性が高い * コールバックスタイル + JavaScript(< ES6)とか * 言語レベル組み込みサポート + C#とか * 言語レベルCPS変換サポート + altJSとか * 言語レベル(限定)継続サポート + Schemeとか * ユーザーレベルでも限定継続(CPS変換)を実現出来るエレガントなマクロサポート * Lisp ※ネタです。マサカリ投げないで下さい。 === # まとめ: なぜコールバック"地獄"なのか ------------------------------------ * そもそも難しいことをやろうとしている * 難しいことをカバーするだけの言語の機能が足りてない