継続渡しスタイル

関数型プログラミングにおいて、継続渡しスタイル( CPS ) は、制御が継続の形で明示的に渡されるプログラミング スタイルです。これは、通常のプログラミング スタイルである直接スタイルとは対照的です。Gerald Jay SussmanとGuy L. Steele, Jr. は、 Schemeプログラミング言語の最初のバージョンを説明したAI Memo 349 (1975)でこのフレーズを作り出しました。^{[1] [2]} John C. Reynolds は、継続に関する数多くの発見について詳しく説明しています。^[3]

継続渡しスタイルで書かれた関数は、明示的な「継続」、つまり1 つの引数を取る関数という追加の引数を取ります。CPS 関数は結果値を計算すると、この値を引数として継続関数を呼び出してその結果を「返します」。つまり、CPS 関数を呼び出す場合、呼び出し元の関数はサブルーチンの「戻り」値で呼び出されるプロシージャを提供する必要があります。この形式でコードを表現すると、直接スタイルでは暗黙的であるいくつかのことが明示されます。これには、継続の呼び出しとして明らかになるプロシージャの戻り、すべて名前が付けられた中間値、明示的に示される引数評価の順序、および呼び出し元に渡された同じ継続を変更せずにプロシージャを呼び出すだけの末尾呼び出しが含まれます。

プログラムは直接スタイルからCPSに自動的に変換できます。関数型および論理型コンパイラは、命令型または手続き型プログラミング言語のコンパイラが静的単一代入形式（SSA）を使用する中間表現としてCPSを使用することがよくあります。^[4] SSAは、形式的にはCPSのサブセットと同等です（CPSが中間表現として使用される場合に発生しない非ローカル制御フローを除きます）。^{[5]関数型コンパイラは、CPSの「}サンク」（以下の例で説明）ではなく、 A正規形（ANF）を使用することもできます（ただし、積極的な評価を必要とする言語の場合のみ） 。CPSは、ローカルまたはグローバルスタイルとしてプログラマよりも コンパイラによって頻繁に使用されます。

CPS では、各プロシージャは、関数が計算している結果に対して何を行うかを表す追加の引数を取ります。これは、通常利用可能なさまざまな構成を禁止する制限的なスタイルとともに、プログラムのセマンティクスを公開して分析しやすくするために使用されます。このスタイルにより、catch/throw やその他の非ローカルな制御の転送などの通常とは異なる制御構造も簡単に表現できます。

CPS の鍵は、(a)すべての関数が継続と呼ばれる追加の引数を取ること、(b) 関数呼び出しのすべての引数は変数またはラムダ式(より複雑な式ではない) のいずれかでなければならないことを覚えておくことです。これにより、式の最も内側の部分が最初に評価される必要があるため、式が「裏返し」になる効果があります。したがって、CPS は評価の順序と制御フローを明示的にします。直接スタイルのコード例とそれに対応する CPS を以下に示します。これらの例はScheme プログラミング言語で記述されています。慣例により、継続関数は " " という名前のパラメーターとして表されますk。

CPS バージョンでは、 や などの使用されるプリミティブは、+&それ*&自体が CPS であり、直接的なスタイルではないことに注意してください。そのため、上記の例を Scheme システムで動作させるには、次のように定義されるプリミティブの CPS バージョンを記述する必要があります*&。

(定義( *& x y k ) ( k ( * x y )))    
    

一般的にこれを実行するには、次のような変換ルーチンを記述します。

( define ( cps-prim f ) ( lambda args ( let (( r (逆引数))) (( car r ) ( apply f (逆( cdr r )))))) ( define *& ( cps-prim * )) ( define +& ( cps-prim + ))  
  
     
      
               
   
   

直接スタイルで記述されたプロシージャから CPS で記述されたプロシージャを呼び出すには、CPS プロシージャによって計算された結果を受け取る継続を提供する必要があります。上記の例では (CPS プリミティブが提供されていると仮定)、 を呼び出すことができます(factorial& 10 (lambda (x) (display x) (newline)))。

CPS でプリミティブ関数が提供される方法は、コンパイラによって多少異なります。上記では最も単純な規則を使用しましたが、2 つの可能なケースで呼び出される2 つのサンク(=& n 0 (lambda (b) (if b ...)))を受け取るブール プリミティブが提供される場合があり、その場合は上記の定義内の呼び出しf-aux&は と記述されます(=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...)))。同様に、ifプリミティブ自体が CPS に含まれておらず、代わりにif&ブール条件と条件の 2 つのアームに対応する 2 つのサンクの 3 つの引数を受け取る関数が提供される場合もあります。

上記の変換は、CPS がグローバル変換であることを示しています。直接スタイルの階乗は、予想どおり、1 つの引数を取ります。CPS の階乗は、引数と継続の 2 つを取ります。CPS 化された関数を呼び出す関数は、新しい継続を提供するか、独自の継続を渡す必要があります。CPS 化された関数から非 CPS 関数への呼び出しは、暗黙の継続を使用します。したがって、関数スタックがまったく存在しないことを保証するには、プログラム全体を CPS にする必要があります。

