f# - 为什么延续要避免stackoverflow？

Question

我一直在尝试理解延续/CPS，并且从我可以收集到的信息中，它会建立一个延迟计算，一旦我们到达列表的末尾，我们就会调用最终计算。

我不明白的是，当 CPS 看起来类似于按照示例 1 中的幼稚方法构建嵌套函数时，为什么 CPS 会阻止 stackoverflow。抱歉这篇长篇文章，但试图展示这个想法(以及可能出错的地方)来自基础知识:

所以:

let list1 = [1;2;3]

示例 1:“天真的方法”

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

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

1 + sumList [2;3]

1 + (2 + sumList [3])

1 + (2 + (3 + 0))

所以嵌套(和溢出问题)可以通过尾递归来克服——运行一个累加器，即

“示例 2:尾递归”

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

即，

sumList[2;3] (1+0)

sumList[3] (2+1)

sumList[] (3+3)

因此，因为累加器在每一步都被评估，所以没有嵌套，我们避免了堆栈的爆裂。清除!

接下来是 CPS，我知道当我们已经有一个累加器但函数不是尾递归时这是必需的，例如与折返。虽然在上面的例子中不是必需的，但是将 CPS 应用于这个问题会给出:

“示例 3:CPS”

let sumListCPS lst =
    let rec loop l cont =
        match l with
        |[] -> cont 0
        |h::t -> loop t (fun x -> cont( h + x))
    loop lst (fun x -> x)

据我了解，这可以迭代地写为:

loop[2;3] (fun x -> cont (1+x))

loop[3] (fun x ->cont (1+x) -> cont(2+x))

loop[] (fun x -> cont (1+x) -> cont(2+x) -> cont (3+x)

然后从右边依次减少最后的 x = 0即:

cont(1+x)-> cont(2+x) -> cont (3+0)

cont(1+x)-> cont(2+x) -> 3

cont(1+x) -> cont (2+3)

...

cont (1+5) -> 6

我想这类似于:

cont(1+cont(2+cont(3+0)))    
(1+(2+(3+0)))

对原始帖子的更正 - 意识到它是从右侧评估的，例如替换 cont(h +x)与 cont(h+2*x) yield 17对于上面的例子符合: (1+2*(2+2*(3+2*0)))
即我们在示例 1 中开始的确切位置，基于此，因为我们仍然需要跟踪我们来自哪里 为什么使用它可以防止示例 1 遭受的溢出问题？

据我所知没有，我哪里出错了？

我已经阅读了以下帖子(多次)，但上述困惑仍然存在。

http://www.markhneedham.com/blog/2009/06/22/f-continuation-passing-style/

http://codebetter.com/matthewpodwysocki/2008/08/13/recursing-on-recursion-continuation-passing/

http://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/

Answer 1

发生的事情很简单。

.NET(和其他平台，但我们现在讨论的是 F#)将信息存储在两个位置:堆栈(用于值类型、对象指针和跟踪函数调用)和堆(用于对象)。

在常规的非尾递归中，您可以跟踪堆栈中的进度(很明显)。在 CPS 中，您可以跟踪 lambda 函数(它们在堆上!)的进度，尾递归优化确保堆栈没有任何跟踪。

由于堆明显大于堆栈，因此(在某些情况下)最好通过 CPS 将跟踪从堆栈移动到堆。