継続

計算機科学における継続 (Continuation)

継続とは、プログラムの実行中に、ある時点における未評価の残りの処理を指す概念です。これは、手続きや関数として表現され、プログラムの流れを制御するための強力なツールとして利用されます。

歴史

継続の概念自体は1960年代初頭から存在し、Algol 60コンパイラの実装などで言及されていました。しかし、継続の利用に関する初期の記述は、1964年のアドリアン・ファン・ワインハールデンの研究に見られます。

概要

継続は、プログラムの実行を「中断」し、後でその状態から「再開」できるメカニズムを提供します。これにより、複雑な制御フローを扱うことが可能になります。

計算一般における継続

例えば、Schemeというプログラミング言語で `(+ (+ 1 2) 4)` という式を評価する際、`( + 1 2)` が評価された時点での「残りの計算」は、その結果に `4` を足す処理です。これを関数で表現すると、`λv. (+ v 4)` のようになります。このように、計算の途中の状態を表現するものが継続です。

`call/cc`

Schemeには `call-with-current-continuation` (略して `call/cc`) という特殊な手続きがあります。`call/cc` は、その時点での継続を引数として関数を呼び出します。これにより、現在の実行状態を捕捉し、後でその状態から実行を再開することができます。

scheme
(define (count-list lst)
(call-with-current-continuation
(lambda (return)
(letrec ((iter (lambda (l)
(cond ((null? l) 0)
((not (pair? l)) (return #f))
(else (+ 1 (iter (cdr l))))))))
(iter lst)))))

(count-list '(1 2 3)) ; => 3
(count-list '(1 2 . 3)) ; => #f


このコードは、リストの要素数を数える関数ですが、リストが不正な形式の場合、`return` という継続を使って、直ちに `#f` を返します。

`goto` 文を持つ言語の意味論

継続は、`goto` 文を持つ言語に意味論を与えるためにも使用されます。`goto` 文は、プログラムの実行フローを任意の位置にジャンプさせるため、通常の順次実行では説明が難しいのですが、継続を使うことで、`goto` 先の処理を継続として捉え、意味を与えることができます。

意味論における継続

命令文 γ、変数に対する値の割り当て ρ、抽象機械の状態遷移 θ を用いて、`Cγ = θ` のように意味論を与える場合、`goto` 文が存在すると、この表現だけでは意味を与えることができません。継続を用いると、命令の実行後に行うべき処理を継続として表現し、`goto` 文でジャンプする場合も、そのジャンプ先の継続を実行することで、意味を与えることができます。以下のような型を持ちます。

`P:[Cmd → [Env → [C → [S → S]]]]`

ここで、`C` は継続を表し、`S` は機械の状態を表します。`goto` 文は、ラベルの識別子 `ξ` を用いて次のように実装されます。

`P[goto ξ]ρθσ = (ρ[ξ]|C)σ`

応用

継続は、以下のような様々な場面で応用されています。

実用

例外的な処理の扱い: C言語の `setjmp`/`longjmp` のような例外処理を、継続を使って実現できます。これにより、現在の処理を中断し、ネストの外側に値や処理を返すことができます。

Webアプリケーション: 継続を利用することで、Webアプリケーションで状態を保持しやすくなります。これにより、ユーザーとの対話的な処理を、より自然に記述することができます。例えば、Kahuaのようなフレームワークでは、継続を使ってWebアプリケーション開発を効率化しています。

マイクロカーネル: Mach 3.0のようなマイクロカーネルでは、スリープ中のタスクを再開するために継続が利用されています。これにより、カーネルスタックのメモリ消費を削減し、効率的なリソース管理を実現しています。

理論

コルーチン: 継続を使うと、コルーチンのように、複数の処理が相互に呼び出し合う機構を実装できます。ただし、コルーチンはスレッドやファイバーで実装されることが多いです。

* 継続渡しスタイル: 関数呼び出しの際に、その関数が終わった後に実行されるべき継続を明示的に渡すプログラムのスタイルです。プログラミング言語処理系の中間表現としても使われています。

Schemeにおける継続

Schemeは、継続を第一級オブジェクトとして扱い、実行中のコンテキストから継続を取り出して利用できます。また、Schemeの言語仕様は、継続を使って定義されています。

プログラムの理論と継続

継続は、プログラムの理論において重要な概念です。SECDマシンの `D` は継続を表し、手続き型言語の表示的意味論でも、`goto` の意味を定義するために継続が使われます。

限定継続

限定継続は、継続のうち、ある部分だけを取り出すことができる概念です。`shift` と `reset` というプリミティブを使って、限定された継続を作成できます。限定継続は、近年研究や実装が進められています。

まとめ

継続は、計算機科学における強力な概念であり、プログラムの制御、例外処理、Webアプリケーション開発、マイクロカーネルなど、幅広い分野で応用されています。また、理論的な側面も深く研究されており、プログラムの意味論や、新たなプログラミングパラダイムの探求に貢献しています。

もう一度検索