Почему продолжения избегают переполнения стека?

Question

Я пытался понять продолжения / 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 вы отслеживаете свой прогресс в лямбда-функциях (которые находятся в куче!), А оптимизация хвостовой рекурсии гарантирует, что в стеке не будет отслеживания.

Поскольку куча значительно больше стека, лучше (в некоторых случаях) перемещать трекинг из стека в кучу - через CPS.