F# CPS 评估顺序

Question

我试图在使用F＃中使用持续通信样式时了解评估顺序。 以此功能为例。

let rec CPSfunc n k c =
    if k = 0 then c 1
    else if k > 0 then CPSfunc n (k-1) (fun res -> c(2*res+k))

使用参数运行时第一的。

CPSfunc 4 3 (fun res -> res)
CPSfunc 4 2 (fun res -> fun 2*res+3 -> res)
CPSfunc 4 1 (fun res -> fun 2*res+2 -> fun 2*res+3 -> res)
// Evaluating backwards
fun res -> fun 2*res+2 -> fun 2*res+3 -> 1
fun res -> fun 2*res+2 -> 2*1+3
fun res -> 2*5+2
// Evaluating forward
fun 1 -> fun 2*res+2 -> fun 2*res+3 -> res
fun 2*1+2 -> fun 2*res+3 -> res
fun 2*4+3 -> res
4

如何正确计算正确的输出？

Answer 1

要看到 19 是正确的结果，我认为最简单的方法是从 k = 0 开始并递增。每个结果只是前一个结果的两倍加上k。 （请注意，未使用 n。）因此我们有：

k = 0 ->     1     =  1
k = 1 -> 2 * 1 + 1 =  3
k = 2 -> 2 * 3 + 2 =  8
k = 3 -> 2 * 8 + 3 = 19

不过，将简单逻辑转换为延续会变得复杂。下面是 F# 中 CPSfunc 4 3 id 的扩展：

// unexpanded initial call
let c3 = (fun res -> res)
CPSfunc 4 3 c3

// expanded once, k = 3
let c2 = (fun res -> c3 (2 * res + 3))
CPSfunc 4 2 c2

// expanded again, k = 2
let c1 = (fun res -> c2 (2 * res + 2))
CPSfunc 4 1 c1

// expanded again, k = 1
let c0 = (fun res -> c1 (2 * res + 1))
CPSfunc 4 0 c0

// full expansion, k = 0
c0 1

PS 要使 c 具有所需的 int ->; int 签名，您需要稍微不同地定义 CPSfunc ，所以我假设您实际上已经完成了：

let rec CPSfunc n k c =
    if k = 0 then c 1
    elif k > 0 then CPSfunc n (k-1) (fun res -> c(2*res+k))
    else failwith "k < 0"

Answer 2

CPSfunc 4 3 id
CPSfunc 4 2 (fun res -> id(2*res+k))
CPSfunc 4 2 (fun res -> 2*res+3)
CPSfunc 4 1 (fun res -> (fun res -> 2*res+2)(2*res + k))
CPSfunc 4 1 (fun res -> (2*(2*res + 2)+3))
CPSfunc 4 0 (fun res -> (fun res -> (2*(2*res + 2)+3))(2*res + k))
CPSfunc 4 0 (fun res -> 2*(2*(2*res+1) + 2)+3))
(fun res -> 2*(2*(2*res+1) + 2)+3)(1)
2*(2*(2*1+1)+2)+3
19

实际上，我通过对上述功能进行评估，在对​​它们进行实际评估之前评估了一些功能，从而获得了一些自由，但这并不重要