2

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

C# はラムダをサポートしているため、ウィキペディアの記事から最初の例を取り上げ、それを強い型付けで 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)))

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

// (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ましたが、シグネチャは長くなります。とにかく、よくわからないのは次のとおりです。

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

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

4

2 に答える 2

4

  1. はい、最も外側の継続で数値以外のことをしたいのでない限り、それは正しいです。元の式がより多くの型を含む場合にのみ、より多くの「Cont」が必要になります。

    (定義 (foo x) (if (= x 0) 1 0))

その場合、次のようになります（簡潔にするためにスキームで書いてすみません）：

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

-- 現在、最も外側の継続は入力として数値 (int としましょう) を持ち、"=&" に提供されるものは bool->int 型を持ちます。

  1. あなたはほぼ正しいです（双対性まで）-コールスタックの各ステップは、何らかの継続への呼び出しになりました。一般に、ファーストクラスの継続と cps を混同している可能性があります。前者は言語機能 (call/cc 演算子を使用して現在の継続にアクセスできるスキームのように) であり、後者はどこでも使用できる手法です。実際には、言語に高階関数がなくても (何らかの形で表現するだけで) 式を cps に変換できます。

あなたが尋ねたもう1つのことは、cpsが制御フローにどのように関係しているかです。さて、適用可能な関数型言語 (スキームなど) で指定した唯一のことは、適用の場合、最初にオペランドと演算子を評価し、後者を前者に適用することだけであることに注意してください。オペランドをどの順序で評価するかは問題ではありません。左から右、右から左 [または、おかしな方法で] 行うこともできます。しかし、純粋に関数型のスタイルを使用しておらず、オペランドが何らかの副作用を引き起こしている場合はどうでしょうか? たとえば、何かを stdout に出力し、後で何らかの値を返す場合があります。その場合、順序を制御したいと考えています。私の記憶がよければ、gambit-C でコンパイルされたプログラムは引数を右から左に評価しますが、gambit のインタープリターで左から右に解釈されます。つまり、問題は実際に存在します。. そしてまさに、cps があなたを救うかもしれません [実際には他の手段もありますが、今は cps についてです!]. あなたが投稿したスキームの例では、「+」の引数が左から右に評価されることが強制されています。簡単に変更できます。

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

そして、それが問題です。

他のいくつかのアプリケーションについては、コメントで既に述べたように、CPS への変換により、すべてのアプリケーションが末尾位置に移動するため、コール スタックがラムダに置き換えられます。さらに、それらを非機能化すると、得られるのは、制御フロー -- C などの命令型言語に変換されるきちんとした形式。完全自動！または、モナドのマンボジャンボを実装したい場合は、CPS で多分モナドと言って、簡単です。各継続ラムダの前に、受け取った値が「ちょうど何か」であるかどうかのテストを追加するだけです (その場合、仕事をします)結果を継続にプッシュする)、または "Nothing" の場合、(継続ラムダに) Nothing をプッシュするだけです。 もちろん、手動ではなく、別のプログラムやマクロを使用します。面倒な作業になる可能性があります。cps を操作する最も魔法のような機能は、cps への変換を簡単に自動化できることです。

不必要に複雑にしないことを願っています。

于 2016-07-27T19:08:44.473 に答える
1

Continuation モナドの非常に包括的な紹介を作成しました。ここで見つけることができます C# での Continuation モナドの発見

また、ここで.Net Fiddleを見つけることができます

ここで要約して繰り返します 初期関数から始めます

int Square(int x ){return (x * x);}
  1. Callback を使用して戻り値の型を削除する
    public static void Square(int x, Action<int> callback)
    {
    callback(x * x);
    }
  1. コールバックのカリー
    public static Action<Action<int>> Square(int x)
    {
     return (callback) => { callback(x * x); };
    }
  1. 返された継続を一般化する
    public static Func<Func<int,T>,T> Square<T>(int x)
    {
         return (callback) => { callback(x * x); };
    }
  1. モナドのリターンメソッドとしても知られる継続構造を抽出する
       delegate T Cont<U, T>(Func<U, T> f);

    public static Cont<U, T> ToContinuation<U, T>(this U x)
    {
       return (callback) => callback(x);
    }

    square.ToContinuation<Func<int, int>, int>()
  1. bind Monadic メソッドを追加して Monad を完成させます
    public static Cont<V, Answer> Bind<T, U, V, Answer>(
    this Cont<T, Answer> m,
    Func<T, Cont<U, Answer>> k, 
    Func<T, U, V> selector)
    {
     return (Func<V, Answer> c) => 
    m(t => k(t)(y => c(selector(t, y))));
    }
于 2019-03-24T12:10:46.367 に答える