ocaml 中的延续传递样式

Question

我对这个概念有点困惑。所以我有以下功能

    let rec sumlist lst =
          match lst with
             | [] -> 0
             | (h::t) -> h + (sumlist t)

连贯可以写成

let rec cont_sumlist lst c =
match lst with
| [] -> (c 0)
| (h::t) -> cont_sumlist t (fun x -> c (h + x))

我仍然对 c 的含义和作用感到困惑

Answer 1

查看连续传递样式的一种方法是想象如果函数不允许return，您将如何编写代码。您仍然可以通过为每个函数添加一个额外参数来让事情正常进行，该参数告诉您在函数完成计算后您想要做什么。即，您传递一个函数作为整体计算的 "continuation"。

你给的代码就是这样写的，c是延续。也就是说，它是调用者传入的一个函数，它告诉函数在执行其预期计算后下一步要做什么。

Continuation-passing 风格是完全通用的，即所有的计算都可以用这种方式表达。而且，事实上，从普通功能代码到连续传递样式的机械转换。

Answer 2

已经给出了一般性答案，但具体针对 cont_sumlist、

在 [] 的情况下，我们“return”（即饲料）0 进入 c 我们得到的（0 是一个空列表的总和），并且
在 (h::t) 的情况下，我们构造 cont_sumlist t 的延续，以便在之后 t 的结果（即 x) 准备就绪，它将与 h（由 h + x）合并，并进一步送入给我们的 c (h::t).

因此表达了等式 sumlist (<b>h</b>::t) = <b>h +</b> sumlist t，但是求值链被显式作为这些延续函数的链，每个函数将其结果提供给它上面的延续函数；而不是隐含在基于堆栈的评估机制中。

换句话说 fun x -> c (h + x) = c ∘ (h +)，所以当我们沿着列表 [h1; h2; h3; ...] 前进时，延续被逐步构建为 c0 ∘ (h1 +) ∘ (h2 +) ∘ (h3 +) ∘ ...，并最终被称为0 当列表被完全搜索时；其中 c0 是用户给最顶层调用的最顶层延续，例如

cont_sumlist [1,2] (fun x -> x) 
= 
 (fun x -> (fun x -> (fun x -> x) (1 + x)) (2 + x)) 0
=
                     (fun x -> x) 
           (fun x ->              (1 + x)) 
 (fun x ->                                 (2 + x)) 0
=
                                  (1 +     (2 +     0))

所以整体cont_sumlist [x; y; z; ... ; n] c变成了

 (c ∘ (x +) ∘ (y +) ∘ (z +) ∘ ... ∘ (n +) ) 0
= 
  c (x + (y + (z + .... + (n + 0) .... )))

关键的区别是不涉及堆栈卷绕和展开，并且直接从右到左计算总和，以类似 C 的伪代码作为一系列简单步骤给出

    r = 0; 
    r += n; 
    .......
    r += z;
    r += y;
    r += x;
    call c(r);     // call c with r, without expecting c to return; like a jump

有人可能会说整体延续的构造类似于结束堆栈，及其应用——在传统的基于堆栈的评估下展开堆栈。

另一种说法是，CPS 定义了一种特殊的函数调用协议，不同于通常的类 C 协议，后者期望每个函数调用 return。

CPS定义中的每个case都可以解释为给出函数的小步语义转换规则：{ [] } --> 0 ; { (h::t) } --> h + { t }.

ocaml 中的延续传递样式

Continuation Passing Style in ocaml

ocaml

continuation-passing