延续传递样式的中间值和返回值

本文关键字：返回值 中间 样式 延续 | 更新日期: 2023-09-27 17:59:04

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

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

  1. 上面的Cont签名是否正确（即Func<double, double>）？应继续fn。接受参数，处理它，然后返回相同类型的值？

  2. 当我第一次开始阅读continuation时，我有一种感觉，这个continuation函数将为调用堆栈中的每一步调用，但在上面的例子中，它只传递给sqrt&，而所有其他调用都会得到Lambda，这些Lambda并没有真正将中间值"传递"给原始continuation。上面函数中的代码基本上类似于k(Math.Sqrt(x * x + y * y))，所以这是否意味着我对中间"钩子"的假设是错误的？

延续传递样式的中间值和返回值

  1. 是的，除非你想用最外层的连续做任何非数字的事情，否则这是正确的。当你的原始表达式涉及更多类型时，你只需要更多的"Cont"，例如

    （定义（foo x）（如果（=x 0）1 0）

在这种情况下，它可能看起来是这样的（对不起，为了简洁起见，我写了这个方案）：

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

--现在，最外层的continuation有一个数字（比方说int）作为输入，而提供给"=&"的continuation则有bool->int类型。

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

您询问的另一件事是cps与控制流之间的关系。注意，在应用性函数语言（如scheme）中，您唯一指定的是，在应用程序的情况下，您首先计算操作数和运算符，然后将后者应用于前者。计算操作数的顺序并不重要——你可以从左到右，从右到左[或者以某种疯狂的方式]。但是，如果您不使用纯函数样式，并且操作数会产生一些副作用，该怎么办？例如，他们可能会将某些内容打印到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会将每个应用程序移动到尾部位置，因此调用堆栈将被lambdas取代，此外，如果你取消对它们的功能，你会得到一个代表控制流的数据结构——一个可以转换为C或其他命令式语言的整洁形式。完全自动！或者，如果你想实现一些monad的胡言乱语，比如说，也许monad，在CPS中，这很容易，只需在每个延续lambda之前准备测试接收到的值是"justsomething"（在这种情况下，完成任务并将结果推送到延续），还是"Nothing"，在这种情况中，你只需将Nothing推送到延续lambda。当然，通过另一个程序或宏，而不是手动，因为这可能很乏味——cps背后最神奇的是，它很容易自动转换为cps

希望我没有把它弄得不必要的复杂。

我为Continuation monad做了一个非常全面的介绍，您可以在这里找到在C#中发现Continuation Monand

你也可以在这里找到a.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. 提取连续结构也称为monad的返回方法
       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. 添加绑定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))));
    }
相关文章：