継続

計算機科学における継続（けいぞく、continuation）とは、プログラムを実行中のある時点において、評価されていない残りのプログラム（the rest of the program）を表現するものであり、手続き（procedure）あるいは関数（function）として表現されるものである^[1]。

継続に相当する概念は1960年代初頭から存在しており、Algol 60のコンパイラの実装^[2]などの文献にたびたび登場していたが、継続の利用に関する最も早い記述は、1964年のアドリアン・ファン・ワインハールデン (en:Adriaan van Wijngaarden) によるものである^[1]。

概要

計算一般における継続

Schemeによる次の式を考える：

(+ 4 (+ 1 2))

この式を評価する際、まず (+ 1 2) が計算され、すなわち 1+2 が計算され、次にその結果に4を足して全体の計算結果が求められる。(+ 1 2) の評価が行われた段階での「残りの計算」を表現すると、

(lambda (v) (+ 4 v))

のようになる^[3]。この式はすなわち、値 $v$ を引数に取り、それに4を足した値を返す関数である。実際、この後 (+ 1 2) の計算結果が $v$ に代入されて、4を足した値が最終的に計算結果が求められるため、この関数は確かに (+ 1 2) を評価する段階での「残りの計算」の表現である。

call/cc

Schemeの call-with-current-continuation (call/cc と省略される) は、その時点での継続を引数として関数を呼び出す手続きである。Schemeの言語仕様書（R7RS^[4]）には「もっとも単純な例」として次のコードが載っている：

