継続

コンピュータサイエンスにおいて、継続とはコンピュータプログラムの制御状態の抽象表現です。継続はプログラムの制御状態を実装（具体化）します。つまり、継続はプロセス実行の特定の時点での計算プロセスを表すデータ構造です。作成されたデータ構造は、実行時環境に隠されるのではなく、プログラミング言語からアクセスできます。継続は、例外、ジェネレータ、コルーチンなど のプログラミング言語の他の制御メカニズムをエンコードするのに役立ちます。

「現在の継続」または「計算ステップの継続」とは、実行中のコードの観点から、プログラムの実行の現在のポイントから派生する継続です。継続という用語は、ファーストクラスの継続を指すためにも使用できます。ファーストクラスの継続は、プログラミング言語に、任意のポイントで実行状態を保存し、プログラムの後のポイントでそのポイントに複数回戻る機能を 提供する構造です。

継続に関する最も古い記述は、1964年9月にAdriaan van Wijngaardenによってなされました。Wijngaardenは、オーストリアのバーデン・バイ・ウィーンで開催されたIFIP形式言語記述言語ワーキング会議で講演しました。Algol 60プリプロセッサの定式化の一環として、彼は適切な手順を継続渡しスタイルに変換することを要求しましたが、^[1]彼はこの名前を使用しませんでした。彼の意図は、プログラムを単純化してその結果をより明確にすることでした。

クリストファー・ストラチー、クリストファー・P・ワズワース、ジョン・C・レイノルズは、関数型プログラミングの意味論の観点から順次プログラムを分析できるようにするために継続を広範に利用する表示的意味論の分野での研究で継続という用語を有名にしました。^[1]

スティーブ・ラッセル^[2]はIBM 704用の2番目のLisp実装で継続を発明したが、名前を付けなかった。^[3]

レイノルズ (1993) は継続の発見の完全な歴史を説明しています。

ファーストクラスの継続は、命令の実行順序を完全に制御する言語の機能です。現在の関数の呼び出しを生成した関数、または以前に終了した関数にジャンプするために使用できます。ファーストクラスの継続は、プログラムの実行状態を保存するものと考えることができます。真のファーストクラスの継続は、プロセス イメージとは異なり、プログラム データを保存せず、実行コンテキストのみを保存します。これは、「継続サンドイッチ」の説明で示されます。

たとえば、あなたがキッチンの冷蔵庫の前でサンドイッチのことを考えているとします。あなたはその場で継続を取り、それをポケットに入れます。そして冷蔵庫から七面鳥とパンを取り出し、サンドイッチを作ります。サンドイッチはカウンターの上に置かれています。あなたはポケットの中の継続を呼び出し、あなたは再び冷蔵庫の前に立ち、サンドイッチのことを考えていることに気づきます。しかし幸運なことに、カウンターの上にはサンドイッチがあり、それを作るために使われた材料はすべてなくなっています。それであなたはそれを食べます。:-) ^[4]

この説明では、サンドイッチはプログラムデータの一部(ヒープ上のオブジェクトなど) であり、「サンドイッチの作成」ルーチンを呼び出して戻るのではなく、「現在の継続でサンドイッチを作成する」ルーチンを呼び出し、サンドイッチを作成してから実行が中断したところから続行します。

Schemeは、最初に「catch」 ^[1]を提供し、次にcall/ccを提供する最初の完全な製品システムでした。Bruce Dubaはcall/ccをSMLに導入しました。

継続は、表示的意味論、アクター モデル、プロセス計算、ラムダ計算などの計算モデルでも使用されます。これらのモデルでは、プログラマーまたは意味論エンジニアが継続渡しスタイルと呼ばれる数学関数を記述します。つまり、各関数は、この関数呼び出しに関連する計算の残りを表す関数を使用します。値を返すには、関数は戻り値を使用してこの「継続関数」を呼び出します。計算を中止するには、値を返します。

