延续传递式计算表达式

Question

能否在 F# 中使用计算表达式实现 CPS？

type ContinuationBuilder() = 
  member this.Return(x) = (fun k -> k x) 
  member this.ReturnFrom(x) = x 
  member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) 
  member this.Delay(f) = f() 

let cps = ContinuationBuilder()

看起来不错。我可以在 CPS 中写 List.map:

let rec mapk f xs = cps {
  match xs with
  | [] -> return []
  | x::xs ->
      let! xs = mapk f xs
      return f x::xs
}

但堆栈溢出：

mapk ((+) 1) [1..1000000] id

我做错了什么？

Answer 1

问题是您在计算构建器中的 Delay 函数立即调用该函数 - 这意味着当您调用 mapk 时，它会立即运行模式匹配和然后递归调用 mapk（在将其结果传递给 Bind 操作之前）。

您可以通过使用 Delay 的实现来解决此问题，return 是一个函数，仅在它被赋予最终延续后才调用 f - 这样，递归调用将只是return一个函数（没有做更多导致堆栈溢出的递归调用）：

member this.Delay(f) = (fun k -> f () k)

使用此版本的 Delay，您的代码对我来说可以正常工作。

延续传递式计算表达式

Continuation Passing Style Computation Expression

f#

computation-expression

continuation-passing