このセクションでは、ピタゴラスの定理をpyth使用して斜辺を計算する関数を記述します。関数の従来の実装は次のようになります。 pyth

pow2 ::浮動小数点数->浮動小数点数pow2 x = x ** 2    
     

追加:: Float -> Float -> Float追加x y = x + y      
      

pyth :: Float -> Float -> Float pyth x y = sqrt ( add ( pow2 x ) ( pow2 y ))      
         

従来の関数を CPS に変換するには、そのシグネチャを変更する必要があります。関数は関数型の別の引数を受け取り、戻り値の型はその関数によって異なります。

pow2' :: Float -> ( Float -> a ) -> a pow2' x cont = cont ( x ** 2 )        
       

' を追加:: Float -> Float -> ( Float -> a ) -> a ' x y cont = cont ( x + y )を追加          
        

-- 型 a -> (b -> c) と a -> b -> c は同等なので、CPS 関数は
-- 高階関数として見ることができます
sqrt' :: Float -> (( Float -> a ) -> a ) sqrt' x = \ cont -> cont ( sqrt x )        
       

pyth' :: Float -> Float -> ( Float -> a ) -> a pyth' x y cont = pow2' x ( \ x2 -> pow2' y ( \ y2 -> add' x2 y2 ( \ anb -> sqrt' anb cont )))          
                    

まず、関数でaの 2 乗を計算しpyth'、継続として lambda 関数を渡します。この関数は、最初の引数としてaidの 2 乗を受け取ります。計算結果に達するまでこれを繰り返します。この関数の結果を取得するには、関数を最終引数として渡し、渡された値を変更せずに返しますpyth' 3 4 id == 5.0。

GHCに同梱されている mtl ライブラリには、モジュールがありますControl.Monad.Cont。このモジュールは、Monad やその他の便利な関数を実装する Cont 型を提供します。次のスニペットは、Cont を使用する関数を示していますpyth'。

pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 )      
      

pyth_m :: Float -> Float -> Cont a Float pyth_m a b = do a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r        
    
     
     
       
      
   

構文がより簡潔になっただけでなく、この型ではcallCC型の関数を使用できるようになりましたMonadCont m => ((a -> m b) -> m a) -> m a。この関数には関数型の引数が 1 つあります。その関数引数も関数を受け入れ、その呼び出し後のすべての計算を破棄します。たとえば、pyth引数の少なくとも 1 つが負で 0 を返す場合は関数の実行を中断してみましょう。

pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do -- $ 記号は括弧を避けるのに役立ちます: a $ b + c == a (b + c) when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Applicative f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r        
         
            
     
     
       
      
   

継続を使用したプログラミングは、呼び出し元が呼び出し先の完了を待ちたくない場合にも役立ちます。たとえば、ユーザー インターフェイス (UI) プログラミングでは、ルーチンでダイアログ ボックス フィールドを設定し、継続関数とともに UI フレームワークに渡すことができます。この呼び出しはすぐに返されるため、ユーザーがダイアログ ボックスを操作している間もアプリケーション コードを続行できます。ユーザーが [OK] ボタンを押すと、フレームワークは更新されたフィールドを使用して継続関数を呼び出します。このスタイルのコーディングでは継続が使用されますが、完全な CPS ではありません。^{[説明が必要]}

関数confirmName ( ) { fields.name = name ; framework.Show_dialog_box ( fields , confirmNameContinuation ) ; }​​  
      
     


関数confirmNameContinuation ( fields ) { name = fields . name ; }  
      

関数を別のスレッドまたは別のプロセッサで実行する必要がある場合にも、同様のアイデアを使用できます。フレームワークは、呼び出された関数をワーカー スレッドで実行し、ワーカーの結果を使用して元のスレッドで継続関数を呼び出すことができます。これは、Swing UI フレームワークを使用したJava 8の場合です。

