7

我是 ocaml 的新手，并尝试编写一个延续传递样式函数，但很困惑我需要将什么值传递给 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 *)
4

4 回答 4

12

延续k是一个函数，它获取结果evenk并执行“其余计算”并产生“答案”。答案的类型以及“其余计算”的含义取决于您将 CPS用于什么。CPS 本身通常不是目的，而是出于某种目的而完成的。例如，在 CPS 形式中，很容易实现控制运算符或优化尾调用。在不知道您要完成什么的情况下，很难回答您的问题。

对于它的价值，如果您只是尝试从直接样式转换为延续传递样式，并且您所关心的只是答案的值，那么将恒等函数作为延续传递是正确的。

一个好的下一步是evenk使用 CPS 来实施。我会做一个更简单的例子。如果我有直接式功能

let muladd x i n = x + i * n

如果我假设 CPS 原语mulkand addk，我可以写

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

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

我希望这有帮助。

于 2010-06-18T23:11:36.857 回答
8

每当我使用 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;;

示例用法：“偶数 [2; 4; 6; 8] id;;”。

于 2010-06-20T23:54:24.277 回答
6

由于您调用了evenk正确的（使用身份功能 - 有效地将连续传递样式转换回正常样式），我认为困难在于定义evenk.

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

于 2010-06-19T01:26:08.973 回答
1

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

这是您的函数，用于测试列表是否只有偶数：

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

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

于 2011-04-20T10:36:56.190 回答