ocaml 中的连续传球风格 [英] Continuation Passing Style in ocaml

问题描述

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

I am a bit confused on the concept. So I have the following function

    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 的含义和它的作用感到困惑

I am still confused on what the c means and what it does

推荐答案

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

A general answer is already given, but specifically, for cont_sumlist,

• 在[]的情况下，我们返回"(即feed)0 into c我们得到(0 是一个空列表的总和)，以及

• in case of [] we "return" (i.e. feed) 0 into c that we're given (0 is the sum of an empty list), and

在 (h::t) 的情况下，我们构造 cont_sumlist t 的延续，以便 after 的结果 t(即x)已准备好，它将与h(通过h + x)组合并进一步馈送进入 c 给我们的 (h::t).

in case of (h::t) we construct the continuation for cont_sumlist t so that after the result for t (i.e. x) is ready, it will be combined with h (by h + x) and fed further into c given to us for (h::t).

这就表达了方程 sumlist (h::t) = h + sumlist t，但是求值链显式作为这些延续函数的链，每一个都将其结果提供给它上面的延续函数；而不是隐含在基于堆栈的评估机制中.

This is thus expressing the equation sumlist (h::t) = h + sumlist t, but the evaluation chain is made explicit as the chain of these continuation functions, each feeding its result to the continuation function above it; as opposed to being implicit in the stack-based evaluation mechanism.

换句话说 fun x ->c (h + x) = c ∘ (h +)，所以我们沿着列表 [h1;h2;h3;...]，continuation 被逐步构造为 c0 ∘ (h1 +) ∘ (h2 +) ∘ (h3 +) ∘ ...，最后用 0 当列表已经完全搜索完毕；其中 c0 是用户对最顶层调用给出的最顶层延续，例如

In other words fun x -> c (h + x) = c ∘ (h +), so as we go along the list [h1; h2; h3; ...], the continuation is being progressively constructed as c0 ∘ (h1 +) ∘ (h2 +) ∘ (h3 +) ∘ ..., and is finally called with 0 when the list has been searched through completely; where c0 is the top-most continuation given by a user to the top-most call, e.g.

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 的伪代码中给出，作为一系列简单的步骤

with the crucial difference that there's no stack winding and unwinding involved and the sum is calculated from right to left directly, given in a C-like pseudocode as a sequence of simple steps

    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

有人可能会说，整体的continuation的构造类似于stacking up，其应用对应于传统stack-based评估下的stack unwinding.

One might say that the construction of the overall continuation is similar to winding up the stack, and its application corresponds to the unwinding of the stack under conventional stack-based evaluation.

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

Another way of putting it is that CPS defines a special kind of function call protocol, unlike the usual C-like one which expects every function call to return.

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

Each case in the CPS definition can be interpreted as giving a small-step semantics transition rule for the function: [] --> 0 ; (h::t) --> (h +).

这篇关于ocaml 中的连续传球风格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！