相关疑难解决方法(0)

我一直在努力理解continuation/CPS,并且从我可以收集的内容中建立一个延迟计算,一旦我们到达列表的末尾,我们就会调用最终的计算.

我不明白的是,为什么CPS会阻止堆栈溢出,因为它看起来类似于按照示例1中的天真方法构建嵌套函数.对于长篇文章感到抱歉但是试图表明这个想法(可能在哪里出错)基本:

所以:

let list1 = [1;2;3]

例1:"天真的方法"

let rec sumList = function
    |[] -> 0
    |h::t -> h + sumList t

因此,当它运行时,迭代地导致:

1. 1 + sumList [2;3]
2. 1 + (2 + sumList [3])
3. 1 + (2 + (3 + 0))

因此,Tail Recursion可以克服嵌套(和溢出问题) - 运行累加器即

"示例2:尾递归"

let sumListACC lst =
    let rec loop l acc =
        match l with
        |[] -> acc
        |h::t -> loop t (h + acc)
    loop lst 0

即

1. sumList[2;3] (1+0)
2. sumList[3] (2+1)
3. sumList[] (3+3)

因此,因为在每一步都评估累加器,所以没有嵌套,我们避免破坏堆栈.明确!

接下来是CPS,我知道当我们已经有一个累加器时这是必需的但是函数不是尾递归的,例如使用Foldback.虽然在上面的示例中不需要,但将CPS应用于此问题会给出: …

题

通过遵循连续传递样式(CPS),可以使每个递归函数尾递归.据我所知,你把第一次递归调用后的所有内容都放到一个函数中,然后把它交给同一个调用.因此,递归调用是函数中的最后一个语句,编译器能够进行尾调用优化.这意味着递归被循环替换.没有额外的堆栈帧消耗.

延续是一项功能,它可以完成所有剩下的工作.在我看来,每次递归调用(或循环迭代),延续都在增长.我想知道在执行循环时这个不断增长的指令集存储在内存中的哪个位置.据我所知,只存在两个可以保存动态数据的内存部分:堆栈和堆.我会排除堆栈,因为堆栈帧大小在已经分配时是固定的.它不能保持延续的增长指令集,因此堆剩余.也许堆栈帧包含指向存储连续函数的存储器地址的指针.这个假设是否正确？

例

这里有一个简单的例子.这是一个递归函数,它不是尾递归的:

// bigList: int -> int list
let rec bigList = function
    | 0 -> []
    | n -> 1 :: bigList (n-1)

当参数n很小时,一切都可以:

> bigList 3;;
val it : int list = [1; 1; 1]

但是当n很好时你可以得到一个stackoverflow错误:

> bigList 170000;;
Stack overflow in unmanaged: IP: 0x2dcdb0, fault addr: 0xbf759ffc
Stack overflow in unmanaged: IP: 0x2dcdb0, fault addr: 0xbf758ffc
...

这基本上是相同的功能,但在延续传递方式:

// bigListC: int -> (int list -> 'a) -> 'a
let rec bigListC n c = …