再帰とStackOverflowError

Question

テールコールの最適化が行われるように、単純な再帰の例を調整します（StackOverflowErrorではなく）。

count 0 = 0 
count n = succ (count (pred n)) 
count 100000 

Answer 1

これは「長さ/折りたたみ」の種類のスタックオーバーフローの種類です。これは、結果を構成する関数アプリケーションの厳密な引数を計算するために再帰関数が適用されたときに発生します。比較：fが第2引数で厳しいとき

-- naive computation of list length 
-- this is not like it's defined in Frege, of course 
length [] = 0 
length (_:xs) = 1 + length xs 

これをまたfoldr fで発生します。

1. 末尾再帰：

   は（SO）スタックオーバーフローのための他の可能な理由があります。テール再帰関数がwhileループにコンパイルされるため、これはFregeで最も効率的に処理されます。他のJVM言語とは異なり、実際にSOを引き起こすことはありません。

2. 明示的な間接テール再帰：（例えば、aテールコールb、テールはcをコールし、テールはaを呼び出します）。これは決してFregeのSOをもたらさないはずです。
3. 深くネストされたサンクの建物は、評価時にSOが発生します。これはHaskellのfoldlで起こります。 Fregeでは、標準foldはアキュムレータに厳格であり、多くの場合免除されています。しかし、長いリストでは次のようにオーバーフローします。fold (<>) mempty (map (Just . Sum) [1..10000])
4. この例のように、長さ/折り返しの種類は繰り返します。非尾に
5. 再帰呼び出し：

   even 0 = true 
       even n = case even (pred n) of 
         true -> false 
         false -> true 
   

   第2の式がeven n = not (even (pred n))と意味的に等価であり、したがって4の一層悪質な変異体である：ここ

は最後の場合の例です。

あなたの質問に答えるには、アキュムレータを使用してテール再帰バージョンを作成することができます。

count n = go 0 n 
    where 
     go acc 0 = acc 
     go acc n = go (succ acc) (pred n) 

Haskellであなたの例も失敗したことは注目におそらく価値がある：

GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help 
Loading package ghc-prim ... linking ... done. 
Loading package integer-gmp ... linking ... done. 
Loading package base ... linking ... done. 
Prelude> let count 0 = 0; count n = succ (count (pred n)) 
Prelude> count 10000 
10000 
Prelude> count 100000 
100000 
Prelude> count 1000000 
1000000 
Prelude> count 10000000 
10000000 
Prelude> count 100000000 
*** Exception: stack overflow 

それだけではるかに高い数字で溢れている理由は、HaskellのRTSがより適している方法で、RAMを管理していることですJVMは起動時に小さなデフォルトスタックを割り当てますが、最高で数千のコール深度に対応しています。

あなたは大きなスタックを割り当てるためにJVMを強制するときにもフレーゲでプログラムをはるかに大きい数字を計算することができます

java -Xss512m .... 

経験は、サイズ512メートルのスタックがapproximatly千万のための呼び出しの深さを可能にすることを示しています単一の引数関数。

ただし、これは一般的な解決策ではありません。これは、JVMがこのスタックサイズのすべてすべてのスレッドを作成するためです。したがって、貴重なRAMが無駄になります。そしてたくさんのRAMがあっても、たぶん2g以上のスタックを作ることはできません。

Fregeの次のメジャーバージョンでは、スタックオーバーフローの種類3と4（上記参照）の病理学的なケースはうまくいけばうまく管理されます。しかし、今日の時点では、そのような構成は、JVMスタックに収まる小さな問題のサイズに対してのみ機能します。