問題タブ [continuation-passing]

• 固定小数点コンビネータは、再帰を導入するための非常に便利なツールです。
• Continuation-Passing スタイルは、関数が決して返らないラムダ計算のスタイルです。代わりに、プログラムの残りの部分をラムダ引数として関数に渡し、それらを続行します。これにより、実行フローをより適切に制御し、さまざまなフロー変更構造 (ループ、コルーチンなど) をより簡単に定義できます。

しかし、ひとつひとつを表現できるかどうかは疑問です。私が見たすべての CPS スタイルの言語には、FIX再帰を定義するための明示的な構造があります。

• なしでは、プレーンな CPS で固定小数点コンビネータ (または類似のもの) を定義できないためFIXですか? もしそうなら、あなたはそのようなことの証拠を知っていますか?
• それともタイピングの問題だけですか？
• それとも可能かもしれませんが、何らかの理由で非現実的ですか？
• それとも、そこにある解決策が見つからなかっただけですか...？

Y コンビネータのような CPS 関数が次のように機能することを期待しCPSYます。Y 対応の CPS 関数を定義すると、次のようになります。

次に、それを入れて、CPSYそれ自体に再帰する関数を生成します。

はCPSY、再帰に依存しない単純な継続渡しスタイルの関数である必要があります。Y コンビネータは、組み込みの再帰を使用せずに、単純なラムダ計算でこのような方法で定義できます。なんらかの形で CPS にも存在できますか?

明確にするために繰り返します：私はコンビネータのような関数CPSYを探しています：

• CPS 関数の再帰を有効にします
• it の定義は再帰に依存しません
• it の定義は、継続渡しスタイルで与えられます (の本体内のどこにもラムダを返しませんCPSY) 。

継続渡しスタイル (CPS) モナドのモナド法則 (左右のユニット + 結合性) を証明しようとしています。

https://coq.inria.fr/cocorico/AUGER_Monadの型クラス ベースの Monad 定義を使用しています。

CPS 型コンストラクターは Ralf Hinze のFunctional Pearl about Compile-time parsing in Haskellからのものです

私はこれを定義bindしてreturn_好きです

しかし、私は と の証明義務に固執していright_unitますassociativity。

の義務を与えるright_unit：

助けてくれてとても感謝しています！

intros; apply eq_refl.編集: András Kovács は、型チェッカーでの eta 変換で十分であると指摘しましたreflexivity.。

まず、 の誤った定義を修正する必要がありbindました。（目に見えない議論cは間違った側にありました)...

継続渡しスタイルのチュートリアルを見ていますが、次の関数の型がわかりません。

上記は以下の改造です。

Atom エディターによって提供される型情報を見るとs :: (a -> r) -> r、 、f :: a -> (b -> r) -> r、k :: b -> r. さらにzはxタイプx :: aです。

これについて私が混乱しているのは、それzが type であることですz :: a -> r。

つまり、 に適用した後s zの型である必要があります。rzs

もしそうなら、最終的な型はどのように出てき(b -> r) -> rますか?

編集：b -> rから来kます...右。編集者が言うように、それはz本当に が typeであることを意味します。a -> rしかし、なぜ次の型チェックが失敗するのでしょうか?

継続渡しスタイルに関するいくつかのブログ記事/ウィキペディアを表面的に読んだことがあります。私の高レベルの目標は、再帰関数を末尾再帰にするための体系的な手法を見つけることです (または、制限がある場合は、それらを認識して)。しかし、私は自分の考えを明確にするのに苦労しており、私の試みが意味を成すかどうかはわかりません.

例として、簡単な問題を提案します。目標は、一意の文字の並べ替えられたリストを指定して、これらの文字から作成されたすべての可能な単語をアルファベット順に出力することです。たとえば、sol("op".toList, 3)を返す必要がありooo,oop,opo,opp,poo,pop,ppo,pppます。

私の再帰的な解決策は次のとおりです。

関数をパラメーターとして追加してこれを書き直そうとしましたが、末尾再帰であると確信できるものを作成することができませんでした。私は彼らの素朴さを恥じているので、私の試みを質問に含めたくないので、これを許してください.

したがって、質問は基本的に次のとおりです。上記の関数は CPS でどのように記述されますか?

私は OOP の非機能的なバックグラウンドを持っているため、継続渡しに関するいくつかのオンライン例を完全に視覚化するのに苦労しています。また、Scheme のような関数型言語では、引数の型や戻り値を指定する必要がないため、その考えが正しいかどうかはわかりません。

