継続

テンプレート:See Wiktionary

計算機科学における継続（けいぞく、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 と具体的に表現することができるようになる。

Schemeマクロによる手続き言語的BEGIN文における限定的な継続の実装

上記説明における制御構文を手続き（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]。

以下のような式を評価して、値を得るという計算を考える。

(((((1 + 2) + 3) + 4) + 5) + 6)

ちょうど「3を足す」という計算が終わったところだとする。

(((6 + 4) + 5) + 6)

この時、「4を足す」というのが次にするべき計算で、さらにその継続は「5を足して、さらに6を足す」というものである。

このように、コンピュータプログラムに限らず、あらゆる計算に継続は存在している。

その他の、プログラミング言語やプログラミングと継続

サブルーチンの呼び出しや割り込みの際には、プログラムの元の部分から実行を再開するための情報がスタックに積まれ、必要な処理が終わるとスタックからそれを戻して実行を再開するが、この際の「実行を再開するための情報」も継続の一種である。

C言語では、setjmp関数で継続を保存し、longjmp関数でその継続に飛ぶことができ、多くの標準Cライブラリはレジスタの保存・復元で実装しているため、任意のジャンプに対応できるように実装されているが、ISOの仕様では関数呼び出しの入れ子が浅くなる側に飛ぶ場合しか保証されていなく、そのようなジャンプしか出来ない標準Cライブラリもある。

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にも継続のサポートがある^[2]。

応用

実用

例外的な処理の扱い

たとえばC言語ではsetjmp/longjmpで実装するような、あるいはAda、C++、Javaなどの高水準プログラミング言語では言語機能として例外処理をサポートしているが、継続を扱うことができれば、同様の「今やっている計算を打ち切り、ネストの外側に値と処理を返す」、というふるまいをプログラムできる。

Web アプリケーション

Webアプリケーションにおいて、継続の利用が開発効率を上げるとして、継続を利用するスタイルでのWebアプリケーションの開発がおこなえるフレームワークが開発されており、Kahuaなどの実装例がある。通常、Webサーバではユーザからの HTTP リクエストは完全に独立したものとして扱われており、したがってサーバ上で走っているプログラムは個々のリクエストを独立した計算過程として完了しなければならなかった。しかし、多くの Web アプリケーションでは『ログイン』や『買い物カゴへの追加』など、あたかもサーバ上で連続した状態を保持しているかのような機能をユーザに対して提供する必要がある。従来のWebプログラミングでは、これは一連のリクエストをいくつかの状態に分割してサーバ上に（あるいはクッキーなどで）保存しておき、各リクエストごとにそこから復帰するという手法が一般的だったが、このようなプログラミングは複雑になりがちで、バグも起こりやすかった。しかし継続をサーバ上に保持できれば、プログラマは状態の分割をなにも考えずにあたかもユーザと 1対1で通信しているかのようなコードを書くことができる。これにより複雑な Web アプリケーションがより簡単に（バグも少なく）書けるようになると、それらのフレームワークの開発者は主張している。

理論

コルーチン

例外のようなスタックの巻き戻しのような処理ばかりではなく、コルーチンのように相互に呼び出し合うような機構も継続を使って実装できる（なお、コルーチンの実装には継続の持つ能力の全ては必要ではなく、また性能や機能の理由から、スレッドやファイバーで実装されるほうが多い）。

継続渡しスタイル

テンプレート:Main 現在主流である、LIFOの関数呼び出しではなく、全ての関数呼び出しに、その関数が終わった後実行されるべき継続を、明示的に渡す、というプログラムのスタイルがあり、プログラマが書くコードとしてだけではなく、プログラミング言語処理系の中間表現としても使われており研究されている。

Schemeにおける継続

Schemeでは前述のように、継続が第一級オブジェクトであり、また簡単に実行中のコンテキストから継続を取り出して使うことができる。そればかりではなく、Schemeは仕様においてプログラム意味論が与えられているが、そこでも継続を利用して定義がおこなわれている。

プログラムの理論と継続

Scheme以前から、プログラムの理論として継続は意識されており^[3]、SECDマシンの「D」は継続そのものである。また、手続き型（命令型）プログラミング言語の表示的意味論でも、gotoなどの意味を定めるために継続を使う。

限定継続

計算の残り全体を扱う継続は、扱いづらいのみならず、一種の副作用のようなふるまいをする^[4]。

これに対し、限定継続（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
↑ http://blog.practical-scheme.net/shiro/20120122-origin-of-continuations
↑ http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3Acall%2Fcc%E3%81%A8%E5%89%AF%E4%BD%9C%E7%94%A8

参考文献

[1] 計算順を明示するために、全ての式に括弧を付けている。結合法則が成り立たない計算を考えているといった意味があるわけではない。

[2] RhinoWithContinuations

[3] ttp://blog.practical-scheme.net/shiro/20120122-origin-of-continuations

[4] ttp://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3Acall%2Fcc%E3%81%A8%E5%89%AF%E4%BD%9C%E7%94%A8

[1]

[2]

[3]

[4]

継続

目次

概要