継続渡しスタイルの中間値と戻り値

Question

私はOOPの機能していないバックグラウンドから来ているので、continuation passingに関するいくつかのオンラインの例を完全に視覚化することに問題があります。また、Schemeのような関数型言語は、引数の型や戻り値の型を指定する必要がないので、私が正しく考えているかどうかは不明です。

C＃が、私は、パターンを適用する方法を確認するために、Wikipediaの記事からの最初の例を取っ​​て、強い型付けでのC＃に移植することを試みたが、ラムダをサポートしているため：

// (Scheme) 

// direct function 
(define (pyth x y) 
(sqrt (+ (* x x) (* y y)))) 

// rewriten with CPS 
(define (pyth& x y k) 
(*& x x (lambda (x2) 
      (*& y y (lambda (y2) 
        (+& x2 y2 (lambda (x2py2) 
           (sqrt& x2py2 k)))))))) 

// where *&, +& and sqrt& are defined to 
// calculate *, + and sqrt respectively and pass the result to k 
(define (*& x y k) 
(k (* x y))) 

をので、書き換えC＃でのCPS pyth&バージョンがもたらした：

// (C#6) 

// continuation function signature 
delegate double Cont(double a); 

// *&, +& and sqrt& functions 
static double MulCont(double a, double b, Cont k) => k(a * b); 
static double AddCont(double a, double b, Cont k) => k(a + b); 
static double SqrtCont(double a, Cont k) => k(Math.Sqrt(a)); 

// sqrt(x*x + y*y), cps style 
static double PythCont(double x, double y, Cont k) => 
    MulCont(x, x, x2 => 
     MulCont(y, y, y2 => 
      AddCont(x2, y2, x2py2 => 
       SqrtCont(x2py2, k)))); 

私が代わりにdoubleのジェネリック医薬品を使用することもできますが、署名はbのでしょうe長く。とにかく、私はわからないことです：

1. が正しい（すなわちFunc<double, double>）上記Cont署名ですか？ fnが続くべきか？パラメータを受け入れて処理し、同じ型の値を返しますか？

2. 私が最初にコンティニューについて読み始めたとき、このコンティニュアス機能がコールスタックの各ステップで呼び出されると感じましたが、上の例ではsqrt&にしか渡されず、他のコールはすべてラムダを取得します。実際に中間の値を元の継続に「渡す」必要はありません。上記の関数の上のコードは、基本的にはk(Math.Sqrt(x * x + y * y))に類似しているので、中間の「フック」についての私の前提が間違っていますか？

Answer 1

1. あなたが最も外側の継続と非数値何かをする場合を除きはい、それは正しいです。 オリジナルの表現にもっと多くのタイプが含まれている場合、より多くの「Cont」が必要になります。 （私は簡潔にするための方式で書き込み申し訳ありません）

その場合には、次のようになります

（（= X 0）1 0）の場合は（）（FOO xを定義する）：

(define (foo& x k) 
    (=& x 0 (lambda (r1) 
      (if r1 (k 1) (k 0))))) 

- 一番外側の連続は数値（intと言う）を入力とし、 "= &"はbool-> int型です。

2. ほとんどの場合（二重性まで）、コールスタックの各ステップがいくつかの継続を呼び出すようになりました。 一般的には、cpsと第1クラスの継続を混同することがあります。前者は言語機能であり（call/cc演算子で現在の継続をアクセスできるスキームのように）、後者はどこでも使用できる手法です。 実際には、あなたの言語で高次関数を使用しなくても式をcpsに変換することができます。

もう1つの質問は、cpsが制御フローにどのように関係しているかということです。さて、あなたが指定した唯一のことは、適用可能な関数型言語（スキームのようなもの）では、アプリケーションの場合、まずオペランドと演算子を評価し、後者を前者に適用することに注意してください。どのような順序でオペランドを評価するかは重要ではありません。左から右、右から左、または多分狂った方法で行うことができます。しかし、純粋に機能的なスタイルを使用せず、オペランドがいくつかの副作用を引き起こす場合はどうなりますか？例えば、何かを標準出力に出力し、後である値を返します。その場合、注文を管理したいと考えています。 私はよく覚えている場合は、左から右への策略のインタプリタで解釈しながら、策略-Cでコンパイルされたプログラムは、右から左への引数を評価する - ので、問題が実際に存在する;）。そして正確にはcpsがあなたを救うかもしれません[実際には他の手段もありますが、今はcpsについてです！]。 投稿したスキームの例では、 "+"の引数が左から右に評価されることが強制されています。 これを簡単に変更することができます：

(define (pyth& x y k) 
(*& y y (lambda (y2) 
      (*& x x (lambda (x2) 
        (+& x2 y2 (lambda (x2py2) 
           (sqrt& x2py2 k)))))))) 

これは問題です。

コメントの中で既に述べたように、CPSへの変換はすべてのアプリケーションを末尾に移動させるので、コールスタックはlambdasに置き換えられ、さらにそれらの機能を無効にすると、制御フローを表すデータ構造 - 例えばCなどに変換されるきれいな形式または他の命令的言語。完全にautomagicaly！ それとも、あなたには、いくつかのモナドのマンボジャンボを実装したい場合は、たぶんモナドを言う、CPSにそれは簡単です、ちょうど各継続ラムダに受け取った値が「ちょうど何か」であるかどうかのテストを先頭に追加（場合仕事をして結果をあなたの継続にプッシュする）、または "何もない"場合は、Nothingを（継続 - ラムダに）押し込むだけです。別のプログラムまたはマクロによってではなく、手ではなく、もちろん 、それは退屈かもしれないとして - CPSをbehingほとんどの魔法が、それは、CPSに変換を自動化するので、簡単だということです。私はそれが不必要に複雑にしていなかった

希望。