C# はラムダをサポートしているため、ウィキペディアの記事から最初の例を取り上げ、それを強い型付けで C# に移植して、パターンがどのように適用されるかを確認しました。

したがって、pyth&C# で CPS バージョンを書き直すと、次のようになりました。

の代わりにジェネリックを使用することもできdoubleましたが、シグネチャは長くなります。とにかく、よくわからないのは次のとおりです。

1. 上記のCont署名は正しいですか (つまりFunc<double, double>)? 継続すべき fn. パラメータを受け入れて処理し、同じ型の値を返しますか?

2. 最初に継続について読み始めたとき、この継続関数はコール スタックの各ステップで呼び出されるように感じましたが、上記の例では にのみ渡されsqrt&、他のすべての呼び出しは実際には「パスしないラムダ」を取得します。 " 元の継続の中間値。上記の関数の上記のコードは、基本的に に似てk(Math.Sqrt(x * x + y * y))います。これは、中間の「フック」に関する私の仮定が間違っていることを意味しますか?

効率化のために Attoparsecにいくつかの機能を入れようとしてVectorいますが、壁にぶつかりました。

Attoparsec が CPS を使用して書かれていなければ、機能的な unfoldrを使用できたかもしれませんが、それはここではオプションではありません。問題は、ここではすべての呼び出しが末尾の位置にある必要があり、標準的な意味で関数が返されないため、配列をアキュムレータとして渡す必要があることです。

STモナドを使ってこれをやろうとしましたが、それがうまくいかなかったときは上記を試しましたが、それでもうまくいきません。ここでは、Haskell の型システムに本当に悩まされています。CPSでプログラミングするときに可変配列を編集することはとにかく可能ですか?

STモナド内でこれを行うことが可能であれば、私はこれを二重に感謝します.

ただし、配列以外のデータ構造を使用するように指示する投稿には反対票が投じられます。

非常に典型的な使用例: オブジェクト (またはクラス) は、関連する型のいくつかの public val を宣言し、それらすべてを含むコレクションを返すアクセサーを宣言したいと考えています。

この例は明らかに DRY に違反しており、エラーが発生しやすくなっています。変更可能な状態を使用して非常に簡単に解決できます (暗黙のBuilder[Ball, Seq[Ball]]パラメーターをBallコンストラクターに追加するなど)。しかし、その解決策にも問題がないわけではありません。特に、解決策を一般化しようとしたり、すべてのクラスが宣言するクラス階層を作成しようとすると、一部の値では、変更可能な部分的な要約から最終的な不変の値に切り替えるタイミングが明確ではありません。

知的な練習として、そして好奇心から、私は純粋に機能的な変種を考え出そうとしましたが、あまり成功しませんでした. 私が思いついた最高のものは

これは非常に優れていますが、ボールまたはその初期化子の数が少なくなると、管理できなくなります。有効な代替手段は、すべてを HMap に変更することですが、私は通常、パブリック API で形状のない依存関係を回避しようとします。おそらくscalaの継続で実行できるように思えますが、リセットブロックに対して宣言を非ローカルにする方法がわかりません。

編集：私が以前に強調しなかったこと、およびscala.Enumeration私のために仕事をしない理由は、実際のケースではオブジェクトが同一ではなく、実際には複合構造であり、コンストラクターが数行以上かかることです. したがって、最終的な型は同じかもしれませんが (または少なくとも詳細には興味がありません)、単純な列挙ではなく、読みやすさの理由から、宣言されたメンバー/キーの名前を次のようにできることが重要です。その定義と視覚的に簡単に結びつけることができます。したがって、ここでの形状のないソリューションと、提案されている形状のない Seq ベースのソリューションは、実際の識別子を間違えて間違った値に変更が加えられる、オフバイワン エラーの影響を非常に受けやすくなっています。

もちろん、実際のケースは現在、継承されたコンストラクター メソッドによって生成された値のシーケンスを維持することにより、scala.Enumeration と同様に実装されています。ただし、列挙型が行うすべての問題があり、実際のobject Balls初期化子の外側でコンストラクターを呼び出したり、条件付きブロックの値を破棄したりすることによるエラーの可能性が増幅されます。その上、これが純粋関数型言語でどのように解決されるのか非常に興味がありました。

ケーキを持って食べる方法はありますか？