読者です 読者をやめる 読者になる 読者になる

限定継続について勉強してみた(continued)

継続

日にちが開いてしまったけれど、前回の続き。


まず、meta continuation、メタ継続について。メタ継続とはつまり、「継続の継続」のことで、次のような動機により導入される概念らしい。

resetとshiftの継続意味論を再掲。

\llbracket\mbox{reset}\,E\rrbracket\rho = \lambda k.k(\llbracket E\rrbracket\rho(\lambda v.v))
\llbracket\mbox{shift}\,c\,M\rrbracket\rho = \lambda k.\llbracket M\rrbracket(\rho[c\mapsto \lambda v.\lambda k'.k' (k v)])(\lambda v.v)


ここで、resetがnon-tail callを含んでいることに注意。継続kの呼び出しは、式Eを\lambda v.vという継続とともに評価して、値が「返って」くるまで実行がサスペンドされる。関数がreturnすることを強制されるのでtail callではない。

では、tail callにするために


\llbracket\mbox{reset}\,E\rrbracket\rho = \lambda k.(\llbracket E\rrbracket\rho(\lambda v.k v))

としてはダメなのかといえば、これはよくない。Eに与えられる継続は、shiftからの脱出によって捨てられる可能性があるためだ(resetの継続kは、shiftから脱出したときでも実行されるのだから、脱出によって捨てられてしまってはいけない)。

shift内で捕捉される継続\lambda v.\lambda k'.k' (k v)についても、tail callでない形をしている。これらをtail callの形にしようというのがメタ継続。のはず。


メタ継続を導入すると、resetとshiftのsemanticsは次のようになる。

\llbracket\mbox{reset}\,E\rrbracket\rho = \lambda k.\lambda m.\llbracket E\rrbracket\rho(\lambda x.\lambda m'.m' x)(\lambda r.k r m)
\llbracket\mbox{shift}\,c\,M\rrbracket\rho =


\lambda k.\lambda m.\llbracket M\rrbracket(\rho[c\mapsto\lambda v.\lambda k'.\lambda m''.k v (\lambda w.k' w m'')]) (\lambda w.\lambda m'.m' w) m


継続は値とメタ継続を引数にとり、メタ継続は値のみを引数にとる。変数、関数抽象、関数適用それぞれに対するsemanticsはここには載せてないけれど、全部を眺めてみても、どのメタ継続がどの継続の継続処理として実行されるのかは追いきれてなかったりする。とりあえず、shift/resetのsemanticsが完全にCPSで表すことができるってことが分かればいいんだろか。それから、継続は捨てられることがあってもメタ継続は必ず実行されるということが保証されるのかな(これは実装コードからの逆算だけど)。

今まで見たきただけではメタ継続のありがたみというのは分からないんだけど、メタ継続を取り入れることでcall/ccによるshift/resetの実装ができるようになるらしい。