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

查看延续传递样式的一种方法是想象如果不允许函数返回,您将如何编写代码.您仍然可以通过在函数执行计算后使用每个函数的额外参数来说明您想要执行的操作.即,您传递的函数充当整体计算的"延续".

你给出的代码就是这样编写的,并且c是继续的.即,它是调用者传入的函数,它告诉函数执行其预期计算后要执行的操作.

延续传递风格是完全通用的,即所有计算都可以这种方式表达.事实上,从普通的功能代码到延续传递风格的机械转换.

Answer 2

已经给出了一般答案，但具体来说cont_sumlist，

\n

\n

• 如果[]我们“返回”（即输入）0 给 c定的内容（0 是空列表的总和），并且

  \n
\n

• 如果(h::t)我们构造延续 for ，cont_sumlist t以便在(ie )的结果准备好后，它将与(by )组合并进一步输入给我们 fortxhh + xc(h::t)。

  \n
\n

\n

因此，这表达了方程 ，但评估链被明确表示为这些连续函数的链，每个连续函数将其结果馈送到其上方的连续函数；而不是隐含在基于堆栈的评估机制中。sumlist (h::t) = h + sumlist t

\n

换句话说， fun x -> c (h + x)= c \xe2\x88\x98 (h +)，因此当我们沿着 list 前进时[h1; h2; h3; ...]，延续将逐渐被构造为，并最终在列表被完全搜索完时c0 \xe2\x88\x98 (h1 +) \xe2\x88\x98 (h2 +) \xe2\x88\x98 (h3 +) \xe2\x88\x98 ...被调用；0其中c0是用户对最顶层调用给出的最顶层延续，例如

\n

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

\n

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

\n

 (c \xe2\x88\x98 (x +) \xe2\x88\x98 (y +) \xe2\x88\x98 (z +) \xe2\x88\x98 ... \xe2\x88\x98 (n +) ) 0\n= \n  c (x + (y + (z + .... + (n + 0) .... )))\n

\n

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

\n

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

\n

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

\n

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

\n

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

\n