Ocaml的延续传递风格

Question

我是一名新手，正在尝试编写一个延续传递风格的函数，但是不太清楚需要将哪个值传递到附加参数 k 中。

例如，我可以编写一个递归函数，如果列表中的所有元素都是偶数，则返回 true，否则返回 false。

代码如下：

let rec even list = .... 

在 CPS 中，我知道我需要添加一个参数来传递函数，就像这样：

let rec evenk list k = .... 

但是我不知道如何处理这个k以及它的确切作用。

例如对于这个偶函数，环境看起来像：

val evenk : int list -> (bool -> ’a) -> ’a = <fun>

evenk [4; 2; 12; 5; 6] (fun x -> x)  (* output should give false *)

- REALFREE

Answer 1

续传函数 k 接收来自evenk的结果并执行“剩余计算”，生成“答案”。答案的类型和“剩余计算”的含义取决于使用CPS的目的。 CPS通常不是最终目标，而是带有某些目的。例如，在CPS形式下，很容易实现控制操作符或优化尾调用。如果不知道你要完成什么任务，很难回答你的问题。

值得一提的是，如果你只是想从直接方式转换为过程传递方式，并且你关心的只是答案的值，则将身份函数作为续传函数传递是正确的。

一个好的下一步是使用CPS实现evenk。我会举个更简单的例子。如果我有直接方式函数：

let muladd x i n = x + i * n

如果我假设CPS基元mulk和addk，那么我可以写成

let muladdk x i n k =
  let k' product = addk x product k in
  mulk i n k'

你会发现乘法先进行，然后“继续”使用k'执行加法，最后使用k“继续”返回给调用者。关键思想是，在muladdk的主体中，我分配了一个新的continuation k'，它代表了乘-加函数中的一个中间点。为了使你的evenk工作，你将需要分配至少一个这样的continuation。

希望这能帮到你。

- Norman Ramsey

Answer 2

每当我使用 CPS 时，传递给 continuation 的东西就是通常返回给调用方的东西。在这个简单的例子中，一个好的“直觉润滑剂”是将 continuation 命名为“return”。

let rec even list return =
  if List.length list = 0
    then return true
    else if List.hd list mod 2 = 1
      then return false
      else even (List.tl list) return;;

let id = fun x -> x;;

示例用法: “even [2; 4; 6; 8] id;;”

- George Kangas

Answer 3

自从您正确调用了evenk（使用恒等函数 - 实际上将续传样式转换回正常样式），我认为困难在于定义evenk。

如Norman所说，k是表示计算的其余部分并生成最终值的续传函数。因此，您需要计算even的v结果，并将该结果传递给k，而不仅仅是返回v，应该返回k v。

- Michael Ekstrand

Answer 4

你想将函数的结果作为输入，就好像它没有使用 continuation passing style 一样。

这是一个测试列表是否只包含偶数整数的函数：

(* val even_list : int list -> bool *)
let even_list input = List.for_all (fun x -> x mod 2=0) input

现在让我们使用 continuation cont 来编写它：

(* val evenk : int list -> (bool -> 'a) -> 'a *)
let evenk input cont =
  let result = even_list input in
  (cont result)

你计算出函数的结果，并将result传递给续体...

- Hugo