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