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

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

Так вложенности (и проблемы переполнения) можно преодолеть хвостовую рекурсию - работает аккумулятор т.е.

«Пример 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. Хотя это и не требуется в приведенном выше примере, применяя КПА к этой проблеме дает:

«Пример 3: КПС»

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 i.е:

• 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.