如何将CPS风格的gcd计算转换为使用延续Monad

Question

让我们考虑下面的延续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

我们如何重写gcd计算的CPS风格的实现(参见How to memoize recursive functions?)，特别是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

我觉得问题在于，在他对How to memoize recursive functions?的回答中，迈克尔把CPS风格称为什么不是CPS风格。在CPS样式中，只要想要返回值，就会使用额外的连续参数k -然后将该值应用于k。

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

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

这里，k不是用来返回的(直接返回b)，它是用来代替执行递归调用的。这将展开递归:在gcd_cont中，可以将k视为gcd_cont本身，就像使用let rec一样。稍后，可以使用一个固定点组合器将gcd_cont转换为一个真正的递归函数，它基本上是“将其提供给自己”：

let rec fix f x = f (fix f) x
let gcd = fix gcd_cont

(这相当于Michael定义的call函数)

与直接使用let rec定义gcd的不同之处在于，带有未缠绕递归的版本允许“插装”递归调用，因为递归本身是由固定点组合器执行的。这就是我们想要的memoization:我们只想在结果不在缓存中时执行递归。因此就有了memo组合器的定义。

如果使用let rec定义函数，则在定义函数的同时关闭递归，因此无法插入递归调用点来插入memoization。

作为附注，这两个答案基本上实现了相同的东西:唯一的区别是它们在定点组合器中实现递归的方式:迈克尔的定点组合器使用let rec，杰克逊的使用引用，即“Landin的结”--如果你的语言中有引用的话，这是实现递归的另一种方式。

所以，总而言之，我想说在延续monad中实现它是不可能的/没有意义的，因为事情一开始就不是CPS。