継続のソースを表示

{{See Wiktionary|プログラムの継続|継続}}{{参照方法|date=2022年5月}}
計算機科学における'''継続'''（けいぞく、continuation）とは、プログラムを実行中のある時点において、評価されていない残りのプログラム（the rest of the program）を表現するものであり、手続き（procedure）あるいは関数（function）として表現されるものである<ref name=":0">{{Cite journal|last=Reynolds|first=John C.|date=1993-11|title=The discoveries of continuations|url=http://link.springer.com/10.1007/BF01019459|journal=LISP and Symbolic Computation|volume=6|issue=3-4|pages=233–247|language=en|doi=10.1007/BF01019459|issn=0892-4635}}</ref>。

継続に相当する概念は1960年代初頭から存在しており、[[ALGOL|Algol 60]]のコンパイラの実装<ref>{{Cite journal|last=Naur|first=Peter|date=1963-06|title=The design of the GIER ALGOL compiler Part I|url=http://link.springer.com/10.1007/BF01935579|journal=BIT|volume=3|issue=2|pages=124–140|language=en|doi=10.1007/BF01935579|issn=0006-3835}}</ref>などの文献にたびたび登場していたが、継続の利用に関する最も早い記述は、1964年のアドリアン・ファン・ワインハールデン{{Enlink|Adriaan van Wijngaarden|3=en}}によるものである<ref name=":0" />。

== 概要 ==
=== 計算一般における継続 ===
[[Scheme]]による次の式を考える：<syntaxhighlight lang="scheme">
(+ 4 (+ 1 2))
</syntaxhighlight>この式を評価する際、まず {{Code|(+ 1 2)|scheme}} が計算され、すなわち 1+2 が計算され、次にその結果に4を足して全体の計算結果が求められる。{{Code|(+ 1 2)|scheme}} の評価が行われた段階での「残りの計算」を表現すると、<syntaxhighlight lang="scheme">
(lambda (v) (+ 4 v))
</syntaxhighlight>のようになる<ref>{{Cite web |url=https://courses.cs.washington.edu/courses/cse341/04wi/lectures/15-scheme-continuations.html |title=Scheme: Continuations and exceptions |access-date=2022-05-30 |publisher=University of Washington, Department of Computer Science and Engineering |work=CSE 341 : Programming Languages Winter 2004 (Lecture Notes)}}</ref>。この式はすなわち、値 {{Mvar|v}} を引数に取り、それに4を足した値を返す関数である。実際、この後 {{Code|(+ 1 2)|scheme}} の計算結果が {{Mvar|v}} に代入されて、4を足した値が最終的に計算結果が求められるため、この関数は確かに {{Code|(+ 1 2)|scheme}} を評価する段階での「残りの計算」の表現である。

=== call/cc ===
Schemeの {{Code|call-with-current-continuation|scheme}} ({{Code|call/cc|scheme}} と省略される) は、その時点での継続を引数として関数を呼び出す手続きである。Schemeの言語仕様書（R7RS<ref>{{Cite web |url=https://small.r7rs.org/attachment/r7rs.pdf |title=Revised{{Sup|7}} Report on the Algorithmic Language Scheme |access-date=2022-05-31 |publisher=Scheme Working Group 1}}</ref>）には「もっとも単純な例」として次のコードが載っている：<syntaxhighlight lang="scheme">
(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))))))
</syntaxhighlight>このコードは、真正な（終端が空リストである）リストが渡された際にはそのリストの要素数を数えて返し、そうでない場合はfalse値を返す。

=== goto文を持つ言語の意味論 ===
継続の概念は[[goto文]]を持つ言語に意味論を与える。goto文を持たない場合、意味論は例えば命令文 {{Mvar|γ}}、変数に対する値の割り当て {{Mvar|ρ}}、抽象機械の状態遷移 {{Math|''θ'' ∊ [''S'' → ''S'']}} ({{Mvar|S}} は機械の状態空間を表す) を用いて<math display="block">\mathcal{C}[\gamma](\rho)=\theta</math>のように与えられる<ref name=":1">{{Cite journal|last=Strachey|first=Christopher|last2=Wadsworth|first2=Christopher P.|date=2000|title=Continuations: A Mathematical Semantics for Handling Full Jumps|url=http://link.springer.com/10.1023/A:1010026413531|journal=Higher-Order and Symbolic Computation|volume=13|issue=1/2|pages=135–152|doi=10.1023/A:1010026413531}}</ref><ref>{{Cite report|last=Scott|first=Dana|first2=Christopher|last2=Strachey|url=https://www.cs.ox.ac.uk/publications/publication3723-abstract.html|title=Toward a Mathematical Semantics for Computer Languages|year=1971|publisher=Oxford University Computing Laboratory, Programming Research Group|location=Oxford|series=Technical Monograph|number=PRG-6|language=en}}</ref>。この意味論において、2つの命令の逐次実行は2つの状態遷移の合成として表すことができるが、goto文が存在する言語の場合、goto文の直後の命令は、goto文を実行した直後に実行されるわけではないため、少なくともそのように意味論を与えることはできない。


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


この設定の下でgoto文はラベルの識別子 <math display="inline">\xi\in\mathit{Id}</math> に対して<math display="block">\mathcal{P}[\mathop{\mathbf{goto}}\xi]\rho\theta\sigma=(\rho[\xi]|_C)\sigma</math>のように実装される。ここで <math display="inline">\rho[\xi]|_C</math> とは <math display="inline">\rho[\xi]\in D</math> の {{Mvar|C}} への射影であり、動的な型検査としての働きを持つものである<ref name=":1" />。

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

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

==== マイクロカーネル（Mach 3.0） ====
[[Mach|Mach 3.0]]では、あるタスクがスリープ中の別のタスクを実行可能とする一方、自分自身はその処理待ちでスリープする状況において継続をサポートしている。

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

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

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

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

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

==== プログラムの理論と継続 ====
Scheme以前から、プログラムの理論として継続は意識されており<ref>[http://blog.practical-scheme.net/shiro/20120122-origin-of-continuations Island Life - 継続の起源]</ref>、[[SECDマシン]]の「D」は継続そのものである。また、手続き型（命令型）プログラミング言語の[[表示的意味論]]でも、gotoなどの意味を定めるために継続を使う。

==== 限定継続 ====
計算の残り全体を扱う継続は、扱いづらいのみならず、一種の[[副作用 (プログラム)|副作用]]のようなふるまいをする<ref>[http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3Acall%2Fcc%E3%81%A8%E5%89%AF%E4%BD%9C%E7%94%A8 Scheme:call/ccと副作用]</ref>。

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

== 脚注 ==
{{脚注ヘルプ}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* {{Citation |author=Guy Lewis Steele, Jr.|year=1978|title=Rabbit: A Compiler for Scheme|url=ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-474.pdf}}
* {{Citation |author=Guy Lewis Steele, Jr. and Gerald Jay Sussman|year=1976|洋書|title=Lambda: The Ultimate Imperative|postscript={{dl|date=2022-05}}|url=http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-353.pdf}}
* {{Citation |author=Peter J. Landin| year=1965|洋書| title=A Generalization of Jumps and Labels |postscript={{dl|date=2022-05}}| url=http://mirrors.csl.sri.com/www.brics.dk/%257Ehosc/local/HOSC-11-2-pp125-143.pdf}}
* {{Citation |author=Michael J. Fischer|year=1972|洋書| title=Lambda-Calculus Schemata|postscript={{dl|date=2022-05}}|url=https://users-cs.au.dk/hosc/local/LaSC-6-34-pp259-288.pdf}}
* {{Citation |author=Gordon Plotkin|year=1975| title=Call-by-Name, Call-by-Value and the Lambda Calculus|url=http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambda.pdf}}
* {{Citation |author=Olivier Danvy , Andrzej Filinski|year=1990|title=Abstracting Control|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8753}}
* {{Citation |author=Olivier Danvy , Andrzej Filinski|year=1992|title=Representing control: a study of the CPS transformation|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.84}}
* {{Citation |author=Andrzej Filinski|year=1994|title=Representing Monads|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8213}}
* {{Citation |author=Martin Gasbichler. Michael Sperber|year=2002|title=Final Shift for Call/cc: Direct Implementation of Shift and Reset|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.3425}}
* {{Citation |author=Timothy G. Griffin|year=1990|title=A Formulae-as-Types Notion of Control|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.6893}}
* {{cite journal|和書|author=廣川佐千男, 亀山幸義, 馬場謙介 |date=1997-05 |url=https://hdl.handle.net/2433/61141 |title=λC計算とλP計算との対応(計算理論とその応用) |journal=数理解析研究所講究録 |ISSN=1880-2818 |publisher=京都大学数理解析研究所 |volume=992 |pages=167-174 |hdl=2433/61141 |CRID=1050001201936747648 |ref=harv}}
* {{Citation | author=浅井 健一 | others=ACM SIGPLAN Continuation Workshop 2011 チュートリアルセッション資料 | title=shift/reset プログラミング入門| url=http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-j.pdf}}

{{DEFAULTSORT:けいそく}}
[[Category:制御構造]]