奥卡姆连续传球风格

Question

我是 ocaml 的新手，尝试编写一个连续传递样式函数，但很困惑我需要将什么值传递给 k 上的附加参数，

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

所以就像在 CPS 上一样

let rec even list = .... 

，我知道我需要添加一个参数来传递函数 很喜欢

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 *)

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'

你会看到乘法首先完成，然后是“ continue” 与 k' 进行添加，最后 continues 与 k 返回给调用者。关键思想是，在 muladdk 主体中，我分配了一个新的延续 k'，它代表乘加函数中的中间点。为了让你的 evenk 工作，你必须分配至少一个这样的延续。

我希望这有帮助。

Answer 2

每当我使用 CPS 时，传递给延续的东西就是您通常返回给调用者的东西。在这个简单的例子中，一个很好的“直觉润滑剂”是将延续命名为“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;;”。

Answer 3

由于您正确调用了 Evenk（使用恒等函数 - 有效地将连续传递样式转换回正常样式），我认为困难在于定义 Evenk >。

正如诺曼所说，k 是代表其余计算并产生最终值的延续函数。因此，您需要做的是计算 even 的 v 结果并将该结果传递给 k，返回 k v code> 而不仅仅是 v。

Answer 4

您希望将函数的结果作为输入，就好像它不是用连续传递样式编写的一样。

这是您的函数，用于测试列表是否仅包含偶数：

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

现在让我们用延续 cont 编写它：

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

您计算函数的结果，并将结果传递给延续...