f# - 为什么继续操作可以避免stackoverflow？

我一直在尝试理解延续性/CPS，从我的收集中可以得出延迟的计算结果，一旦到达列表的末尾，我们便调用最终的计算结果。

我不明白的是，为什么CPS阻止了stackoverflow，这似乎类似于按照示例1中的幼稚方法来构建嵌套函数。基本:

所以:

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

IE，

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)会产生上述示例的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/

最佳答案

发生的事情很简单。

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

在常规的非尾递归中，您会跟踪堆栈中的进度(很明显)。在CPS中，您可以跟踪lambda函数(在堆上!)的进度，并且尾部递归优化可确保堆栈不进行任何跟踪。

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

关于f# - 为什么继续操作可以避免stackoverflow？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15746230/