9

ラムダ計算やOcamlのようなカレー言語のCPSはどのように意味がありますか？技術的には、すべての関数に1つの引数があります。したがって、そのような言語の1つにCPSバージョンの加算があるとします。

cps-add k n m = k ((+) n m)

そして、私たちはそれを次のように呼びます

(cps-add random-continuation 1 2)

これは、次と同じです。

(((cps-add random-continuation) 1) 2)

末尾呼び出しではなく、実際には複雑にネストされた式である2つの呼び出しがすでに表示されてい(cps-add random-continuation)ます。値、つまり数値を消費する関数を返し、次に別の数値を消費して両方の合計をに返す関数を返します。そのrandom-continuation。ただし、各関数に引数を1つしか与えることができないため、これをCPSに再度変換するだけでは、この値の戻りを回避することはできません。継続と「実際の」議論のための余地を作るために、少なくとも2つ必要です。

それとも私は何かを完全に見逃していますか？

4

3 に答える 3

10

これに Haskell のタグを付けたので、その点についてお答えします。Haskell では、CPS 変換を行うのと同等のことがContモナドで機能しています。モナドは、値xを 1 つの引数を取り、それを適用する高階関数に変換します。にx。

まず、これが通常の Haskell の 1 + 2 です:(1 + 2)そして、これは継続モナドにあります:

contAdd x y = do x' <- x
                 y' <- y
                 return $ x' + y'

...あまり参考になりません。何が起こっているのかを見るために、モナドを逆アセンブルしてみましょう。まず、do表記を削除します。

contAdd x y = x >>= (\x' -> y >>= (\y' -> return $ x' + y'))

return関数は値をモナドに持ち上げます。この場合、 として実装されるか\x k -> k x、中置演算子セクションを として使用し\x -> ($ x)ます。

contAdd x y = x >>= (\x' -> y >>= (\y' -> ($ x' + y')))

演算子 ( 「(>>=)バインド」と読む) は、モナド内の計算を連鎖させ、この場合は として実装され\m f k -> m (\x -> f x k)ます。バインド関数をプレフィックス形式に変更し、ラムダに置き換え、さらにわかりやすくするために名前を変更します。

contAdd x y = (\m1 f1 k1 -> m1 (\a1 -> f1 a1 k1)) x (\x' -> (\m2 f2 k2 -> m2 (\a2 -> f2 a2 k2)) y (\y' -> ($ x' + y')))

一部の関数適用を減らす:

contAdd x y = (\k1 -> x (\a1 -> (\x' -> (\k2 -> y (\a2 -> (\y' -> ($ x' + y')) a2 k2))) a1 k1))

contAdd x y = (\k1 -> x (\a1 -> y (\a2 -> ($ a1 + a2) k1)))

そして、最後の再配置と名前変更のビット:

contAdd x y = \k -> x (\x' -> y (\y' -> k $ x' + y'))

つまり、関数の引数は数値から、期待どおり、数値を取り、式全体の最終結果を返す関数に変更されました。

編集contAdd：コメント者は、それ自体がカリー化されたスタイルでまだ2つの引数を取ることを指摘しています. 継続を直接使用しないため、これは理にかなっていますが、必須ではありません。それ以外の場合は、最初に関数を引数間で分割する必要があります。

contAdd x = x >>= (\x' -> return (\y -> y >>= (\y' -> return $ x' + y')))

そして、次のように使用します。

foo = do f <- contAdd (return 1)
         r <- f (return 2)
         return r

これは実際には以前のバージョンと変わらないことに注意してください。最終結果だけでなく、各部分適用の結果を継続としてパッケージ化するだけです。関数は第一級の値であるため、数値を保持する CPS 式と関数を保持する CPS 式の間に大きな違いはありません。

ここでは、何かが継続渡しスタイルである場合のすべてのステップを明示するために、非常に冗長な方法で物事を書いていることに注意してください。

補遺: 最終的な式が、単項式の糖分を取り除いたバージョンと非常によく似ていることに気付くかもしれません。これは偶然ではありません。以前の値に基づいて計算の構造を変更できるようにするモナド式の内側への入れ子の性質は、継続渡しスタイルと密接に関連しているからです。どちらの場合も、ある意味で因果関係の概念を具現化しています。

于 2010-12-22T18:06:56.857 に答える
2

簡単な答え：もちろん、それは理にかなっています。CPS変換を直接適用できます。お気づきのように、各引数には独自の継続が付加されるため、多くの問題が発生するだけです。

あなたの例では、カレーの+(x,y)ないプリミティブがあり、あなたは

let add x y = +(x,y)

（これaddはOCamlの(+)演算子を忠実に表しています）

add構文的には同等です

let add = fun x -> (fun y -> +(x, y))

したがって、CPS変換¹を適用して

let add_cps = fun x kx -> kx (fun y ky -> ky +(x,y))

自発的に記述できるものに似た翻訳コードが必要な場合は、既知のアリティ関数を非カレー関数と実際に見なし、すべてのパラメーターを全体として処理する、より細かい変換を考案できます（非カリー関数の場合と同様）。カレー言語、および機能コンパイラーが明らかにパフォーマンス上の理由ですでに行っているように）。

¹： 「1つの真のCPS変換」がないため、「CPS変換」を作成しました。さまざまな翻訳が考案されており、多かれ少なかれ継続関連のゴミが発生しています。正式なCPS変換は通常、ラムダ計算で直接定義されるため、正式ではなく、より手作りのCPS変換を念頭に置いていると思います。

CPSの優れた特性（プログラムが尊重するスタイルとしてであり、このスタイルへの特定の変換ではありません）は、評価の順序が完全に明示的であり、すべての呼び出しが末尾呼び出しであることです。あなたがそれらを尊重する限り、あなたはあなたができることにおいて比較的自由です。したがって、カレー化された機能を具体的に処理することはまったく問題ありません。

備考：(cps-add k 1 2)コンパイラがcps-addが実際には常に3つの引数を取り、中間クロージャを構築しないことを検出して最適化すると仮定した場合、バージョンは末尾再帰と見なすこともできます。それはとてつもないように思えるかもしれませんが、CPS以外のプログラムで、それらの言語で末尾呼び出しについて推論するときに使用するのとまったく同じ仮定です。

于 2010-12-22T17:43:11.530 に答える
0

はい、技術的にはすべての関数を1つのメソッドで関数に分解できますが、CPSを使用する場合は、計算の特定の時点で継続メソッドを実行するだけです。

あなたの例を使って、見てみましょう。少し簡単にするために、cps-addを通常の形式に分解してみましょう。ここでは、引数を1つだけ取る関数です。

（cps-kを追加）-> n-> m = k（（+）nm）

この時点で、継続kは評価されていないことに注意してください（これが混乱のポイントになる可能性がありますか？）。

ここに、cps-add kというメソッドがあります。このメソッドは、関数を引数として受け取り、別の引数nを受け取る関数を返します。

（（cps-add k）n）-> m = k（（+）nm）

これで、引数mをとる関数ができました。

ですから、私が指摘しようとしているのは、カリー化がCPSスタイルのプログラミングの邪魔にならないということだと思います。それが何らかの形で役立つことを願っています。

于 2010-12-22T17:00:01.127 に答える