継続渡しスタイルでプログラムを書く関数型プログラマーは、制御フローを任意の方法で操作する表現力を獲得します。その代償として、制御と継続の不変条件を手動で維持する必要があり、これは非常に複雑な作業になる可能性があります (ただし、以下の「継続渡しスタイル」を参照してください)。

継続は、一見無関係に見えるパターンを統合する基本的な低レベルのプリミティブを提供することで、コルーチン/グリーン スレッドや例外処理などのいくつかの一般的な設計パターンの実装を簡素化および明確化します。継続は、進むボタンと戻るボタンの使用やリンクの追跡によってアクセスされる複数のページをサポートする Web サーバーのプログラミングなど、いくつかの難しい高レベルの問題にエレガントなソリューションを提供できます。Smalltalk Seaside Web フレームワークは継続を効果的に使用しており、ページを切り替えるときに継続を切り替えることで、Web サーバーを手続き型スタイルでプログラミングできます。

「継続がエレガントな記述を提供する」^[1]より複雑な構造も存在します。たとえば、Cでは、2番目の関数がスタックのより深いところにある場合（最初の関数が戻るのを待っている場合など） 、longjmp を使用して1つの関数の途中から別の関数にジャンプできます。その他のより複雑な例としては、Simula 67、Lua、およびPerlのコルーチン、Stackless Pythonのタスクレット、IconおよびPythonのジェネレーター、 Scalaの継続（2.8 以降）、Rubyのファイバー（1.9.1 以降）、Prologのバックトラッキングメカニズム、関数型プログラミングのモナド、およびスレッドなどがあります。

