今回はLunarMLに入れるつもりの継続周りの機能についてグダグダと書いていきます。
先月のLunarML進捗報告は
でした。
目次
動機付け
Standard MLの標準ライブラリーにはsleep関数や
structure OS : sig
structure Process : sig
val sleep : Time.time -> unit
...
end
...
end
ストリームから同期的に読み込む関数
structure TextIO : sig val inputLine : instream -> string option ... end
があります。LunarMLのNode.jsバックエンドでもこれらの関数を提供したいです。
しかし、Node.jsには同期的なsleep関数や、同期的なストリーム読み取り関数はありません（後者は、正確に言えば生のfile descriptorを触るAPIかファイル全体を読み取る関数しかありません）。Node.jsではこういう場合、コールバックを使うようにプログラムを書き換えるか、async/awaitを使うことになります。
LunarMLではソース言語をいじるわけにはいかないので、コンパイル時の変換によってどうにかしたいです。
元の（SMLで書かれた）プログラムがこんな感じだとすると、
...sleepに至るまでのプログラム... OS.Process.sleep delay; ...sleepの後に実行するべきプログラム...
コンパイル後のJavaScriptコードは次のようになっていて欲しいです：
...sleepに至るまでのプログラム...
setTimeout(function() {
...sleepの後に実行するべきプログラム...
}, delay);
つまり、sleep関数は「自身の後に実行されるべきプログラムの残り全体」を取得してそれをコールバックに設定したいわけです。このような「ある計算の後に実行されるべき残りの部分」を継続 (continuation) と呼びます。特に、継続を値として取り扱い、（関数のように）好きなタイミングで呼び出せたりするものを第一級継続 (first-class continuation) と呼びます。
第一級継続を持っている言語としてはSchemeがあります。Standard MLの処理系であるSML/NJやMLtonも拡張機能として第一級継続を持っています。継続を取得するオペレーターはcall-with-current-continuation、略してcall/ccと呼ばれます。
中間言語
コンパイル先がネイティブコードや独自VMであれば、実装依存な方法でスタックをコピーして第一級継続を実装できたりするようですが、JavaScriptではそれはできません。
ターゲットによらず第一級継続を使えるようにする汎用的な方法として、CPS変換（継続渡しスタイル (continuation-passing style) への変換）があります。
CPSはコンパイラーの内部表現（中間言語）としてもよく使われるようで、SML/NJの人が書いた
- Appel, A. (1991). Compiling with Continuations. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511609619
という本が有名です。call/ccの実装方法にも触れています。
CPSはコンパイラーの中間表現として有用で、SSAやANFとよく比較されます。
しかし、コンパイラーの中間言語としてCPSは大変すぎる（？）のか、その後も「CPSじゃない（direct-styleな）中間言語の提案」とか「やっぱりCPSがいいんだ」みたいな論文が色々出てます：
- Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The essence of compiling with continuations. In Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation (PLDI ’93). Association for Computing Machinery, New York, NY, USA, 237–247. https://doi.org/10.1145/155090.155113
- Andrew Kennedy. 2007. Compiling with Continuations, Continued. ACM Press https://www.microsoft.com/en-us/research/publication/compiling-with-continuations-continued/
- Luke Maurer, Zena Ariola, Paul Downen, Simon Peyton Jones. 2017. Compiling without continuations. ACM Conference on Programming Languages Design and Implementation (PLDI’17) https://www.microsoft.com/en-us/research/publication/compiling-without-continuations/
- Youyou Cong, Leo Osvald, Grégory M. Essertel, and Tiark Rompf. 2019. Compiling with continuations, or without? whatever. Proc. ACM Program. Lang. 3, ICFP, Article 79 (August 2019), 28 pages. https://doi.org/10.1145/3341643
The Essence of Compiling with ContinuationはCPSしなくてもANF (Administrative Normal Form)でCPSと同等の恩恵を受けられるよね、的な話です。
Compiling with Continuations, Continued（SML.NETの人が著者）は、call/ccが要らない人でもCPSは有用だよ！みたいな話です。SML.NETは一旦CPSにして最適化した後direct-styleに戻しているそうです。そのため、継続はsecond-classとなっています。
Compiling without Continuationsは、direct style側の論文で、join pointを構文的に扱うようにしているようです。Haskell (GHC)に適用することを念頭に置いているようで、CPSが評価順を強制することを懸念しているようです。
Compiling with Continuations, or without? Whatever.は限定継続っぽいオペレーターを導入して部分的にCPSするみたいです。
call/ccが欲しいかどうかに関わらず、second-class continuationやjoin pointなどの概念は
- パターンマッチの脱糖でコードの複製を避けつつ、クロージャーじゃなくてgotoに変換する
- 末尾再帰をループに変換する
のに有用そうに思えます。
Selective CPS Transformation
スタックをいじれない環境で第一級継続が必要であればCPS変換しなければなりませんが、プログラムの全てで第一級継続が必要なわけではありません。プログラムの必要な部分だけをCPS変換 (selective CPS transformation) するという手が考えられます。
そういう方向性の研究もいくつかあります：
- Lasse R. Nielsen, A Selective CPS Transformation. Electronic Notes in Theoretical Computer Science, Volume 45, 2001, Pages 311-331, ISSN 1571-0661, https://doi.org/10.1016/S1571-0661(04)80969-1.
- Tiark Rompf, Igno Maier, Martin Odersky. 2009. Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-Transform
- Kenichi Asai and Chihiro Uehara. 2017. Selective CPS transformation for shift and reset. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM ’18). Association for Computing Machinery, New York, NY, USA, 40–52. https://doi.org/10.1145/3162069
A Selective CPS Transformationは項にアノテーションをつけてnon-trivialな継続の使用がある（可能性のある）ものをCPS変換するやつっぽいです。
Implementing First-Class Polymorphic Delimited Continuations by a Type-Directed Selective CPS-TransformはScalaの限定継続 (shift/reset) のやつで、アノテーションを使います。また、answer-type polymorphismをサポートします。
Selective CPS transformation for shift and resetはshift/reset+answer-type modificationのある体系で、（最適とは限らない）アノテーションを推論してくれるっぽい（？）です。
フルの継続は適切か？
LunarMLにもCPS変換を実装してcall/ccを一旦実装してみました：
https://github.com/minoki/LunarML/commit/3ce094815c7707aac270e282127f7a947e2d8bea
setTimeoutを同期的なsleepに見せる例は次のようになります：
val setTimeout = JavaScript.global "setTimeout";
Cont.callcc (fn suspend =>
let fun sleep delay_ms = Cont.callcc (fn cont =>
let val callback = JavaScript.function (fn arguments => Cont.throw cont ())
in JavaScript.call setTimeout #[callback, JavaScript.fromReal delay_ms]
; Cont.throw suspend ()
end
)
in print "Hello\n"
; sleep 1000.0
; print "world!\n"
; sleep 2000.0
; print "Good night!\n"
; raise Fail "Nyan\n"
end handle Fail s => print s
);
まず、外側のcallccでプログラムを中断するための継続 suspend を取得します。sleep関数では「sleep呼び出しの後に実行するべき処理」を継続 cont として取得し、その継続を呼び出すコールバックを作成し、 setTimeout にコールバック関数を渡しています。setTimeout を呼び出した後は処理を中断したいので最初に取得した継続 suspend を呼び出します。
さて、JavaScriptのコールバック関数はどういう値を返すべきでしょうか。setTimeout 的にはコールバック関数からは何を返しても無視されるので別に気にしなくて良いのですが、几帳面な人はきちんと undefined を返しておきたい、と思うかもしれません。しかし、上記のSMLコードでは返しているJavaScriptの値が明示されていません。明示的に undefined を返したいと思って
val callback = JavaScript.function (fn arguments => (Cont.throw cont (); JavaScript.undefined))
と書いてみても、Cont.throw で制御が飛ばされてしまうので JavaScript.undefined には辿り着きません。
まあcall/ccを追加で使ったり、suspend をあれこれすれば几帳面な人が満足する実装になるのかもしれませんが、筆者的にはむしろ限定継続 (delimited continuation) を使う方が適切だと思いました。
この話以外にも、call/ccは良くないんじゃないかという議論はOleg Kiselyov氏による
という記事でも色々書かれています。
余談ですが、さっきのコードのトップレベルのcall/cc呼び出しの後に処理を書くと
Cont.callcc (fn suspend => ...sleepを2回呼び出す...); print "I'm here!\n"; (* 3回実行される *)
その処理が複数回実行されます。
限定継続
フルの継続は「残りのプログラム全体」を取得しますが、限定継続はプログラマーが与えた「区切り」までの継続を取得します。
限定継続のオペレーターは何種類かあって、最もポピュラーなのはshift/resetかと思います。resetは「区切り」を与えるオペレーターです。shiftは呼び出し元を辿って直前のresetまでの継続を取得し、与えられた関数にその継続を与えて実行し、直前のresetまで脱出する関数です。
Caml Lightに限定継続を追加したOchaCaml
で例を挙げると、resetとshiftの型は
# reset;;
- : (unit => 'a) -> 'b = <fun>
# shift;;
- : (('a -> 'b) => 'c) => 'a = <fun>
となっています。二重矢印 => になっている部分は継続の副作用がある可能性のある関数です（雑）。試しに、中で何もしないreset呼び出しを書いてみると、中の値がそのまま返ってきます：
# reset (fun () -> "Hello world!");; - : string = "Hello world!"
一方、中でshiftを呼び出すと、shiftの中で返した値がresetの返り値になります：
# reset (fun () -> 1 + shift (fun k -> "foo"));; - : string = "foo"
どこぞのJavaScriptのyieldやらasync/awaitは別の関数に書いてしまうと効力を失いますが、shiftとresetは別の関数に書かれていても大丈夫です。stackfulってことですね。例外が関数を跨いでも捕捉できるのと同じような感じ（？）です。
# let f () = shift (fun k -> "foo");; f : unit => 'a = <fun> # reset (fun () -> 1 + f ());; - : string = "foo"
resetの中の型はどう見ても int で、shift呼び出しさえなければ int が返ってくるはずですが、実際にはshift呼び出しがあるせいで string が返ってきています。このように、resetが返す型がshift呼び出しによって変更される現象をanswer type modificationと呼ぶらしいです。OchaCamlはanswer type modificationをサポートする特別な型システムを持っています。OchaCamlではanswer typeを表示することも可能です：
# #answer "all";;
# reset;;
- : (unit / 'a -> 'a / 'b) -> 'b = <fun>
# shift;;
- : (('a -> 'b) / 'c -> 'c / 'd) / 'b -> 'a / 'd = <fun>
# f;;
- : unit / 'a -> 'b / string = <fun>
shiftで受け取った継続を利用する例も載せておきましょう。次のコードでは、継続 k には 1 + _ に相当する処理が束縛され、全体として 1 + (1 + 5) という計算が行われます。
# reset (fun () -> 1 + shift (fun k -> k (k 5)));; - : int = 7
【5月27日 追記】OchaCamlを使ったより詳しい限定継続入門には、浅井先生の
を読んでください。【追記終わり】
限定継続の「区切り」、resetが導入するようなやつはpromptと呼ばれることがあります。promptの名前の由来はREPLのプロンプトのことらしいです。promptを複数種類持てる (multi-prompt) システムもあります。
伝統的な（answer type modificationをサポートしない）MLの型システムに限定継続を入れる際は、multi promptを採用してpromptにanswer typeを持たせる（？）ことがあります。Monadic Frameworkの論文
- Kent Dybvig, Simon Peyton Jones, Amr Sabry. 2005. A Monadic Framework for Delimited Continuations. Journal of Functional Programming. doi:10.1017/S0956796807006259 https://www.microsoft.com/en-us/research/publication/a-monadic-framework-for-delimited-continuations/
やOCaml向けのdelimcc、それから今度GHCに入ろうとしている限定継続
ではそういう風になっています。
Monadic Frameworkの論文ではshift/resetとはちょっと違うプリミティブが採用されていますが、多分そっちの方がパワフルなんだと思います（←よくわかってない）。
one-shotかmulti-shotか
継続と単に言った場合は取得した継続を複数回呼び出せることが多いです。さっき書いたOchaCamlの例でも継続を複数回呼び出せました。
これに対して、取得した継続を一回しか呼び出せない、という制限がついた変種もあります。one-shot continuationというやつです。スタックをコピーする必要がなくて効率がいいらしいです。
Luaにあるようなstackfulなcoroutineはone-shot continuationと等価らしいです（←よくわかってない）。
非同期プログラミングが主目的ならone-shotに制限してもそんなに問題ない気がしますが、素直にCPS変換で実装するとmulti-shotのやつが得られるのでLunarMLではmulti-shotでいいかなあという気がします。
一つ、LunarMLに影響のある範囲でmulti-shotだと厄介な点を挙げておきます。「与えられた関数に0からn-1までの整数を適用した結果で配列を初期化する関数」Array.tabulateの実装を考えます。JavaScriptで書くと次のようになるでしょう：
function Array_tabulate(n, f) {
let a = new Array(n);
for (let i = 0; i < n; ++i) {
a[i] = f(i);
}
return a;
}
これを制御を複数回返す関数 f に使うと、配列を一個しか作っていないのに、同じ位置の a[i] が何回も上書きされてしまいます。対策は、一旦リストを作ってから改めて配列に詰め直すことです。
function Array_tabulate(n, f) {
let xs = List_tabulate(n, f);
return Array_fromList(xs);
}
LunarMLではどうするか
まず、JavaScriptでstackfulな継続に類する機能をやるにはCPS変換が必要です。
ただ、大域的なCPS変換はパフォーマンスへの影響が心配で、かといって最初からselective CPSをやるのも実装の手間的に大変そうです。そこで、まずは「（パフォーマンスが低くても良い）新しいバックエンドとして」CPS変換をするやつを実装します（しました）。
LunarMLの実行時に --js-cps オプションを指定するとJS-CPSバックエンドが有効になります。JS-CPSバックエンドではCPS変換して限定継続を使えるようにした上で、Standard MLをJavaScriptにコンパイルします。
Lua-CPSバックエンドはありません。Luaではそんなにガンガン非同期プログラミングをするわけでもないし、限定継続の需要はそこまでないと思っているので……。
（上の方に書いたように、当初はフルの継続 (call/cc) を実装していましたが、その後限定継続に切り替えました。）
LunarMLで限定継続を使うインターフェースはこんな感じです：
structure LunarML : sig
structure DelimCont : sig
type 'a prompt
type ('a,'b) subcont
val newPrompt : unit -> 'a prompt
val pushPrompt : 'a prompt * (unit -> 'a) -> 'a
val withSubCont : 'b prompt * (('a,'b) subcont -> 'b) -> 'a
val pushSubCont : ('a,'b) subcont * (unit -> 'a) -> 'b
val shift : 'a prompt * (('b -> 'a) -> 'a) -> 'b
val control : 'a prompt * (('b -> 'a) -> 'a) -> 'b
val abort : 'a prompt * 'a -> 'b
val topLevel : unit prompt
end
...
end
大体Monadic Frameworkのやつに沿っています。実装の話をすると、metacontinuationはグローバル変数で管理しています。shift/control/abortは組み込みではなく、4つのプリミティブ（newPrompt, pushPrompt, withSubCont, pushSubCont）を使ってSMLで実装されています。topLevelはLunarMLの独自機能で、ライブラリー実装の都合というか、ランタイムによりトップレベルに暗黙にpushされているプロンプトです。
pushPromptは大体resetに相当していて、withSubContはshiftのように継続をキャプチャーでき、pushSubContはその継続を呼び出せます（雑）。プロンプトの扱いがshiftとは違うんだっけ、みたいな話もあります。
Standard MLには既に継続を操作する機能として例外があります。Monadic Frameworkの論文は例外を考慮していないので、LunarMLの実装は手探り（フィーリング）でやっています。今のところ限定継続と例外は別々の機能として実装していますが、例外は限定継続の上に乗っける感じで実装するべきなのかもしれません。
そういえばせっかくJavaScriptを出力するのだからJavaScriptのgenerator/yieldとかasync/awaitとかの継続ライクな機能と連携できると良いかもしれません（思いつき）。
例
LunarMLの限定継続を使った例をいくつか見てみましょう。まず、「途中に0が含まれていた場合は計算を一切行わずに0を返す」リストの積の計算です。
fun product xs = let val p = DelimCont.newPrompt ()
fun loop [] = 1
| loop (0 :: _) = DelimCont.abort (p, 0)
| loop (x :: xs) = x * loop xs
in DelimCont.pushPrompt (p, fn () => loop xs)
end;
print (Int.toString (product [1, 2, 3]) ^ "\n");
print (Int.toString (product [0xffffffff, 0xffffffff, 0xffffffff, 0]) ^ "\n");
print ((Int.toString (product [0xffffffff, 0xffffffff, 0xffffffff]) handle Overflow => "Overflow") ^ "\n");
sleepの例です。
val toplevel : unit DelimCont.prompt = DelimCont.newPrompt ();
val setTimeout = JavaScript.global "setTimeout";
fun sleep delay_ms = DelimCont.withSubCont
(toplevel, fn cont : (unit, unit) DelimCont.subcont =>
let val callback = JavaScript.function
(fn arguments =>
( DelimCont.pushPrompt (toplevel, fn () => DelimCont.pushSubCont (cont, fn () => ()))
; JavaScript.undefined
)
)
in JavaScript.call setTimeout #[callback, JavaScript.fromReal delay_ms]
; ()
end
);
DelimCont.pushPrompt (toplevel, fn () =>
( print "LunarML\n"
; sleep 1000.0
; print "delimited\n"
; sleep 2000.0
; print "continuations!\n"
; raise Fail "Yay!\n"
) handle Fail s => (sleep 1000.0; print s)
);
print "supports\n";
一番外側のpushPromptの後の print "supports\n"; は一回だけ実行されます。最初のsleepで中断するタイミングです。
ここではトップレベルに相当するプロンプトを手動でpushしていますが、ランタイムが提供するLunarML.DelimCont.topLevelを使えば手動で書く必要がなくなります。
もちろん、JavaScriptのsetTimeoutに渡すコールバック関数はちゃんとundefinedを返すことがソースから明らかです。
Haskellのリストモナドみたいな非決定的計算も書けます：
fun choose (p : 'a list LunarML.DelimCont.prompt, xs : 'b list) : 'b
= LunarML.DelimCont.withSubCont (p, fn cont : ('b,'a list) LunarML.DelimCont.subcont =>
let fun loop [] = []
| loop (x :: xs) = LunarML.DelimCont.pushPrompt (p, fn () => LunarML.DelimCont.pushSubCont (cont, fn () => x)) @ loop xs
in loop xs
end
)
fun run (f : 'a list LunarML.DelimCont.prompt -> 'a list) : 'a list
= let val p = LunarML.DelimCont.newPrompt ()
in LunarML.DelimCont.pushPrompt (p, fn () => f p)
end;
val result = run (fn p =>
let val x = choose (p, [0,1,2])
val y = choose (p, [0,1,2])
val z = choose (p, [0,1,2])
in if x + y + z = 3 then
[(x,y,z)]
else
[]
end
);
List.app (fn (x,y,z) => print ("(" ^ Int.toString x ^ "," ^ Int.toString y ^ "," ^ Int.toString z ^ ")\n")) result;
その他
継続に関する最近の話題を語る上で、algebraic effectは外せなさそうです。が、今のところその辺は未調査です。
LunarMLの限定継続が要らないバックエンド（Lua, JavaScript）の最適化用の中間言語をどうするのか、結局まだ決めていません。現在はSystem Fω相当の型システムを持ったラムダ計算で適当にやっていますが、Lua/JavaScriptに変換する段階で結局ANFっぽい変換をしているので、中間言語の段階でANF+join pointsなりCPS with second-class continuationsなりを採用してガンガン最適化をかけるのが筋が良いように思えます。
ピンバック: 限定継続と例外とモナド | 雑記帳
ピンバック: 限定継続いろいろ | 雑記帳