Почему продолжения избегают 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))

Таким образом, проблемы с гнездом (и переполнением) могут быть решены с помощью Tail Recursion - запуск аккумулятора 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)

Итак, поскольку на каждом шаге оценивается аккумулятор, нет гнездования, и мы избегаем разрыва стека. Ясно!

Далее идет 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)

Насколько я понимаю, итеративно это можно было бы написать как:

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 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+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/

Ответ 1