如何转换CPS样式的gcd计算以使用Continuation Monad

Question

让我们考虑Continuation monad的以下实现,对于CPS样式的计算产生和整数:

module Cont : sig
  type 'a t = ('a -> int) -> int
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
  val callCC: (('a -> 'b t) -> 'a t) -> 'a t
end = struct
  type 'a t = ('a -> int) -> int

  let return x =
    fun cont -> cont x

  let bind m f =
    fun cont -> m (fun x -> (f x) cont)

  let callCC k =
    fun cont -> k (fun x -> (fun _ -> cont x)) cont
end

我们如何重写CPS风格的gcd计算实现(参见如何记忆递归函数？),尤其是memoization以利用Cont monad？

定义之后

let gcd_cont k (a,b) =
  let (q, r) = (a / b, a mod b) in
  if r = 0 then Cont.return b else k (b,r)

我尝试使用类型求解器给出关于memoization函数应该具有的类型的提示:

# let gcd memo ((a,b):int * int) =
  Cont.callCC (memo gcd_cont (a,b)) (fun x -> x)
;;
    val gcd :
  (((int * int -> int Cont.t) -> int * int -> int Cont.t) ->
   int * int -> (int -> 'a Cont.t) -> int Cont.t) ->
  int * int -> int = <fun>

但是,我无法将此提示转换为实际实现.有人能够这样做吗？在memoization函数中使用"callCC"的逻辑是,如果在缓存中找到一个值,那么这是一个提前退出的条件.

Answer 1

我觉得问题在于他对如何记忆递归函数？，迈克尔称之为CPS风格什么不是CPS风格。在 CPS 风格中，只要想要返回一个值，就会使用额外的延续参数k- 然后将应用该值k。

\n\n

这并不是我们真正想要的，也不是实现的：

\n\n

let gcd_cont k (a,b) =\n  let (q, r) = (a / b, a mod b) in\n  if r = 0 then b else k (b,r)\n

\n\n

这里，k不用于返回（b直接返回），它用于代替执行递归调用。这展开了递归：在 内gcd_cont，人们可以将其视为k自身gcd_cont，就像let rec使用 if 一样。稍后，gcd_cont可以使用定点组合器将其转变为真正的递归函数，基本上“将其提供给自身”：

\n\n

let rec fix f x = f (fix f) x\nlet gcd = fix gcd_cont\n

\n\n

（这相当于callMichael定义的函数）

\n\n

gcd与直接使用 a定义的区别let rec在于，具有展开递归的版本允许“检测”递归调用，因为递归本身是由定点组合器执行的。这就是我们想要的记忆：如果结果不在缓存中，我们只想执行递归。这就是组合器的定义memo。

\n\n

如果使用 a 定义函数let rec，则在定义函数的同时关闭递归，因此无法检测递归调用站点以插入记忆。

\n\n

作为旁注，这两个答案基本上实现了相同的事情：唯一的区别是它们在定点组合器中实现递归的方式：Michael 的定点组合器使用let rec，Jackson 的一个使用引用，即“Landin” s 结" \xe2\x80\x94 是实现递归的另一种方法（如果您有您语言中的引用）。

\n\n

Sooo，总而言之，我想说在延续 monad 中实现这一点实际上是不可能的/没有真正意义，因为这本来就不是 CPS。

\n