Schemeプログラミング言語には、制御演算子call-with-current-continuation (略称: call/cc) が含まれており、これを使用して Scheme プログラムは制御のフローを操作できます。

 (継続#fを定義する)  

 ( define ( test ) ( let (( i 0 )) ; call/cc は最初の関数引数を呼び出し、その関数への引数としてプログラムのこのポイントを表す継続変数を渡します。 ; ; この場合、関数引数はその継続を変数 the-continuation に割り当てます。; ( call/cc ( lambda ( k ) ( set! the-continuation k ))) ; ; 次に the-continuation が呼び出されるときは、ここから開始します。( set! i ( + i 1 )) i )) 
     
     
     
     
     
     
     
     
          
     
     
         
     

上記を使用して、次のコード ブロックは、自身の将来の実行状態を test設定する関数を定義します。the-continuation

 > ( test ) 1 > ( the-continuation ) 2 > ( the-continuation ) 3 > ; 現在の継続 (次に 4 を出力します) を保存します> ( define another-continuation the-continuation ) > ( test ) ; the-continuation 1をリセットします> ( the-continuation ) 2 > ( another-continuation ) ; 以前保存した継続4を使用します 
 
  
 
  
 
  
    
   
 
  
 
   
 

このメカニズムのより簡単な紹介については、call-with-current-continuationを参照してください。

この例は、コルーチンを別々のスレッドとして実装するための継続の使用例を示しています。^[5]

 ;;; スレッド スケジューリング用の単純なキュー。
;;; 「実行を待機している」継続のリストを保持します。 

   ( *キュー* ' ()を定義します)  

   (定義(空のキュー? ) ( null? *キュー* )) 
      

   ( define ( enqueue x ) ( set! *queue* ( append *queue* ( list x ))))  
          

   ( define ( dequeue ) ( let (( x ( car *queue* ))) ( set! *queue* ( cdr *queue* )) x )) 
        
          
       

   ;;; これにより、新しいスレッドの実行が開始されます (proc)。

   (定義(プロシージャをフォーク) (呼び出し/cc (ラムダ( k ) ( kをエンキュー) (プロシージャ))))  
     
       
         
        

   ;;; 別のスレッドがある場合は、プロセッサをそのスレッドに渡します。

   (定義( yield ) (呼び出し/cc ( lambda ( k ) ( kをエンキュー) ((デキュー))))) 
     
       
         
        

   
;;; これにより、現在のスレッドが終了されます。他のスレッドが残っていない場合は、プログラム全体が終了します。   

   (定義(スレッド終了) ( if (キューが空か) (終了) ((デキュー)))) 
      
         
         

上記で定義された関数を使用すると、協調型マルチタスク、つまりキュー内の次のスレッドに制御を渡すスレッド を定義および実行できます。

   ;;; 何らかの処理を行う典型的な Scheme スレッドの本体:

   ( define ( do-stuff-n-print str ) ( lambda () ( let loop (( n 0 )) ( format #t "~A ~A \n " str n ) ( yield ) ( loop ( + n 1 )))))  
      
          
             
         
            

   ;;; 2 つのスレッドを作成し、実行を開始します。
( fork ( do-stuff-n-print "This is AAA" )) ( fork ( do-stuff-n-print "Hello from BBB" )) ( thread-exit )     
     
   

前のコードは次の出力を生成します:

これはAAA0です
 BBB 0からこんにちは
 これはAAA1です
 BBB 1からこんにちは
 これはAAA2です
 BBB 2からこんにちは
 ...

プログラムは、関数が使用する変数のためにメモリ内にスペースを割り当てる必要があります。ほとんどのプログラミング言語では、必要な変数を格納するためにコールスタックを使用します。これは、メモリの割り当てと解放を高速かつ簡単に行えるためです。他のプログラミング言語では、メモリの割り当てと解放に高いコストがかかりますが、柔軟性を確保するためにヒープを使用します。これらの実装はどちらも、継続のコンテキストでは利点と欠点があります。^[6]

多くのプログラミング言語では、さまざまな名前でファーストクラスの継続が表現されています。具体的には、次のようになります。

• Common Lisp : cl-cont。カスタムマクロも使用可能
• C# / VB.NET :asyncおよびawait: 「メソッドの残りを継続として登録し、すぐに呼び出し元に戻ります。タスクは完了時に継続を呼び出します」。C# の非同期プログラミング
• 要因:callcc0およびcallcc1
• Haskell :継続モナドControl.Monad.Cont
• Haxe : haxe 継続
• Icon、Unicon  :create, suspend, @演算子: 共式
• Java : Lightwolf javaflow (実行時またはコンパイル時にバイトコードの操作が必要)
• コトリン :Continuation
• JavaScript ライノ :Continuation
• Parrot : ContinuationPMC;すべての制御フローに継続渡しスタイルを使用する
• Perl : Coro と継続性
• ピコ：call(exp())そしてcontinue(aContinuation, anyValue)
• Python : PyPyの_continuation.continulets
• ラケット: call-with-current-continuation(一般的には と略されるcall/cc)
• ルビー：callcc
• Scala :scala.util.continuations提供shift/reset
• スキーム: call-with-current-continuation(一般的には と略されるcall/cc)
• Smalltalk : Continuation currentDo:; 最近のほとんどの Smalltalk 環境では、追加の VM サポートなしで継続を実装できます。
• ニュージャージー州の標準 ML :SMLofNJ.Cont.callcc
• Unlambda : c、現在の継続を伴う呼び出しのフロー制御操作

クロージャと適切な末尾呼び出しをサポートする言語であれば、継続渡しスタイルでプログラムを記述し、 call/cc を手動で実装することができます。(継続渡しスタイルでは、 call/cc はlambdaで記述できる単純な関数になります。) これはHaskellで特に一般的な戦略で、"継続渡しモナド" (たとえば、ライブラリのContモナドとContTモナド トランスフォーマー) を簡単に構築できます。継続渡しスタイルでは関数が返されることはなく、すべての呼び出しが末尾呼び出しであるため、適切な末尾呼び出しmtlのサポートが必要です。

継続の実用化が見られる分野の一つは、Webプログラミングである。^{[7] [8]}継続の使用は、プログラマーをHTTPプロトコルのステートレスな性質から保護する。Webプログラミングの従来のモデルでは、状態の欠如がプログラムの構造に反映され、計算上の問題を表現するのに非常に不向きなモデルを中心に構築されたコードにつながる。したがって、継続は、制御の反転に関連する有用な特性を持つコードを可能にし、その問題を回避します。「制御の反転を元に戻す、または継続とページ中心のプログラミング」^[9]は、Webプログラミングに適用される継続の優れた入門書である。

継続のサポートは多岐にわたります。プログラミング言語は、継続が繰り返し呼び出される可能性がある場合 (すでに戻った後でも)、再呼び出し可能な継続をサポートします。再呼び出し可能な継続は、Peter J. Landin によって、制御のフローをプロシージャ呼び出しの途中に戻すことができるJ (Jump の略) 演算子を使用して導入されました。再呼び出し可能な継続は、 Racket言語では「再入可能」とも呼ばれています。ただし、この「再入可能」という用語の使用は、マルチスレッドの説明での使用と混同されやすい場合があります。

より限定された種類は、現在のコンテキストを周囲のコンテキストにエスケープするために使用できるエスケープ継続です。継続を明示的にサポートしていない多くの言語は、エスケープ継続と同等であり、同じ目的で使用できる例外処理をsetjmp/longjmpサポートしています。Cも同様です。スタックを巻き戻すためにのみ使用できます。エスケープ継続は、末尾呼び出しの削除を実装するためにも使用できます。

継続の一般化の 1 つに、区切られた継続があります。 のような継続演算子は、プログラム内の特定の時点での残りの計算全体call/ccをキャプチャしますが、このキャプチャを区切る方法はありません。 区切られた継続演算子は、継続操作を区切るプロンプトと、 またはなどの具体化演算子という2 つの別個の制御メカニズムを提供することで、この問題に対処します。 区切られた演算子を使用してキャプチャされた継続は、したがって、プログラム コンテキストの一部のみを表します。 shiftcontrol

継続はGOTOステートメントの機能的表現であり、同じ注意事項が適用されます。^[10] 継続は Web プログラミングなどの特殊なケースでは賢明な選択肢ですが、継続を使用すると、追跡が困難なコードになる可能性があります。実際、難解なプログラミング言語 Unlambdaには、call-with-current-continuation が機能の 1 つとして含まれていますが、これは、それを含む式が「追跡するのが絶望的に​​困難になる傾向がある」ためです。^[11]以下の外部リンクでは、この概念をより詳細に説明しています。

「継続と量化の性質」の中で、クリス・バーカーは「継続仮説」を提唱した。

いくつかの言語表現（特にQNP（量化名詞句））には、それ自身の継続を操作する外延がある。^[12]

バーカーは、この仮説は、NP の意味の二重性(例: QNP「everyone」は、非量化名詞句「Bob」とは大きく異なる動作をし、「Alice sees [Bob/everyone]」のような文の意味に貢献する)、スコープの置換(例: 「a raindrop fell on every car」は、通常ではなく と解釈される)、スコープの曖昧性(「someone saw every」のような文はと の間では曖昧になる可能性がある) などの現象を説明するのに使用できると主張した。彼はまた、この考え方は、ある意味ではリチャード・モンタギューの「The Proper Treatment of Quantification in Ordinary English」(PTQ) におけるアプローチの自然な延長に過ぎないと指摘し、「後知恵ではあるが、モンタギュー (1973) の PTQ における NP の一般化量化子としての扱いの核心には、限定された形式の継続渡しが明らかに認められる」と書いている。 ${\displaystyle \forall c\exists r,{\mbox{fell}}(r,c)}$${\displaystyle \exists r\forall c,{\mbox{fell}}(r,c)}$${\displaystyle \exists x\forall y,{\mbox{saw}}(x,y)}$${\displaystyle \forall y\exists x,{\mbox{saw}}(x,y)}$

継続が自然言語における他の一般的な現象を説明するためにどの程度使用できるかは、現在研究されているテーマである。^[13]

• 現在の継続を伴う呼び出し
• 閉鎖
• 由来
• 継続渡しスタイル
• 制御フロー
• コルーチン
• 限定継続
• 表示的意味論
• 後藤
• スパゲッティスタック
• Quajects は、依存性注入を通じて、オブジェクトごとにメソッドに対して選択可能な継続 (「コールアウト」と呼ばれる) を設定できるオブジェクトの種類です。

• Peter Landin . ジャンプとラベルの一般化 レポート。UNIVAC Systems Programming Research。1965 年 8 月。Higher Order and Symbolic Computation、11(2):125-143、1998 年に Hayo Thielecke による序文付きで再版。
• Drew McDermottおよびGerry Sussman。The Conniver Reference Manual MIT AI Memo 259。1972 年 5 月。
• Daniel Bobrow :人工知能プログラミング言語の制御構造モデルIJCAI 1973。
• Carl Hewitt、Peter Bishop、Richard Steiger。人工知能のためのユニバーサル モジュラー アクター形式 IJCAI 1973。
• Christopher Stracheyおよび Christopher P. Wadsworth。Continuations : フルジャンプを処理するための数学的セマンティクステクニカルモノグラフ PRG-11。オックスフォード大学コンピューティング研究所。1974 年 1 月。2000 年に Christopher P. Wadsworth による序文付きで Higher Order and Symbolic Computation、13(1/2):135—152 に再版。
• John C. Reynolds .高階プログラミング言語の定義的インタープリタ、第25回ACM全国会議論文集、pp. 717–740、1972年。序文付きでHigher-Order and Symbolic Computation 11(4):363-397、1998年に再版。
• John C. Reynolds.直接意味論と継続意味論の関係について、オートマトン、言語、プログラミングに関する第 2 回コロキウムの議事録。LNCS 第 14 巻、pp. 141–156、1974 年。
• Reynolds, John C. (1993). 「継続の発見」(PDF) . LISP と記号計算. 6 (3/4): 233–248.
• ジェラルド・サスマン、ガイ・スティール「SCHEME: 拡張ラムダ計算のインタープリター」 AI メモ 349、MIT 人工知能研究所、マサチューセッツ州ケンブリッジ、1975 年 12 月。1998 年に序文付きで Higher-Order and Symbolic Computation 11(4):405-439 に再掲載。
• Robert Hieb、R. Kent Dybvig、Carl Bruggeman。第一級継続が存在する場合の制御の表現、 ACM SIGPLAN '90 プログラミング言語の設計と実装に関する会議の議事録、66～77 ページ。
• Will Clinger、Anne Hartheimer、Eric Ost。継続の実装戦略、 1988 ACM LISP および関数型プログラミング会議の議事録、pp. 124–131、1988 年。ジャーナル版: Higher-Order and Symbolic Computation、12(1):7-45、1999 年。
• Christian Queinnec.制御の反転を元に戻す、または継続とページ中心のプログラミングSIGPLAN Notices 38(2)、pp. 57–64、2003。

• ICFPでのACM SIGPLAN継続に関するワークショップ 2011 。
• サム・ルビーによる「Curmudgeons」の続編
• Dorai Sitaram 著の『Teach Yourself Scheme in Fixnum Days』には、継続に関する優れた章があります。
• Christian Tismer による継続とスタックレス Python
• 第 4 回 ACM SIGPLAN 継続ワークショップのオンライン議事録。2010 年 12 月 2 日にWayback Machineにアーカイブされました。
• 第 2 回 ACM SIGPLAN 継続ワークショップのオンライン議事録
• 継続、関数、ジャンプ 2010-12-02 にWayback Machineでアーカイブされました
• http://okmij.org/ftp/continuations/ by Oleg Kiselyov
• https://wiki.haskell.org/Continuations ^{[永久リンク切れ‍ ]}
• 継続を伴う Rhino
• RIFE Web アプリケーション フレームワークからの純粋な Java での継続
• 純粋な Java での継続のデバッグRIFE Web アプリケーション フレームワークから2021-05-16 にWayback Machineでアーカイブされました
• ジェネレータ、コルーチン、継続の比較、上記例のソース