dlaczego kontynuacje unikają stackoverflow?

Question

Próbowałem zrozumieć kontynuacje/CPS i na podstawie tego, co mogę zebrać, buduję opóźnione obliczenia, kiedy dojdziemy do końca listy, wywołujemy ostateczne obliczenia.

Czego nie rozumiem, to dlaczego CPS zapobiega stackoverflow, gdy wydaje się analogiczne do budowania funkcji zagnieżdżonej, jak na naiwne podejście w przykładzie 1. Przepraszamy za długi post, ale próbował pokazać pomysł (i ewentualnie gdzie to idzie źle) od podstaw:

Więc:

let list1 = [1;2;3] 

Przykład 1: "naiwne podejście"

let rec sumList = function 
    |[] -> 0 
    |h::t -> h + sumList t 

Więc kiedy to skończy, iteracyjnie skutkuje:

1. 1 + sumList [2;3]
2. 1 + (2 + sumList [3])
3. 1 + (2 + (3 + 0))

Więc zagnieżdżenie (i kwestie przelewowe) mogą być przezwyciężone przez Tail rekursji - działa akumulator tj.

"Przykład 2: Rekursja ogona"

let sumListACC lst = 
    let rec loop l acc = 
     match l with 
     |[] -> acc 
     |h::t -> loop t (h + acc) 
    loop lst 0 

tj

1. sumList[2;3] (1+0)
2. sumList[3] (2+1)
3. sumList[] (3+3)

tak dlatego, że akumulator jest oceniana na każdym kroku, nie ma gniazdowania i unikamy pęknięcie stos . Jasny!

Dalej przychodzi CPS, Rozumiem, że jest to wymagane, gdy mamy już akumulator, ale funkcja nie jest rekurencyjna, np. z foldback. Chociaż nie jest to wymagane w powyższym przykładzie, stosując CPS tego problemu daje:

"Przykład 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) 

mojego rozeznania, iteracyjnie to może być zapisany jako:

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)

, która następnie zmniejsza się sekwencyjnie od prawej z ostatecznym 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

który Przypuszczam jest analogiczna do:

cont(1+cont(2+cont(3+0)))  
(1+(2+(3+0))) 

korekta do oryginalnej wiadomości - zrozumiał, że jest oceniany z prawej strony, na przykład zastępując cont(h +x) z cont(h+2*x) daje 17 dla powyższego przykładu zgodny z: (1+2*(2+2*(3+2*0)))

czyli dokładnie tam, gdzie zaczęliśmy w przykładzie 1, na podstawie tego skoro wciąż musimy śledzić, skąd pochodzimy, dlaczego użycie tego zapobiega problemowi przepełnienia, którego przykład 1 cierpi?

Jak wiem, nie mam, gdzie się pomyliłem?

Przeczytałem następujące posty (wiele razy), ale powyższy błąd pozostaje.

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

Co się dzieje, jest bardzo proste.

.NET (i inne platformy, ale omawiamy teraz F #) przechowuje informacje w dwóch lokalizacjach: stos (dla typów wartości, dla wskaźnika dla obiektów i dla śledzenia wywołań funkcji) i sterty (dla obiektów).

W regularnej rekursji non-tail śledzisz postępy w stosie (oczywiście). W CPS śledzisz swoje postępy w funkcjach lambda (które znajdują się na stercie!), A optymalizacja rekursji ogona zapewnia, że ​​stos pozostaje wolny od śledzenia.

Ponieważ stuła jest znacznie większa niż stos, to (w niektórych przypadkach) lepiej jest przenieść śledzenie ze stosu do sterty - przez CPS.