4

Hugs Haskell 実装での「エラー C スタック オーバーフロー」の通常の原因は何ですか。

4

4 に答える 4

11

これは、末尾再帰因数分解が一般的な関数型言語に慣れている場合に発生する可能性があります。関数があるとします：

sum = go 0
    where
    go accum [] = accum
    go accum (x:xs) = go (accum+x) xs

ちなみに、これは

sum = foldl (+) 0

関数を評価すると、問題がわかります。

sum [1,2,3,4]
go 0 [1,2,3,4]
go (0+1) [2,3,4]
go ((0+1)+2) [3,4]
go (((0+1)+2)+3) [4]
go ((((0+1)+2)+3)+4) []
(((0+1)+2)+3)+4

その式を評価するために、Haskell はスタックを使用します。

EXPR            | STACK
(((0+1)+2)+3)+4 | 
((0+1)+2)+3     | +4
(0+1)+2         | +3 +4
(0+1)           | +2 +3 +4
1               | +2 +3 +4
3               | +3 +4
6               | +4
10              |

そして、ここでオーバーフローが発生する可能性があります。sum [1..10^6] を評価した場合、そのスタックは 100 万エントリの深さになります。

しかし、ここで病状に注意してください。巨大な fscking 式 (「サンク」) を構築するためだけにリストを再帰し、スタックを使用してそれを評価します。末尾の再帰を厳密にすることで、再帰しているように評価したいと思います。

sum = go 0
    where
    go accum [] = accum
    go accum (x:xs) = accum `seq` go (accum+x) xs

これは、再帰呼び出しを評価しようとする前に accum を評価することを意味するため、次のようになります (これを理解するには少し時間がかかる場合があります)。

sum [1,2,3,4]
go 0 [1,2,3,4]
let accum = 0 in accum `seq` go (accum+1) [2,3,4]
go (0+1) [2,3,4]
let accum = 0+1 in accum `seq` go (accum+2) [3,4]
go (1+2) [3,4]
let accum = 1+2 in accum `seq` go (accum+3) [4]
go (3+3) [4]
let accum = 3+3 in accum `seq` go (accum+4) []
go (6+4) []
6+4
10

したがって、リストをトラバースしながら合計を計算しているため、結果を評価するために深いスタックを使用する必要はありません。この変更された末尾再帰パターンは、Data.List.foldl' にカプセル化されているため、次のようになります。

sum = foldl' (+) 0

foldlは常に巨大なサンクを構築するため、決して使用しないことをお勧めします。代わりに foldl' を使用してください。出力タイプが遅延構造 (リストや関数など) の場合は、foldr を使用します。しかし、一般的にスタック オーバーフローを回避するための特効薬はありません。プログラムの評価動作を理解する必要があるだけです。これは難しい場合があります。

しかし、私の理解が正しければ、スタック オーバーフローは常に巨大なサンクを評価しようとすると発生します。そのため、それらを作成できる場所を探し、評価を早期に強制します。

于 2010-03-17T14:35:16.230 に答える
1

暴走再帰が最も可能性の高い候補です...より正確な答えを得るには、より多くの情報を提供する必要があります。

于 2010-03-17T14:04:10.463 に答える
1

ランナウェイ再帰を引き起こす可能性のあるコードを次に示します。

main =
  let x = x :: Int
  in print x

ここで何が起こるかというと、xが評価されるprint xと、その評価を完了するためには を評価する必要があることがわかりますx。

于 2010-03-17T14:07:19.500 に答える
0

最も可能性の高い原因は、制御されていない再帰です。各再帰呼び出しは、その入力/出力パラメーター用に少し多くのスタック スペースを消費します。

于 2010-03-17T14:10:26.257 に答える