为什么延续避免stackoverflow？

Question

我一直在努力理解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应用于此问题会给出:

"例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)

根据我的理解,迭代地这可以写成:

1. loop[2;3] (fun x -> cont (1+x))
2. loop[3] (fun x ->cont (1+x) -> cont(2+x))
3. 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/

Answer 1

发生的事情很简单.

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

在常规的非尾递归中,您可以跟踪堆栈中的进度(非常明显).在CPS中,您可以跟踪lambda函数(在堆上的函数)的进度,并且尾递归优化可确保堆栈保持清除任何跟踪.

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