c# - 连续传递风格的中间值和返回值

Question

我来自 OOP、非功能性背景，因此我无法完全可视化有关 continuation passing 的几个在线示例。 。另外，像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)))

因此，重写 CPS pyth& C# 版本导致:

// (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& ，并且所有其他调用都会获取 lambda，但这些 lambda 并不真正将中间值“传递”到原始延续。上面函数中的代码基本上类似于 k(Math.Sqrt(x * x + y * y)) ，那么这是否意味着我对中间“钩子(Hook)”的假设是错误的？

Answer 1

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 类型。

你几乎是对的(直到对偶性)——调用堆栈上的每一步现在都是对某个延续的调用。一般来说，您可能会将一流的延续与 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 会将每个应用程序移至尾部位置，因此调用堆栈将被 lambda 替换，此外，如果您对它们进行去功能化，您得到的是数据表示控制流的结构——一种要转换为 C 语言或其他命令式语言的简洁形式。全自动!或者，如果你想实现一些 monad mumbo-jumbo，比如说 Maybe monad，在 CPS 中这很简单，只需在每个 continuation-lambda 前面添加测试接收到的值是否是“Just something” (在这种情况下，完成工作并将结果推送到您的延续)，或“Nothing”，在这种情况下，您只需推送 Nothing(到延续 lambda)。当然，而是通过另一个程序或宏，而不是手动，因为这可能很乏味 - cps 最神奇的地方在于，可以很容易地自动转换为 cps。

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