継続

継続は、前の状態を引き継ぐこと。持続、保持。 計算機科学における継続（けいぞく、continuation）とは、プログラムの実行においてある時点において評価されていない残りのプログラム（the rest of the program）を意味するものであり、手続き（procedure）として表現されるものである。 次のようなBASICプログラムについて考える。 10 GOTO 40 20 PRINT "WORLD" 30 STOP 40 PRINT "HELLO" 50 GOTO 20 60 END このgoto文を用いたBASICプログラムは以下のように手続きを用いて書きなおすことができる。 100 SUB L1 110 PRINT "WORLD" 120 STOP 130 END SUB 140 SUB L2 150 PRINT "HELLO" 160 CALL L1 170 END SUB 180 CALL L2 190 END 継続の骨子は、このようにgoto文などの制御構文を手続きの呼び出しとして解釈することである。例えば、書きなおす前のBASICプログラムの５０行を評価した時点における継続は具体的に表現する事は困難であるが、下のBASICプログラムであれば、単純に"HELLO"を表示した後に呼び出される手続き L1 と具体的に表現することができるようになる。 上記説明における制御構文を手続き（procedure）として表現するという手法を用いると、begin文に限定的な継続を導入することが容易に可能となる。 次に示すreset-beginマクロはbegin文と基本的挙動は同一であるが、shift-begin文を用いることによって、shift-begin行以下の継続を扱うことができる。 (define-syntax reset-begin (syntax-rules (shift-begin) ((_) #f) ((_ exp) exp) ((_ (shift-begin k body ...) exp2 ...) (let ((programpoint (lambda (res) (reset-begin exp2 ...)))) ((lambda (k) body ...) programpoint))) ((_ exp1 exp2 ...) (let ((res exp1)) (reset-begin exp2 ...))))) 上記マクロを用いた例 > (reset-begin (display "1\n") (display "2\n") (shift-begin cont (cont 0) (display "3 shifted\n")) (display "4\n") (shift-begin cont (display "5 exit\n")) (display "6\n") (display "END\n")) 1 2 4 5 exit 3 shifted 複数の段階から成るあらゆる計算において、「継続」は存在している。まず、簡単な例として、算術の計算を考えてみよう。 以下のような式を評価して、値を得るという計算を考える。 (((((1 + 2) + 3) + 4) + 5) + 6) ちょうど「3を足す」という計算が終わったところだとする。 (((6 + 4) + 5) + 6) この時、「4を足す」というのが次にするべき計算で、さらにその継続は「5を足して、さらに6を足す」というものである。 このように、コンピュータプログラムに限らず、あらゆる計算に継続は存在している。 サブルーチンの呼び出しや割り込みの際には、プログラムの元の部分から実行を再開するための情報がスタックに積まれ、必要な処理が終わるとスタックからそれを戻して実行を再開するが、この際の「実行を再開するための情報」も継続の一種である。 C言語では、setjmp関数で継続を保存し、longjmp関数でその継続に飛ぶことができるが、標準では関数呼び出しの入れ子が浅くなる側に飛ぶ場合しか保証されておらず、そのようなジャンプしか出来ないのが一般的である。 Schemeでは、call-with-current-continuation（en:call-with-current-continuation、しばしばcall/ccと略される）という関数により、「現在の継続」を明示的に取り出し、プログラムで扱うことができる（継続が第一級オブジェクトである、という）。継続を、関数のようにして呼び出すと、その引数を返戻値として、call-with-current-continuationから戻る。 Rubyでは、C言語による実装（MRIとも呼ばれる）にも、同様のcallccというメソッドがある（バージョン1.9ではcontinuationライブラリをrequireする必要がある）。 JavaScriptでは、MozillaによるJavaScript処理系の実装であるRhinoにも継続のサポートがある。 たとえばC言語ではsetjmp/longjmpで実装するような、あるいはAda、C++、Javaなどの高水準プログラミング言語では言語機能として例外処理をサポートしているが、継続を扱うことができれば、同様の「今やっている計算を打ち切り、ネストの外側に値と処理を返す」、というふるまいをプログラムできる。 Webアプリケーションにおいて、継続の利用が開発効率を上げるとして、継続を利用するスタイルでのWebアプリケーションの開発がおこなえるフレームワークが開発されており、Kahuaなどの実装例がある。通常、Webサーバではユーザからの HTTP リクエストは完全に独立したものとして扱われており、したがってサーバ上で走っているプログラムは個々のリクエストを独立した計算過程として完了しなければならなかった。しかし、多くの Web アプリケーションでは『ログイン』や『買い物カゴへの追加』など、あたかもサーバ上で連続した状態を保持しているかのような機能をユーザに対して提供する必要がある。従来のWebプログラミングでは、これは一連のリクエストをいくつかの状態に分割してサーバ上に （あるいはクッキーなどで）保存しておき、各リクエストごとにそこから復帰するという手法が一般的だったが、このようなプログラミングは複雑になりがちで、バグも起こりやすかった。しかし継続をサーバ上に保持できれば、プログラマは状態の分割をなにも考えずにあたかもユーザと 1対1で通信しているかのようなコードを書くことができる。これにより複雑な Web アプリケーションがより簡単に（バグも少なく）書けるようになると、それらのフレームワークの開発者は主張している。 例外のようなスタックの巻き戻しのような処理ばかりではなく、コルーチンのように相互に呼び出し合うような機構も継続を使って実装できる（なお、コルーチンの実装には継続の持つ能力の全ては必要ではなく、また性能や機能の理由から、スレッドやファイバーで実装されるほうが多い）。 現在主流である、LIFOの関数呼び出しではなく、全ての関数呼び出しに、その関数が終わった後実行されるべき継続を、明示的に渡す、というプログラムのスタイルがあり、プログラマが書くコードとしてだけではなく、プログラミング言語処理系の中間表現としても使われており研究されている。 Schemeでは前述のように、継続が第一級オブジェクトであり、また簡単に実行中のコンテキストから継続を取り出して使うことができる。そればかりではなく、Schemeは仕様においてプログラム意味論が与えられているが、そこでも継続を利用して定義がおこなわれている。 Scheme以前から、プログラムの理論として継続は意識されており、SECDマシンの「D」は継続そのものである。また、手続き型（命令型）プログラミング言語の表示的意味論でも、gotoなどの意味を定めるために継続を使う。 計算の残り全体を扱う継続は、扱いづらいのみならず、一種の副作用のようなふるまいをする。 これに対し、限定継続（en:delimited continuation・restricted ～、partial continuation 部分継続などとも）は、継続のうち、ある所までの計算を区切って取り出すことができる、というもので、近年研究や実装が進められている。限定継続に対し（ふつうの）継続をundelimited continuationなどと言う。 shiftとresetと呼ばれるプリミティブにより、限定された継続が作られる。Schemeでcall/ccを使った実装例が、論文 "Final shift for call/cc:: direct implementation of shift and reset" 中の§2のサーベイ中に示されている。 ^ 計算順を明示するために、全ての式に括弧を付けている。結合法則が成り立たない計算を考えているといった意味があるわけではない。 ^ RhinoWithContinuations ^ Island Life - 継続の起源 ^ Scheme:call/ccと副作用 Guy Lewis Steele, Jr. (1978), Rabbit: A Compiler for Scheme, ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf  Guy Lewis Steele, Jr. and Gerald Jay Sussman (1976), Lambda: The Ultimate Imperative, http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-353.pdf  Peter J. Landin (1965), A Generalization of Jumps and Labels, http://mirrors.csl.sri.com/www.brics.dk/%257Ehosc/local/HOSC-11-2-pp125-143.pdf  Christopher Strachey; Christopher P. Wadsworth (1974), Continuations: A Mathematical Semantics for Handling Full Jumps, http://www.ling.ohio-state.edu/research/groups/commies/past/autumn2009/strachey-wadsworth2000.pdf  Michael J. Fischer (1972), Lambda-Calculus Schemata, https://users-cs.au.dk/hosc/local/LaSC-6-34-pp259-288.pdf  Gordon Plotkin (1975), Call-by-Name, Call-by-Value and the Lambda Calculus, http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambda.pdf  Olivier Danvy , Andrzej Filinski (1990), Abstracting Control, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8753  Olivier Danvy , Andrzej Filinski (1992), Representing control: a study of the CPS transformation, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.84  Andrzej Filinski (1994), Representing Monads, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8213  Martin Gasbichler. Michael Sperber (2002), Final Shift for Call/cc: Direct Implementation of Shift and Reset, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.3425  Timothy G. Griffin (1990), A Formulae-as-Types Notion of Control, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.6893  廣川 佐千男, 亀山 幸義, 馬場 謙介 (1997), λC計算とλP計算との対応, http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0992-24.pdf  浅井 健一, shift/reset プログラミング入門, ACM SIGPLAN Continuation Workshop 2011 チュートリアルセッション資料, http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-j.pdf  John C.Reynolds (1993), The Discoveries of Continuations, http://cs.au.dk/~hosc/local/LaSC-6-34-pp233-248.pdf