void buttonHandler () { // これは Swing UI スレッドで実行されます。// ここで UI ウィジェットにアクセスしてクエリ パラメータを取得できます。int param = getField ();  
    
    
       

    new Thread (() -> { // このコードは別のスレッドで実行されます。 //データを取得するために、データベースやネットワークなどのブロッキング リソースにアクセスするなどの操作を実行できます。 int result = lookup ( param );   
        
        
        
           

        javax.swing.SwingUtilities.invokeLater (() - > { //このコードはUI スレッドで実行され、取得したデータを使用して UI ウィジェットに入力できます。setField ( result ) ; } ) ; }). start ( ); }  
            
            
            
        
    

CPS のすべての呼び出しは末尾呼び出しであり、継続は明示的に渡されます。末尾呼び出し最適化(TCO) なしで CPS を使用すると、構築された継続が再帰中に大きくなる可能性があるだけでなく、呼び出しスタックも大きくなります。これは通常望ましくありませんが、興味深い方法で使用されています ( Chicken Schemeコンパイラを参照)。CPS と TCO は暗黙の関数戻りの概念を排除するため、これらを組み合わせて使用​​すると、ランタイムスタックの必要性を排除できます。関数型プログラミング言語のいくつかのコンパイラとインタープリタは、この機能を斬新な方法で使用しています。^[6]

継続渡しスタイルは、第一級継続は備えていないが、第一級関数と末尾呼び出し最適化を備えている関数型言語で継続と制御フロー演算子を実装するために使用できます。末尾呼び出し最適化がない場合、トランポリン、つまり、サンクを返す関数を繰り返し呼び出すループを使用するなどの手法を使用できます。第一級関数がない場合、そのようなループで末尾呼び出しを単なる goto に変換することも可能です。

CPS でコードを記述することは不可能ではありませんが、多くの場合エラーが発生しやすくなります。直接的なスタイルの式を CPS 式に変換する、純粋なラムダ計算の 1 パスまたは 2 パス変換として通常定義されるさまざまな変換があります。ただし、トランポリン スタイルで記述することは非常に困難です。使用する場合は、通常、コンパイルなどの何らかの変換の対象となります。

複数の継続を使用する関数を定義して、さまざまな制御フロー パラダイムをキャプチャできます。たとえば、( Schemeの場合)。

( define ( /& x y ok err ) ( =& y 0.0 ( lambda ( b ) ( if b ( err ( list "div by zero!" x y )) ( ok ( / x y ))))))     
     
             
                    
                   

CPS変換は概念的には米田埋め込みであることに留意すべきである。^[7]また、 π計算におけるラムダ計算の埋め込みにも似ている。^{[8] [9]}

コンピュータサイエンス以外では、CPSは、単純な表現を複雑な表現に組み立てる従来の方法の代替として、より一般的な関心を集めています。たとえば、言語意味論では、クリス・バーカーと彼の協力者は、CPSを使用して文の意味を指定することで、自然言語の特定の現象を説明できる可能性があると示唆しています。^[10]

数学において、コンピュータプログラムと数学的証明の間のカリー・ハワード同型性は、継続渡しスタイルの変換を、古典論理の直観主義（構成的）論理への二重否定埋め込みのバリエーションに関連付けます。原子命題p を(( p → ⊥) → ⊥) にマッピングする通常の二重否定変換とは異なり、継続渡しスタイルでは、⊥ を最終式の型に置き換えます。したがって、上記の例のように、結果は恒等関数をCPS 式への継続として 渡すことによって得られます。

古典論理自体は、Schemeのcall-with-current-continuation制御演算子のように、プログラムの継続を直接操作することに関連しており、これはTim Griffinによる観察である（密接に関連するC制御演算子を使用）。^[11]

• トランポリンによる末尾再帰

• Continuation Passing C (CPC) - Juliusz Chroboczek と Gabriel Kerneis によって設計および開発された、並行システムを作成するためのプログラミング言語。github リポジトリ
• ML用の CPS ベースのコンパイラの構築については、 Appel, Andrew W. (1992)「Compiling with Continuations」、Cambridge University Press、ISBNで説明されています。 978-0-521-41695-5。
• Danvy, Olivier ; Filinski, Andrzej (1992). 「制御の表現、CPS 変換の研究」.コンピュータサイエンスにおける数学的構造. 2 (4): 361– 391. CiteSeerX  10.1.1.46.84 . doi :10.1017/S0960129500001535. S2CID  8790522.
• Chicken Scheme コンパイラ。継続渡しスタイルを使用して Scheme プロシージャを C 関数に変換し、C スタックを世代別ガベージ コレクターの保育所として使用するSchemeからCへのコンパイラです。
• Kelsey , Richard A. (1995年3 月)。「継続渡しスタイルと静的単一代入形式との対応」。ACM SIGPLAN 通知。30 (3): 13– 22。CiteSeerX 10.1.1.3.6773。doi :10.1145 / 202530.202532。 
• Appel, Andrew W. (1998 年 4 月). 「SSA は関数型プログラミングです」. ACM SIGPLAN Notices . 33 (4): 17– 20. CiteSeerX  10.1.1.34.3282 . doi :10.1145/278283.278285. S2CID  207227209.
• Danvy, Olivier、Millikin, Kevin、Nielsen, Lasse R. (2007)。「ワンパス CPS 変換について」。BRICS レポート シリーズ: 24。ISSN 0909-0878。RS  -07-6。2007年10 月 26 日閲覧。
• Dybvig, R. Kent (2003). Scheme プログラミング言語. Prentice Hall. p. 64.直接リンク: 「セクション 3.4. 継続渡しスタイル」。