Loading article…
プログラミング言語では、区切り継続、構成可能継続、または部分継続は、関数に具体化された継続フレームの「スライス」です。通常の継続とは異なり、区切り継続は値を返すため、再利用および構成できます。区切り継続の基礎となる制御区切り子は、1988 年にMatthias Felleisenによって導入されました[ 1 ]。ただし、構成可能継続と区切り継続に関する初期の言及は、 Carolyn Talcottの 1984 年のスタンフォード大学の博士論文 Felleisen et al.に見られます。 [ 2 ]フェレイゼンの 1987 年の博士論文、[ 3 ]および関数バックトラッキングのアルゴリズム、例えば、パターンマッチング、構文解析、代数論理関数プログラミング言語、およびPrologの関数実装で は、失敗継続は暗黙的に保持されることが多く、成功継続が存在する理由はそれが構成可能であるためです。
限定継続は、1988年にフェライゼンによって初めて導入されました[ 1 ] 。1987年の技術レポートで初めて紹介された[ 2 ] 、プロンプト構造とともにこの演算子は、Schemecall/cc、ISWIMのJ演算子、John C. Reynoldsの演算子など、文献で説明されている制御演算子の一般化として設計されました。その後、プログラミング言語の研究コミュニティによって、や、[ 4 ]や、[ 5 ] 、 [ 6 ]、[ 7 ]など、競合する多くの区切り制御演算子が考案されました。escapepromptcontrolshiftresetcuptofcontrol
研究文献では、限定継続のためのさまざまな演算子が提案されている。[ 8 ]
独立した提案の 1 つ[ 5 ]は、継続渡しスタイル(CPS)に基づいており、つまり継続フレームに基づいておらず、動的な限定継続ではなく静的な限定継続を生み出す 2 つの制御演算子 と を提供します。shift[ 9 ]演算子 は継続の制限を設定し、演算子 は現在の継続を最も内側の囲み までキャプチャまたは具体化します。たとえば、Schemeの次のスニペットを考えてみましょう。resetresetshiftreset
( * 2 (リセット( + 1 (シフトk ( k 5 )))))は、(この例では と名付けられている)をキャプチャするreset継続を区切ります。このスニペットが実行されると、 の使用は、 が値で埋められる計算部分を表す継続にバインドされます。この継続は、 から までの を囲むコードに直接対応します。シフトの本体 (つまり、) がすぐに継続を呼び出すため、このコードは次のコードと同等です。shiftkshiftk(+ 1 [])[]shiftreset(k 5)
( * 2 ( + 1 5 ))一般的に、これらの演算子は、例えば、キャプチャされた継続をk値として返したり、k複数回呼び出したりすることで、より興味深い動作をエンコードできます。shift演算子は、キャプチャされた継続をk本体内のコードに渡します。本体内のコードは、継続を呼び出すか、結果として生成するか、完全に無視することができます。がshift生成する結果は、最も内側のに提供され、とreset間の継続は破棄されます。ただし、継続が呼び出された場合、に戻ると、継続が実質的に再インストールされます。内の計算全体が完了すると、結果は区切り継続によって返されます。[ 10 ]例えば、このSchemeコードでは、次のようになります。resetshiftresetreset
(リセット( * 2 (シフトkコード)))CODEが呼び出されるたびに(k N)、(* 2 N)が評価され返されます。
これは以下と同等です。
( let (( k ( lambda ( x ) ( * 2 x ))))コード)さらに、内部の計算全体shiftが完了すると、継続は破棄され、外部で実行が再開されますreset。したがって、
(リセット( * 2 (シフトk ( k ( k4 ) ))))まずが呼び出され(k 4)（8 が返される）、次に が呼び出されます(k 8)（16 が返される）。この時点でshift式は終了し、reset式の残りの部分は破棄されます。したがって、最終結果は 16 です。
式の外側で起こることはすべてreset隠蔽され、つまり制御の移譲の影響を受けません。たとえば、これは 17 を返します。
( + 1 (リセット( * 2 (シフトk ( k ( k 4 ))))))限定継続は、Felleisenら[ 2 ]と Johnson [ 11 ]によって独立に初めて記述されました。それ以来、特に新しい制御演算子を定義する際に、多くの分野で使用されています。概説についてはQueinnec [ 12 ]を参照してください。
より複雑な例を見てみましょう。null空のリストを とします。
(リセット(開始(シフトk ( cons 1 ( k ( void )))) ;; (1) null ))によって取得されるコンテキストはshiftであり(begin [*] null)、は のパラメータが挿入される[*]穴です。内のの最初の呼び出しは、このコンテキストに対して評価され、穴は=に置き換えられるため、 の値は=となります。 の本体、つまり=は、最終結果として式の全体の値になります。kkshift(void)#<void>(k (void))(begin #<void> null)nullshift(cons 1 null)(1)reset
この例をさらに複雑にするために、次の行を追加してください。
(リセット(開始(シフトk ( cons 1 ( k ( void )))) (シフトk ( cons 2 ( k ( void )))) null ))最初の部分をコメントアウトするとshift、結果は既にわかっているので、(2)式を次のように書き換えることもできます。
(リセット(開始(シフトk ( cons 1 ( k ( void )))) (リスト2 )))これはよく知られており、 と書き換えることができます。(cons 1 (list 2))つまり、 です。(list 1 2)
yieldこの方法を使えば定義できます。
(define (yield x) (shift k (cons x (k (void)))))
リスト作成に活用する：
(リセット(開始( yield 1 ) ( yield 2 ) ( yield 3 ) null )) ;; (リスト 1 2 3)consを に置き換えるとstream-cons、遅延ストリームを構築できます。
( define ( stream-yield x ) ( shift k ( stream-cons x ( k ( void )))))( define lazy-example ( reset ( begin ( stream-yield 1 ) ( stream-yield 2 ) ( stream-yield 3 ) stream-null )))これを一般化して、リストをストリームに一気に変換することもできます。
( define ( list->stream xs ) ( reset ( begin ( for-each stream-yield xs ) stream-null )))以下のより複雑な例では、継続をラムダ式の本体に安全にラップして、そのように使用することができます。
( define ( for-each->stream-maker for-each ) ( lambda ( collection ) ( reset ( begin ( for-each ( lambda ( element ) ( shift k ( stream-cons element ( k 'ignored )))) collection ) stream-null ))))と の間の部分にはreset、やshiftのような制御関数が含まれています。これはラムダ式を使って言い換えることはできません。lambdafor-each
限定継続は言語学においても有用である。詳細は「言語学における継続」を参照のこと。
(shift k k)：一般化されたカリー関数一般化カリー関数は、カリー化されていない関数fとその引数の数（例えば3）を与えられ、その値を返します。この例はオリヴィエ・ダンヴィ(lambda (v1) (lambda (v2) (lambda (v3) (f v1 v2 v3))))によるもので、1980年代半ばに考案されました。[ 13 ]
以下に、汎用カリー関数がどのような動作をすることが期待されるかを示す単体テスト関数を示します。
( define test-curry ( lambda ( candidate ) ( and ( = ( candidate + 0 ) ( + )) ( = (( candidate + 1 ) 1 ) ( + 1 )) ( = ((( candidate + 2 ) 1 ) 10 ) ( + 1 10 )) ( = (((( candidate + 3 ) 1 ) 10 ) 100 ) ( + 1 10 100 ))) ( = ((((( candidate + 4 ) 1 ) 10 ) 100 ) 1000 ) ( + 1 10 100 1000 ))))これらの単体テストでは、可変引数関数をn 項のカリー化関数にカリー化し、その結果を n 個の引数に適用した場合、n = 0、1、2、3、4 の場合に、これらの n 個の引数に適用した場合と同じ結果が得られるかどうかを検証します。++
以下の再帰関数はアキュムレータベースであり、最終的にアキュムレータを反転させてから、与えられた非カリー化関数を適用します。帰納ステップの各インスタンスにおいて、関数は(lambda (v) ...)カリー化アプリケーションの引数に明示的に適用されます。
( define curry_a ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_a "negative input: ~s" n ) ( letrec ([ visit ( lambda ( i a ) ( if ( = i 0 ) ( apply f ( reverse a )) ( lambda ( v ) ( visit ( - i 1 ) ( cons v a )))))]) ( visit n ' ())))))例えば、評価する
((( curry_a + 2 ) 1 ) 10 )評価に帰着する
(((訪問2 ' ()) 1 ) 10 )これは評価に帰着する
((( lambda ( v ) ( visit 1 ( cons v ' ()))) 1 ) 10 )これはベータ還元して評価する
((訪問1 ( cons 1 ' ())) 10 )これは評価に帰着する
(( lambda ( v ) ( visit 0 ( cons v ( cons 1 ' ())))) 10 )これはベータ還元して評価する
(訪問0 ( cons10 ( cons1 ' ( ) )))これは評価に帰着する
(適用+ (逆( cons 10 ( cons 1 ' ()))))これは評価に帰着する
(適用+ ( cons 1 ( cons 10 ' ())))これは以下と同等です
( + 1 10 )これはデルタ還元すると、次の結果になります11。
以下の再帰関数は継続ベースであり、リストの反転は行いません。同様に、帰納ステップの各インスタンスにおいて、関数は(lambda (v) ...)カリー化された適用において引数に明示的に適用されます。
( define curry_c ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_c "negative input: ~s" n ) ( letrec ([ visit ( lambda ( i c ) ( if ( = i 0 ) ( c ' ()) ( lambda ( v ) ( visit ( - i 1 ) ( lambda ( vs ) ( c ( cons v vs )))))))]) ( visit n ( lambda ( vs ) ( apply f vs )))))))評価すると
((( curry_c + 2 ) 1 ) 10 )評価に帰着する
((( visit 2 ( lambda ( vs ) ( apply + vs ))) 1 ) 10 )これは評価に帰着する
((( lambda ( v ) ( visit 1 ( lambda ( vs ) (( lambda ( vs ) ( apply + vs )) ( cons v vs ))))) 1 ) 10 )これはベータ還元して評価する
(( visit 1 ( lambda ( vs ) (( lambda ( vs ) ( apply + vs )) ( cons 1 vs )))) 10 )これは評価に帰着する
(( lambda ( v ) ( visit 0 ( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( apply + vs )) ( cons 1 vs ))) ( cons v vs ))))) 10 )これはベータ還元して評価する
( visit 0 ( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( apply + vs )) ( cons 1 vs ))) ( cons 10 vs ))))これは評価に帰着する
((ラムダ( vs ) ((ラムダ( vs ) ((ラムダ( vs ) ( apply + vs )) ( cons 1 vs ))) ( cons 10 vs ))) ' ())これはベータ還元して評価する
((ラムダ( vs ) ((ラムダ( vs ) ( apply + vs )) ( cons 1 vs ))) ( cons 10 ' ()))これはベータ還元して評価する
((ラムダ( vs ) ( apply + vs )) ( cons 1 ( cons 10 ' ())))これはベータ還元して評価する
(適用+ ( cons 1 ( cons 10 ' ())))これは以下と同等です
( + 1 10 )これはデルタ還元すると、次の結果になります11。
次の再帰関数 はcurry_dの直接スタイル対応であり、Andrzej Filinski によるグローバル可変セルと の観点からのシフトとリセットの実装を使用して、 のイディオムcurry_cを特徴としています。[ 14 ] 誘導ステップの各インスタンスでは、継続の抽象化がカリー化されたアプリケーションの引数に暗黙的に適用されます。(shift k k)call/cc
( define curry_d ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_d "negative input: ~s" n ) ( letrec ([ visit ( lambda ( i ) ( if ( = i 0 ) ' () ( cons ( shift k k ) ( visit ( - i 1 )))))]) ( reset ( apply f ( visit n )))))))問題の核心は、ととの間の観測的等価性であり (reset (... (shift k k) ...)) 、 (lambda (x) (reset (... x ...))) ここでx、は新鮮なものであり、楕円は純粋なコンテキスト、つまり制御効果のないコンテキストを表します。
評価すると
((( curry_d + 2 ) 1 ) 10 )評価に帰着する
(((リセット(適用+ (訪問2 ))) 1 ) 10 )これは評価に帰着する
(((リセット(適用+ ( cons (シフトkk ) (訪問1 )) ) ) 1 ) 10 )これは観測上同等である
((( lambda ( x ) ( reset ( apply + ( cons x ( visit 1 ))))) 1 ) 10 )これはベータ還元して評価する
((リセット(適用+ ( cons 1 (訪問1 )))) 10 )これは評価に帰着する
((リセット(適用+ ( cons 1 ( cons ( shift k k ) ( visit 0 ))))) 10 )これは観測上同等である
(( lambda ( x ) ( reset ( apply + ( cons 1 ( cons x ( visit 0 )))))) 10 )これはベータ還元して評価する
(リセット(適用+ ( cons 1 ( cons 10 ( visit 0 )))))これは評価に帰着する
(リセット(適用+ ( cons 1 ( cons 10 ' ()))))これは以下と同等です
(リセット( +110 ) )これはデルタ還元して評価する
（リセット11 ）これにより、次の結果が得られます11。
の定義は、静的な区切り継続も示しています。 およびcurry_dを使用する場合は、この静的範囲を明示的にエンコードする必要があります。[ 15 ]controlprompt
( define curry_cp ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_cp "negative input: ~s" n ) ( letrec ([ visit ( lambda ( i ) ( if ( = i 0 ) ' () ( cons ( control k ( lambda ( x ) ( prompt ( k x )))) ( visit ( - i 1 )))))]) ( prompt ( apply f ( visit n )))))))racket/control Racketライブラリ;以下の例はRacketで実行できます(require racket/control)