2

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

    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对它的手段和作用感到困惑

4

2 回答 2

6

查看延续传递风格的一种方法是想象如果不允许函数返回，您将如何编写代码。您仍然可以通过为每个函数添加一个额外的参数来使事情正常进行，该参数告诉您在函数进行计算后要做什么。即，您传递了一个函数，该函数充当整个计算的“延续”。

你给出的代码就是这样写的，c是延续。即，它是调用者传入的一个函数，它告诉函数完成其预期计算后下一步该做什么。

延续传递风格是完全通用的，即所有计算都可以用这种方式表示。而且，事实上，从普通的函数式代码到延续传递风格有一个机械的转换。

于 2017-10-26T04:58:54.757 回答
5

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

  • 如果[]我们“返回”（即馈送）0 给 c我们（0 是一个空列表的总和），并且

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

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

换句话说fun x -> c (h + x)= c ∘ (h +)，所以当我们沿着 list 前进时[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 协议不同，它期望每个函数调用都返回。

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

于 2017-10-27T06:29:29.483 回答