call/cc の実装方法を見つけようとしています。私が見つけた最高のものは、このHaskellスニペットです:
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k
これは私が望むほど単純ではありませんがContとrunCont. 実際のコードほど明確ではありませんが、それが何をするかの説明も見つけました。
では、最も単純な形で実装するにはどうすればよいでしょうか。これらは私が好む2つの言語であるため、これにSchemeとHaskellのタグを付けています。
「実装call/cc」は、作業しているレイヤーでは意味がありません。言語で実装できる場合call/cc、それは、少なくとも と同じくらい強力な組み込み構造があることを意味しcall/ccます。言語自体のレベルでは、call/cc基本的にプリミティブな制御フロー演算子であり、何らかの形の分岐が必要です。
もちろん、call/cc言語なしで言語を実装できます。これは、レベルが低いためです。言語の構造を特定の方法で翻訳し、この翻訳を調整して実装できるようにしますcall/cc。つまり、一般的に継続渡しスタイルです (ただし、C での移植性のない実装の場合は、スタックを直接コピーすることもできます。継続渡しスタイルについては後で詳しく説明します)。call/cc これは実際にはそれ自体に大きな洞察を与えるものではありません— 洞察は、それを可能にするモデルへの洞察です. その上、call/cc単なるラッパーです。
現在、Haskell は継続の概念を公開していません。それは参照透過性を壊し、可能な実装戦略を制限します。Contは、他のすべてのモナドと同様に Haskell で実装されており、リスト モナドが非決定性をモデル化するのと同様に、継続渡しスタイルを使用した継続を伴う言語のモデルと考えることができます。
callCC技術的には、 とのアプリケーションを削除するだけで、 の定義は型にContなりrunContます。しかし、それはモナドのコンテキストでどのように機能するかを理解するのに役立ちませんContので、代わりにその定義を見てみましょう. (この定義は、現在の Monad Transformer Library で使用されているものではありません。これは、その中のすべてのモナドがそれぞれのトランスフォーマー バージョンの上に構築されているためですが、スニペットのCont(古いバージョンでのみ機能する) の使用と一致します)、および物事を劇的に簡素化します。)
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
Cont r aわかりました。これで、値からこの関数を取得でき(a -> r) -> rます。十分に単純です。しかし、それはどういう意味ですか？runContCont r a
Cont r ar最終結果と結果を伴う継続渡し計算aです。最終結果 とはどういう意味ですか? runContそれでは、 out の型をより明示的に書きましょう。
runCont :: Cont r a -> (a -> r) -> r
ご覧のとおり、「最終結果」は最終的に得られる値runContです。では、どのように計算を構築できContますか? モナドインスタンスは啓発的です:
instance Monad (Cont r) where
return a = Cont (\k -> k a)
m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k))
まあ、それが何を意味するかをすでに知っているなら、それは啓発的です. 重要なことは、あなたが書いたときCont (\k -> ...)、 ,kは計算の残りの部分ですa— それはあなたがそれに value を与えることを期待していますr.戻り値の型も同じであるため、独自の戻り値r。うわー！そして、 でCont計算を実行するときは、最終結果を生成する計算の「最上位」であるrunCont最終を指定しているだけです。k
この「残りの計算」は何と呼ばれますか? 計算の続きだから続き！
(>>=)実際には非常に単純です。左側で計算を実行し、独自の残りの計算を与えます。この残りの計算は、値を にフィードするだけでf、独自の計算が生成されます。その計算を実行し、組み合わせたアクションが与えられた計算の残りの部分に入力します。このようにして、次のように計算をまとめることができますCont。
computeFirst >>= \a ->
computeSecond >>= \b ->
return (a + b)
または、より馴染みのあるdo表記法で:
do a <- computeFirst
b <- computeSecond
return (a + b)
その後、これらの計算を実行できますrunCont— ほとんどの場合、同じ結果と最終的な結果の型を持つrunCont foo ida をその結果に変換するようなもので問題なく動作します。foo
ここまでは順調ですね。それでは、物事を混乱させましょう。
wtf :: Cont String Int
wtf = Cont (\k -> "eek!")
aargh :: Cont String Int
aargh = do
a <- return 1
b <- wtf
c <- return 2
return (a + b + c)
何が起きてる？！最終結果と結果を使用しwtfたCont計算ですが、見えません。StringIntInt
aarghを実行するとどうなるでしょうか?runCont aargh showつまり、計算を実行し、showそのInt結果を a としてString最終結果を生成します。
"eek!"戻ります。
k「残りの計算」がどのようになったか覚えていますか? 私たちが行ったことwtfは、狡猾にそれを呼び出すのではなく、代わりに独自の最終結果を提供することです。
これは、継続ができる最初のことです。次のようなものは、1をCont (\k -> k 1 + k 2)返したかのように残りの計算を実行し、2 を返したかのように実行し、2 つの最終結果を加算します! 継続は基本的に、任意の複雑な非ローカル制御フローを表現することを可能にし、混乱を招くほど強力にします。実際、継続は非常に一般的であるため、ある意味では、すべてのモナドは の特殊なケースです。実際、一般的には、一種の継続渡しスタイルを使用していると考えることができます。Cont(>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
2 番目の引数は、最初の計算の結果を取得し、実行する残りの計算を返す継続です。
しかし、私はまだ質問に答えていません:それで何が起こっているのcallCCですか? さて、それは現在の継続であなたが与える関数を呼び出します。Contしかし、ちょっと待ってください。それは私たちがすでに行っていたことではありませんか? はい。ただし、タイプを比較してください。
Cont :: ((a -> r) -> r) -> Cont r a
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
は。おわかりのように、問題は、渡した関数内Contからアクションをシーケンスできないことです —純粋な方法で結果を生成しているだけです。継続がアクセスされ、受け渡され、通常は計算内からいじられます。私たちが持っているときrcallCC Cont
do a <- callCC (\cc -> ...)
foo ...
関数内の任意の値で呼び出して、それを計算自体ccの戻り値にすることができる関数であると想像できます。または、もちろん、通常どおりに値を返すこともできますが、最初に呼び出すのは少し無意味です:)callCC (\cc -> ...)callCC
bそこにある謎については、通常の制御フローをエスケープし、私が言ったように、それを全体の結果としてすぐに使用するため、 を使用して任意のタイプcc fooの計算を代用できるからです。したがって、実際に値を生成する必要がないため、必要な任意の型の値を返すことができます。こっそり！callCC (\cc -> ...)
これにより、実際の実装に進みます。
callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k)
まず、計算の残り全体を取得し、それを と呼びますk。しかし、このf (\a -> Cont (\_ -> k a))部分は何についてですか？fが type の値を取ることはわかっています。それ(a -> Cont r b)がラムダです — の結果として使用する値を取り、その継続を無視してその値を返すだけcallCC fの計算を返す関数です— 「残りの部分」の観点からの「計算の」。OK、その呼び出しの結果は別の計算であり、実行するには継続を提供する必要があります。同じ継続をもう一度渡すだけです。なぜなら、すべてが正常に行われた場合、計算が返すものを戻り値にして、通常どおり続行する必要があるからです。(実際、別の値を渡してもうまくいきません。ContkcallCC ffCont意味— 「あなたが実際に私を実行しているもの以外の継続で呼び出す」ではなく、「現在の継続で呼び出す」です。)
全体として、これが長い分、啓発的であると感じていただければ幸いです。継続は非常に強力ですが、それがどのように機能するかを直感的に理解するには多くの時間がかかる場合があります。(現在のmtlで動作させるContにはこれを呼び出す必要がありますcont) をいじって、制御フローの感触をつかむためにどのように結果を得るかを考えてみることをお勧めします。
継続に関する推奨されるさらなる読書:
call/cc実装するのは簡単です。難しいのは、実装可能な環境を整えることです。
最初に、継続渡しスタイル（CPS）の実行環境を定義する必要があります。この環境では、関数（または関数のようなもの）は直接値を返しません。代わりに、計算の「次のステップ」（「継続」）を表す関数が渡され、そこで結果が渡されます。Haskellでは、これは次のようになります。
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
ご覧のとおり、Contモナドアクションは実際には継続を取り、(a -> r)結果を継続に渡し、aの最終結果を返す関数ですr。これは単に呼び出し元に渡されます（つまり、Contモナドアクションは末尾呼び出しを行う必要があります）続き）。runContnewtypeラッパーからそれを取り出すだけです-のように、特定の継続を伴うアクションを呼び出すと考えることもできますrunCont someAction someContinuation。
次に、これをモナドに変えることができます。
instance Monad (Cont r) where
return x = Cont $ \cc -> cc x
(Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc)
ご覧のとおり、継続をreturn取得し、ccその値を継続に渡します。(>>=)少し注意が必要ですf。継続を使用して呼び出す必要があります。この継続は、を呼び出しg、アクションを取り戻し、外側の継続をこの新しいアクションに渡します。
したがって、このフレームワークを考えると、継続を取得するのは簡単です。継続して関数を2回呼び出したいだけです。トリッキーな部分は、既存の継続を破棄する新しいモナディックアクションでこの継続を再ラップする必要があることです。それでは、少し分解してみましょう。
-- Invoke a raw continuation with a given argument, throwing away our normal
-- continuation
gotoContinuation :: (a -> r) -> a -> Cont r x
gotoContinuation continuation argument = Cont $ \_ -> continuation argument
-- Duplicate the current continuation; wrap one up in an easy-to-use action, and
-- the other stays the normal continuation for f
callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc
シンプルですね
Schemeのような他の言語でも、原則は同じですが、コンパイラプリミティブとして実装される場合があります。Haskellでそれを実行できる理由は、継続渡しが、ランタイムの下位レベルではなく、Haskellで定義したものだったためです。ただし、原則は同じです。最初にCPSが必要であり、次にcall/ccこの実行モデルの簡単なアプリケーションです。
方程式の Haskell 側を聞いたことがあるでしょう。Racket/Scheme の 1 つを差し上げます。最も役立つ方を使用してください。
シンプルなラケット評価器で call/cc を実装するために提供できる最良の情報源は、Shriram Krishnamurthi のPLAI、特にセクション 20 にあると思うので、私の答えはもっと短くなります。インタプリタ -- 205 ページにあります -- しかし、何度か再フォーマットを試みた後、ページの適切な場所に配置した方がより意味があると判断しました。
繰り返しますが、ここでは call/cc の背後にある考え方を説明しようとしているわけではなく、実際に機能する実装を示しているだけです。他にご不明な点がありましたらお知らせください。
言語外になる危険性私は、Smalltalk では継続を実装し、最も簡単に理解できると思います。その理由は、Smalltalk では、実行スタックが、他のオブジェクトと同様にアクセスおよび操作できる通常のオブジェクトから形成されるためです。
単純な継続オブジェクトを実装するには、次の 2 つのメソッドが必要です。最初のメソッドでは、親 (送信側) フレーム (コンテキスト) を反復処理し、それらの状態 (プログラム カウンター、テンポラリー、引数) をコピーすることで、継続を初期化します。
Continuation>>initializeFromContext: aContext
context := aContext.
stream := WriteStream on: (Array new: 200).
[ context notNil ] whileTrue: [
stream nextPut: context.
1 to: context class instSize do: [ :index |
stream nextPut: (context instVarAt: index) ].
1 to: context size do: [ :index |
stream nextPut: (context at: index) ].
context := context sender ].
values := stream contents
2 番目の方法は、実行を再開することです。まず、現在のスタックを巻き戻し (これも実行スタックの単純なループです)、キャプチャしたスタック フレームを復元し、それらを現在のスタック フレームに再接続してthisContext、実行を再開します。引数anObject:
Continuation>>value: anObject
self terminate: thisContext.
stream := values readStream.
[ stream atEnd ] whileFalse: [
context := stream next.
1 to: context class instSize do: [ :index |
context instVarAt: index put: stream next ].
1 to: context size do: [ :index |
context at: index put: stream next ] ]
thisContext swapSender: values first.
^ anObject
これら 2 つの方法を使用すると、次のように簡単に構築できますcallCC。
Continuation class>>callCC: aBlock
^ aBlock value: (self new initializeFromContext: thisContext sender)
このアプローチの優れた点は、印刷されたコードが完全な継続 (および同様に他の種類の継続) を実装するために必要なすべてを示していることです。システム (VM) に隠された動作はありません。デバッガーを使用して各部分をステップ実行し、実行スタックがどのように操作されるかを観察できます。
上記のコードは、Seaside Web フレームワークからのものです。コードを操作するには、既製のディストリビューションを使用して、クラスWAContinuationとWAContinuationTest.
これには「スキーム」というタグも付けられているため、より短いスキームベースの回答を提供します。
実装の試みが失敗する理由を理解するには、継続渡しスタイルcall/ccとは何かを理解する必要があります。それを理解すれば、それは非常に簡単です。
call/cc直接スタイルでは実装できません。しかし、もう少し情報を与えるために、継続渡しスタイルは、すべてのプロシージャ呼び出しが「追加の」引数を渡す呼び出し規約を支持して、呼び出しスタックの使用を控えるフロー制御の規律です: 呼び出されたプロシージャが想定されているクロージャ「完了」したときに呼び出す (「戻り値」を引数として渡す)。これらの追加の引数クロージャーは継続と呼ばれます。
どのプログラムも、 CPS 変換と呼ばれるものによって、継続渡しスタイルに機械的に変換できます。実際、多くの Scheme システムはそのように機能します。プログラムが解析され、CPS 変換が適用され、CPS 抽象構文ツリーが解釈されるか、オブジェクト コードに変換されます。
call/ccこれは、継続渡しスタイルで実装する方法です(継続continuationの追加引数の名前として使用):
(define (call/cc-cps proc continuation)
(proc continuation continuation))
ご覧のとおり、(a) これを直接的なスタイル (CPS の反対) で実装することはできず、(b) CPS では簡単です。 call/ccは、引数と (必須の) 継続として別の手続きを取り、継続を引数と継続の両方としてその手続きを呼び出す手続きです。