(define list-length
  (lambda (obj)
    (call-with-current-continuation
      (lambda (return)
        (letrec ((r
              (lambda (obj)
                (cond ((null? obj) 0)
                  ((pair? obj)
                    (+ (r (cdr obj)) 1))
                  (else (return #f))))))
          (r obj))))))

このコードは、真正な（終端が空リストである）リストが渡された際にはそのリストの要素数を数えて返し、そうでない場合はfalse値を返す。

goto文を持つ言語の意味論

継続の概念はgoto文を持つ言語に意味論を与える。goto文を持たない場合、意味論は例えば命令文 $γ$ 、変数に対する値の割り当て $ρ$ 、抽象機械の状態遷移 $θ ∊ [S \to S]$ ( $S$ は機械の状態空間を表す) を用いて ${\mathcal {C}}[\gamma ](\rho )=\theta$ のように与えられる^[5]^[6]。この意味論において、2つの命令の逐次実行は2つの状態遷移の合成として表すことができるが、goto文が存在する言語の場合、goto文の直後の命令は、goto文を実行した直後に実行されるわけではないため、少なくともそのように意味論を与えることはできない。

goto文を持つような言語において、意味論を与える写像 ${\textstyle {\mathcal {P}}}$ は例えば、命令文の集合 $Cmd$ 、環境の集合 $Env$ 、継続の集合 $C$ 、機械の状態の集合 $S$ を用いて次のような型を持つ： ${\mathcal {P}}:[{\mathit {Cmd}}\to [{\mathit {Env}}\to [C\to [S\to S]]]]$ ここで継続は $C = [S \to S]$ すなわち状態の遷移として、また環境 $Env$ は ${\textstyle D\supset C}$ を満たすようなラベルの集合 $D$ と識別子の集合 $Id$ を用いて $Env = [Id \to D]$ と表される。命令文 $γ$ と環境 $ρ$ に対して、 ${\mathcal {P}}[\gamma ]\rho$ は継続を受け取って継続を返す関数の形となる。

この設定の下でgoto文はラベルの識別子 ${\textstyle \xi \in {\mathit {Id}}}$ に対して ${\mathcal {P}}[\mathop {\mathbf {goto} } \xi ]\rho \theta \sigma =(\rho [\xi ]|_{C})\sigma$ のように実装される。ここで ${\textstyle \rho [\xi ]|_{C}}$ とは ${\textstyle \rho [\xi ]\in D}$ の $C$ への射影であり、動的な型検査としての働きを持つものである^[5]。

応用

実用

例外的な処理の扱い

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

Web アプリケーション

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

マイクロカーネル（Mach 3.0）

Mach 3.0では、あるタスクがスリープ中の別のタスクを実行可能とする一方、自分自身はその処理待ちでスリープする状況において継続をサポートしている。

Mach 3.0は当時既存のUnix系OSとの互換性や応用を維持しつつ本格的なマイクロカーネルを実装したが、それに伴いCPUのスレッド数に比べてタスクのスレッド数がはるかに多くなった。これらのタスクはカーネル内でスリープする際にカーネルスタックを必要とし、そのためのメモリ消費がシステム全体を圧迫する問題が生じた。この問題を軽減するため、Mach 3.0ではタスクがスリープする際にオプションとして継続の規約をサポートし、保存が必要なデータをタスクに紐付いたメモリに退避した上でカーネルスタックを回収できるようにした。継続を使用してスリープしているタスクが実行可能となった場合は、カーネルから新たにカーネルスタックを受け取った上でタスクのメモリからデータを復元し、実行を再開するようにした。実行再開時のエントリポイントはスリープ時の処理とは別の箇所でも問題なく、これにより継続のセマンティクスを実装している。

回収されたカーネルスタックは通常は実行可能になった別のタスクへそのまま渡し、直ちに再利用するようにしている。これにより、カーネルスタックは原則として各タスクではなくCPUのスレッドに紐付いたリソースとしている。

理論

コルーチン

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

継続渡しスタイル

→詳細は「継続渡しスタイル」を参照

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

Schemeにおける継続

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

プログラムの理論と継続

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

限定継続

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

これに対し、限定継続（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のサーベイ中に示されている。

脚注

[脚注の使い方]

出典

^ ^a ^b Reynolds, John C. (1993-11). “The discoveries of continuations” (英語). LISP and Symbolic Computation 6 (3-4): 233–247. doi:10.1007/BF01019459. ISSN 0892-4635.
^ Naur, Peter (1963-06). “The design of the GIER ALGOL compiler Part I” (英語). BIT 3 (2): 124–140. doi:10.1007/BF01935579. ISSN 0006-3835.
^ “Scheme: Continuations and exceptions”. CSE 341 : Programming Languages Winter 2004 (Lecture Notes). University of Washington, Department of Computer Science and Engineering. 2022年5月30日閲覧。
^ “Revised⁷ Report on the Algorithmic Language Scheme”. Scheme Working Group 1. 2022年5月31日閲覧。
^ ^a ^b Strachey, Christopher; Wadsworth, Christopher P. (2000). “Continuations: A Mathematical Semantics for Handling Full Jumps”. Higher-Order and Symbolic Computation 13 (1/2): 135–152. doi:10.1023/A:1010026413531.
^ Scott, Dana; Strachey, Christopher (1971). Toward a Mathematical Semantics for Computer Languages (Report). Technical Monograph (英語). Oxford: Oxford University Computing Laboratory, Programming Research Group.
^ Island Life - 継続の起源
^ Scheme:call/ccと副作用

参考文献

[:0-1] Reynolds, John C. (1993-11). “The discoveries of continuations” (英語). LISP and Symbolic Computation 6 (3-4): 233–247. doi:10.1007/BF01019459. ISSN 0892-4635.

[2] Naur, Peter (1963-06). “The design of the GIER ALGOL compiler Part I” (英語). BIT 3 (2): 124–140. doi:10.1007/BF01935579. ISSN 0006-3835.

[3] “Scheme: Continuations and exceptions”. CSE 341 : Programming Languages Winter 2004 (Lecture Notes). University of Washington, Department of Computer Science and Engineering. 2022年5月30日閲覧。

[4] “Revised⁷ Report on the Algorithmic Language Scheme”. Scheme Working Group 1. 2022年5月31日閲覧。

[:1-5] Strachey, Christopher; Wadsworth, Christopher P. (2000). “Continuations: A Mathematical Semantics for Handling Full Jumps”. Higher-Order and Symbolic Computation 13 (1/2): 135–152. doi:10.1023/A:1010026413531.

[6] Scott, Dana; Strachey, Christopher (1971). Toward a Mathematical Semantics for Computer Languages (Report). Technical Monograph (英語). Oxford: Oxford University Computing Laboratory, Programming Research Group.

[7] Island Life - 継続の起源

[8] Scheme:call/ccと副作用

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]