問題タブ [continuation-passing]

ウィキペディアでは、 call/cc を使用すると、非決定論的な選択のために amb 演算子を実装できると書かれています。私の質問は、継続の唯一のサポートが継続渡しスタイルで記述することである言語で、amb 演算子をどのように実装するかです。アーラン？

CPSについて、この簡単なコードを実行しようとしました。これは Chrome 43 では機能しますが、Firefox と Opera では機能しません...何が問題なのですか? （だから Linux Mint 17 ）

ここ最近考えていた問題です。インターフェイスが、コピーにコストがかかり、移動にコストがかかるオブジェクトを返すメンバー関数であるとしましょう (std::string、std::vector など)。結果を計算して一時オブジェクトを返す実装もあれば、単にメンバー オブジェクトを返す実装もあります。

説明するサンプル コード:

さまざまな「クライアント」もあります。データを読み取るだけのものもあれば、所有権が必要なものもあります。

上記のコードは適切に構成されていますが、可能な限り効率的ではありません。すべての組み合わせは次のとおりです。

この状況を修正する良い方法は何ですか?

私は2つの方法を思いつきましたが、もっと良い解決策があると確信しています。

私の最初の試みでは、T の値または const T へのポインターのいずれかを保持する DelayedCopy ラッパーを作成しました。これは非常に見苦しく、余分な労力が必要であり、余分な移動が発生し、コピーの省略が妨げられ、おそらく他にも多くの問題があります。

2 番目に考えたのは、継続渡しスタイルです。これは非常にうまく機能しますが、メンバー関数をメンバー関数テンプレートに変換します。std::function があることは知っていますが、オーバーヘッドがあるため、パフォーマンスに関しては受け入れられない場合があります。

サンプルコード:

出力：

余分なコピーを回避する値を渡すためのより良い手法はありますか?

余談ですが、コードは C++11 の g++ 5.2 および clang 3.7 でコンパイルされています。C++14 および C++1z では、DelayedCopy はコンパイルされず、それが私のせいかどうかわかりません。

私はこの形式で計算をしています: s -> a -> s、ここでsは何らかの状態のタイプです。このような関数の結果は、次の評価の状態でもあります。例えば、

次に、appendInt "Int: " 1を与えますが"Int: 1"、 を(appendInt $ appendInt "Int: 1") 2与え"Int: 12"ます。Stateしかし、この種の計算をモナドに入れる方法が見つかりません。

最初の推測は ですがs -> (s,s)、次にa渡すことはできません。次に、 を試し(a -> s) -> (s, a -> s)ましたが、やはりsなしでは取得できませんa。出力ではなく入力であるs -> (a,s)ため、機能しません。a

では、この計算をどのようにラップすればよいでしょうか? モナドはStateこれに適していますか？

編集：私のこの質問は、非常に不適切であることが判明しました。特にコメントを読むと、考えの材料になるかもしれないと今でも信じていますが、それを閉じるのに十分な投票が得られれば、理解できます.

JavaScript で call/cc をエミュレートすることによってコール スタックをアンワインドする方法に関する非常に興味深い論文のいくつかの研究中に (継続とコールバックの違いは何ですか? ) 私は、主に使用される方法の根本的な改善と思われるものに直面しました。 JS 関数呼び出しを非同期にする。

最も一般的な方法はsetTimeout(fun, 0). funこの構成により、現在の実行スレッドから の呼び出しが取り出され、イベント キュー内の他のジョブが実行できるようになります。ただし、順番が来ると、funすべての状況でコール スタック全体を維持します。

しかし、上記の論文がそうであるように、コードが に変更され、継続渡しスタイル(記憶する命令がない) でsetTimeout.bind(null, fun, 0)プログラミングしている場合、 のコール スタックはクリアされ、深さ 1 に戻されます。returnfun

例でこれらすべての動作を確認できます。Chrome、FF、IE、Opera で検証済み。

サンプル HTML ページは、開発者ツールを開いた状態でダウンロードしてブラウザーで実行するのが非常に簡単です。行 18 と行 42 に 2 つの一時停止命令があり、ここで の 2 つの呼び出しによって維持されるコール スタックの違いを確認できますsetTimeout。

問題は、単純な呼び出しsetTimeout.bind()とは根本的に異なる振る舞いをするのはなぜですか? setTimeout誰かが何が起こっているのか説明できますか?

続きが面白い。特に興味深いのは、それらが他のすべてのモナドをどのように包含するかです。また、最適化にも多用されていると聞きます。それらが使用できると聞いていることの1つは、物事の制御の反転です。のように、gui のようなもの。これを使用するHaskellのライブラリの例があるかどうか疑問に思っています。

人気とか特に興味ないです。主に読書用に欲しいです。考慮すべき要素:

• 継続デリバティブではなく、直接継続: と同様の型に基づいている必要がありますnewtype Cont r a = Cont ((a -> r) -> r)。(コンビネータは問題ありませんが、単純な継続がそれにどのように適合するかは理解できるはずです。)
• 制御の反転に使用: 継続は多くの用途に使用されますが、私は主に GUI タイプのものや、制御の反転が物事を容易にする他の場所に興味があります。
• 普及: 継続は普及した制御構造であるべきです。
• よく書かれている: コードは読みやすく、学びやすいものでなければなりません。

(私がこれをやりたい理由は、関数のみに基づく継続が、非常に強力でありながら、非常に純粋な関数型プログラミングの概念であることがわかったからです。私が気に入っているこの 1 つのライブラリは、非常にストレートな関数型プログラミングであり、私は継続して拡張したいと考えています。)

注: ストレートな継続であることはあまり重要ではありません。制御の反転は、私が主に求めているものです。

