为什么继续操作可以避免stackoverflow? [英] why do continuations avoid stackoverflow?
问题描述
我一直在尝试理解延续性/CPS，从我的收集中可以得出延迟的计算结果，一旦我们到达列表的末尾，便调用了最终的计算结果.
I've been trying to understand continuations / CPS and from what I can gather it builds up a delayed computation, once we get to the end of the list we invoke the final computation.
我不明白的是，为什么CPS阻止了stackoverflow的出现，就像按照示例1中的幼稚方法构建嵌套函数一样.抱歉，冗长的帖子却试图展示这个想法(以及可能的发展方向)错误):
What I don't understand is why CPS prevents stackoverflow when it seems analogous to building up a nested function as per the naive approach in Example 1. Sorry for the long post but tried to show the idea (and possibly where it goes wrong) from basics:
所以:
let list1 = [1;2;3]
示例1:幼稚的方法"
let rec sumList = function
|[] -> 0
|h::t -> h + sumList t
因此，当它运行时，迭代地导致:
So when this runs, iteratively it results in:
-
1 + sumList [2;3] -
1 + (2 + sumList [3]) -
1 + (2 + (3 + 0))
1 + sumList [2;3]1 + (2 + sumList [3])1 + (2 + (3 + 0))
因此，可以通过尾递归来克服嵌套(和溢出问题)，即运行累加器.
So the nesting (and overflow issues) can be overcome by Tail Recursion - running an accumulator i.e.
示例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)
sumList[2;3] (1+0)sumList[3] (2+1)sumList[] (3+3)
因此，由于累加器在每一步都进行求值，因此没有嵌套，因此我们避免了使堆栈爆裂.清除！
So because the accumulator is evaluated at each step, there is no nesting and we avoid bursting the stack. Clear!
接下来是CPS，我知道当我们已经有一个累加器但该函数不是尾递归时，这是必需的，例如与折返.尽管在上面的示例中不是必需的，但将CPS应用于此问题可以得出:
Next comes CPS, I understand this is required when we already have an accumulator but the function is not tail recursive e.g. with Foldback. Although not required in the above example, applying CPS to this problem gives:
示例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)
据我了解，这可以迭代地写为:
To my understanding, iteratively this could be written as:
-
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)
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减小，即:
which then reduces sequentially from the right with the final x = 0 i.e:
-
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+x)-> cont(2+x) -> cont (3+0)cont(1+x)-> cont(2+x) -> 3cont(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)))
correction to original post - realised that it is evaluated from the right, as for example replacing cont(h +x) with cont(h+2*x) yields 17 for the above example consistent with: (1+2*(2+2*(3+2*0)))
即基于这一点，我们正是从示例1的确切位置开始的，因为我们仍然需要跟踪我们来自何处，为什么使用它可以防止示例1所遭受的溢出问题?
i.e. exactly where we started in example 1, based on this since we still need to keep track of where we came from why does using it prevent the overflow issue that example 1 suffers from?
据我所知，我哪里出错了?
As I know it doesn't, where have I gone wrong?
我已经多次阅读以下帖子，但上面的困惑仍然存在.
I've read the following posts (multiple times) but the above confusion remains.
http://www.markhneedham.com /blog/2009/06/22/f-continuation-passing-style/
http://codebetter.com/matthewpodwysocki /2008/08/13/recursing-re-cursion-continuation-passing/
http://lorgonblog.wordpress.com/2008/04 /05/catamorphisms-part-one/
推荐答案
发生的事情很简单.
.NET(和其他平台，但我们现在正在讨论F#)将信息存储在两个位置:堆栈(用于值类型，用于对象的指针以及用于跟踪函数调用)和堆(用于对象).
.NET (and other platforms, but we're discussing F# right now) stores information in two locations: the stack (for value types, for pointer to objects, and for keeping track of function calls) and the heap (for objects).
在常规的非尾递归中，您跟踪堆栈中的进度(很明显).在CPS中，您可以跟踪lambda函数(在堆上！)的进度，并且尾递归优化可确保堆栈不进行任何跟踪.
In regular non-tail recursion, you keep track of your progress in the stack (quite obviously). In CPS, you keep track of your progress in lambda functions (which are on the heap!), and tail recursion optimization makes sure that the stack stays clear of any tracking.
由于堆明显大于堆栈，因此(在某些情况下)最好通过CPS将跟踪从堆栈移到堆.
As the heap is significantly larger than the stack, it is (in some cases) better to move the tracking from the stack to the heap - via CPS.
这篇关于为什么继续操作可以避免stackoverflow?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
