2

我来自 OOP，非功能性背景，因此我无法完全可视化几个有关continuation pass的在线示例。此外，像 Scheme 这样的函数式语言不必指定参数类型或返回值，所以我不确定我是否正确理解了这个想法。

由于 C# 支持 lambda，我从 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# 重写 CPSpyth&版本会导致：

// (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) (如果 (= 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，而无需在您的语言中使用高阶函数（仅以某种方式表示它们）。

您问的另一件事是 cps 与控制流的关系。好吧，请注意，在应用程序的函数式语言（如方案）中，您唯一指定的是在应用程序的情况下，您首先评估操作数和运算符，然后将后者应用于前者。评估操作数的顺序无关紧要——您可以从左到右、从右到左[或者可能以某种疯狂的方式]。但是，如果您不使用纯函数式样式，并且操作数会产生一些副作用怎么办？他们可能会打印一些东西到标准输出，然后返回一些值。在这种情况下，您希望控制订单。如果我没记错的话，用 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 会将每个应用程序移动到尾部位置，因此调用堆栈将被替换为 lambdas，并且如果您进一步取消它们的功能，您将得到一个表示控制流——一种可以转换为 C 或其他命令式语言的简洁形式。全自动！或者，如果你想实现一些 monad mumbo-jumbo，比如 Maybe monad，在 CPS 中这很容易，只需在每个 continuation-lambda 前面添加关于接收到的值是否为“Just something ”的测试（在这种情况下完成工作并将结果推送到您的延续）或“Nothing”，在这种情况下，您只需推送 Nothing（到 continuation-lambda）。 当然，而不是通过另一个程序或宏，而不是手动，因为它可能很乏味 - cps 最神奇的地方在于它很容易自动转换为 cps。

希望我没有让它变得不必要的复杂。

于 2016-07-27T19:08:44.473 回答
1

我对 Continuation monad 进行了非常全面的介绍，您可以在这里找到 Discovering the Continuation Monad in C#

你也可以在这里找到一个.Net Fiddle

我在这里总结一下从一个初始函数开始

int Square(int x ){return (x * x);}
  1. 使用回调并删除返回类型
    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. 泛化返回的 Continuation
    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. 添加绑定 Monad 方法，从而完成 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 回答