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 id 时，它的计算结果为 19，但是当我尝试手动计算它时，我会根据向前或向后计算得到不同的结果首先.

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

不过，将简单的逻辑转换为延续会变得很复杂。下面是 CPSfunc 4 3 id:

在 F# 中的展开形式

// 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

P.S。要使 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

实际上我在上面的一些函数实际被求值之前通过求值采取了一些自由，但这并不重要

F# CPS 评估顺序

F# CPS evaluation order

continuations

f#

functional-programming

cps