課題の一部として、大きなグラフに Kosaraju のアルゴリズムを実装しようとしています [MOOC Algo I Stanford on Coursera]

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

現在のコードは小さなグラフで動作しますが、実行時にスタック オーバーフローが発生します。

Expert in F# の関連する章、または Web サイトや SO で利用可能な他の例を読んだにもかかわらず、この問題を解決するために継続を使用する方法がまだわかりません

以下は汎用の完全なコードですが、DFSLoop1 と再帰関数 DFSsub を内部で実行すると、既に失敗します。私は関数の末尾を再帰的にしていないと思います[命令のため

?]

しかし、継続を適切に実装する方法がわかりません。

失敗した部分だけを考えると、DFSLoop1 は深さ優先探索を適用するグラフを引数に取っています。2 番目の DFS ループ (DFSLoop2) でアルゴの 2 番目の部分に進むには、アルゴの一部として終了時刻を記録する必要があります [もちろん、その前に失敗しています]。

これは、単純なグラフの例を含むテキスト ファイルです。

(オーバーフローを引き起こしているのは、約 900,000 ノードで 70Mo の大きさです)

編集

最初にいくつかのことを明確にするために、これが「疑似コード」です

入力: 有向グラフ G = (V,E)、隣接リスト表現。頂点 V が 1、2、3、. . . 、n。1. すべてのアークの向きが逆になった後のグラフ G を Grev とします。2. Grev で DFS-Loop サブルーチンを実行し、与えられた順序に従って頂点を処理し、各頂点 v ∈ V の終了時刻 f(v) を取得します。3. G で DFS ループ サブルーチンを実行し、f(v) の降順に頂点を処理して、各頂点 v ∈ V にリーダーを割り当てます。4. G の強連結成分は、共通のリーダーを共有する G の頂点に対応します。 図 2 : SCC アルゴリズムのトップレベル。f 値とリーダーは、それぞれ DFS-Loop の 1 回目と 2 回目の呼び出しで計算されます (以下を参照)。

入力: 有向グラフ G = (V,E)、隣接リスト表現。1. グローバル変数 t を 0 に初期化します。[これにより、完全に探索された頂点の数が追跡されます。] 2. グローバル変数 s を NULL に初期化します。[これは、最後の DFS 呼び出しが呼び出された頂点を追跡します。] 3. i = n downto 1 の場合: [最初の呼び出しでは、頂点に 1、2、. . . 、 n 任意。2 番目の呼び出しでは、頂点は最初の呼び出しの f(v) 値によってラベル付けされます。] (a) i がまだ探索されていない場合: i. s := i を設定 ii. DFS(G, i) 図 3 : DFS-Loop サブルーチン。

入力: 隣接リスト表現の有向グラフ G = (V,E)、およびソース頂点 i ∈ V 。1. i を探索済みとしてマークします。[DFS-Loop 呼び出しの全期間にわたって探索されたままです。] 2. Leader(i) := s を設定します。 3. 各アーク (i, j) ∈ G について: (a) j がまだ探索されていない場合: i. DFS(G, j) 4. t + + 5. f(i) := t を設定 図 4 : DFS サブルーチン。f 値は、DFS-Loop への最初の呼び出し中にのみ計算する必要があり、リーダー値は、DFS-Loop への 2 回目の呼び出し中にのみ計算する必要があります。

EDIT 経験豊富なプログラマー (リスパーだが F# の経験がない) の助けを借りてコードを修正し、最初の部分をいくらか単純化して、この議論に関係のないコードを気にすることなく、より迅速に例を示しました。

コードはアルゴの半分のみに焦点を当てており、DFS を 1 回実行して逆ツリーの終了時刻を取得します。

これは、小さな例を作成するためのコードの最初の部分です。y は元の木です。タプルの最初の要素は親で、2 番目の要素は子です。しかし、逆ツリーで作業します

したがって、基本的にグラフは (1->2->3->1)::(4->5->6->7->8->....->99999->10000) と逆のグラフですは (1->3->2->1)::(10000->9999->....->4)

ここに直接スタイルで書かれたメインコードがあります

末尾再帰ではないため、継続を使用します。これは、CPS スタイルに適応した同じコードです。

両方のコードがコンパイルされ、小さな例 (コメントのもの) または使用している同じツリーで同じ結果が得られますが、サイズは小さくなります (100000 ではなく 1000)。

ここのアルゴリズムのバグではないと思います。同じツリー構造を持っていますが、大きなツリーが問題を引き起こしているだけです。続きがよく書かれているように見えます。コードを明示的に入力しました。そして、すべての呼び出しは、すべての場合に継続で終了します...

専門家のアドバイスをお待ちしています!!! ありがとう ！！！

私は、Scheme で単純なプログラミング言語のインタープリターを作成しようとしています。現在、break ステートメントを使用して while ループを処理する手順を作成しています。この問題に対処するために、call/cc を使用しています。

言語を解析すると、次のようになります。

になる

これらのステートメントを解釈するための私のアプローチは次のとおりです。

Where (M_State statement state) は、ステートメントを反映するように更新された現在の状態を返します (たとえば、状態 ((x) (2)) は x = 2 を表します。(M_State '(var x 5) '((x) (2))) は、 return ((x) (5)).)

これをデバッガーに通すと、body_line が null でなくても、行 ((null? body_line) (second-break-cont state)) は常に second-break-cont を呼び出します。これをデバッグするのに多くの時間を費やしましたが、エラーが見つからないようです。私の間違いを見つけるための助けをいただければ幸いです。

• 固定小数点コンビネータは、再帰を導入するための非常に便利なツールです。
• 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は間違った側にありました)...