継続はなぜスタックオーバーフローを避けるのですか？

Question

私はcontinuations/CPSを理解しようとしていました。最終的な計算を呼び出すリストの終わりに達すると、遅延計算を構築します。

私が理解できないのは、例1の単純なアプローチのようにネストされた関数を構築するのと類似していると思われる場合、CPSがスタックオーバーフローを防ぐ理由です。長いポストを申し訳ありませんが、基礎から）うまくいかない：だから

：

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が来ますが、これはアキュムレータを既に持っていても機能がテール再帰的ではないことが必要であると私は理解します。フォールドバック付き。上記の例では必要ではないが、この問題に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+cont(2+cont(3+0)))  
(1+(2+(3+0))) 

：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

- オリジナルのポストに

補正は、それがと一致し、上記の例のために17得cont(h+2*x)でcont(h +x)を置き換える例と同様に、右から評価されていることを実現：(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経由で移動するほうが良い場合があります。