连续传递样式中的中间值和 return 值

Question

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

由于 C# 支持 lambda，我从维基百科文章中获取了第一个示例，并尝试将其移植到具有强类型的 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，但签名会更长。无论如何，我不确定的是：

上面的 Cont 签名是否正确（即 Func<double, double>）？应该继续fn。接受参数，处理，然后return返回相同类型的值？
当我第一次开始阅读有关延续的内容时，我觉得这个延续函数将在调用堆栈中的每个步骤中被调用，但在上面的示例中它只传递给 sqrt&，所有其他调用获取的 lambda 表达式实际上并不是 "pass" 原始延续的中间值。上面函数中的代码基本上类似于k(Math.Sqrt(x * x + y * y))，那么这是否意味着我对中间"hooks"的假设是错误的？

Answer 1

是的，除非你想用最外层的continuation做任何非数值的事情，否则它是正确的。当您的原始表达式涉及更多类型时，您只需要更多 "Cont"s，例如

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

在这种情况下，它可能看起来像这样（抱歉，为了简洁起见，我写在方案中）：

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

-- 现在最外层的延续有一个数字（假设是一个 int）作为输入，而提供给“=&”的是 bool->int 类型。

你几乎是对的（直到对偶性）——调用堆栈上的每一步现在都是对某个延续的调用。一般来说，您可能会将 first-class continuations 与 cps 混淆——前者是一种语言特性（如在方案中，您可以使用 call/cc 运算符访问当前的continuation），后者是您的一种技术可以在任何地方使用。您实际上可以将表达式转换为 cps，甚至不需要您的语言中的高阶函数（只需以某种方式表示它们）。

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

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

Answer 2

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

您还可以找到 a.Net Fiddle here

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

int Square(int x ){return (x * x);}

使用回调并删除 return 类型

    public static void Square(int x, Action<int> callback)
    {
    callback(x * x);
    }

Curry 回调

    public static Action<Action<int>> Square(int x)
    {
     return (callback) => { callback(x * x); };
    }

推广 returned 延续

    public static Func<Func<int,T>,T> Square<T>(int x)
    {
         return (callback) => { callback(x * x); };
    }

提取延续结构也称为 monad 的 Return 方法

       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>()

添加 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))));
    }

连续传递样式中的中间值和 return 值

Intermediate and return values in continuation-passing style

c#

lambda

scheme

continuations

continuation-passing