Ocaml延续传球风格

Question

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

Answer 1

延续k是一个函数,它从中获取结果evenk并执行"其余的计算"并产生"答案".答案的类型和"其余计算"的含义取决于您使用CPS 的内容.CPS本身通常不是目的,但考虑到某些目的.例如,在CPS形式中,实现控制运算符或优化尾调用非常容易.在不知道你想要完成什么的情况下,很难回答你的问题.

对于它的价值,如果你只是试图从直接风格转换为延续传递风格,而你关心的只是答案的价值,传递身份函数作为延续是正确的.

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

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'

你会看到mulptiplication首先做的话,就"继续"用k',它不添加,最后是continues用k,它返回给调用者.关键的想法是,在muladdk我的身体内部分配了一个新的延续k',代表乘法 - 加法函数的中间点.为了完成你的evenk工作,你必须至少分配一个这样的延续.

我希望这有帮助.

Answer 2

每当我玩CPS时,传递给延续的东西就是你通常会回到调用者身上的东西.在这个简单的例子中,一个很好的"直觉润滑剂"就是将继续命名为"返回".

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诺曼说,是表示其余计算并产生最终值的延续函数.所以,你需要做的是计算的结果v的even,并且结果传递给k,返回k v而不是只v.