4

遅延評価のおかげで、Haskell は次の式を一瞬で処理できます。

head.head $ let m = 1000000000000000 in map (\n -> [m*n .. m*(n+1)]) [1 .. m]

しかし、次の式が終了しないことに気付きましたが、メモリ使用量は低いままでした。

last.last $ let m = 1000000000000000 in map (\n -> [m*n .. m*(n+1)]) [1 .. m]

Haskell がそれを実行できることは驚くべきことではありません。しかし、私はそれがどのように機能するのだろうか。より正確には、haskell がメモリを割り当てる方法。メモリレイアウトなどを確認する方法はありますか?

4

2 に答える 2

9

何が起こるかを見るために、この例を少し単純化してみましょう。遅延評価とグラフ削減について考えるだけで、それよりも低いレベルに進む必要なく、ほとんどのことを理解できます。ourLast (mkList 3)このコードで の単純化された削減を見てみましょう:

ourLast :: [a] -> a
ourLast [] = error "ourLast []"
ourLast (x:[]) = x
ourLast (_:xs) = ourLast xs

mkList :: Int -> [Int]
mkList 0 = []
mkList n = let rest = mkList (n-1) in n : rest

?foo「まだ見ていない値」を意味します。これらは「let」で作成します。 foo@barは、「すでに計算済みで、計算した値は」 であることbarを意味します?foofoo@bar foo := barfoobar

    -- We start here by creating some value and giving it to ourLast to
    -- look at.
let ?list3 = mkList 3
ourLast ?list3
    -- At this point ourLast examines its argument to figure out whether
    -- it's of the form (_:_) or []
    -- mkList sees that 3 /= 0, so it can pick the second case, and it
    -- computes the value for ?list3.
    -- (I'll skip the arithmetic reductions and other boring things.)
    let ?list2 = mkList 2
    list3 := 3 : ?list2 -- we don't need to compute ?list2 yet, so
                        -- (mkList 3) is done and we can go back to ourLast
ourLast list3@(3 : ?list2)
    -- ourLast needs to examine ?list2 to find out whether it's [] or not,
    -- so mkList does the same thing again
    let ?list1 = mkList 1
    list2 := 2 : ?list1
ourLast list3@(3 : list2@(2 : ?list1))
    -- Now ourLast has enough information to continue;
    -- ourLast (_ : xs@(_ : _)) = ourLast xs
    -- Notice how we don't need to compute list2 a second time; we save its
    -- value the first time we compute it. This is what lazy evaluation is.
ourLast list2@(2 : ?list1)
    -- at this point, there are no references to `list3` anywhere, so it
    -- can be GCed.
    -- Repeat (ourLast examines ?list1, mkList sees that 1 /= 0).
    let ?list0 = mkList 0
    list1 := 1 : ?list0
ourLast list2@(2 : list1@(1 : ?list0))
ourLast list1@(1 : ?list0)
    -- Can GC list2.
    -- Now mkList is being called with 0, so it just returns an empty list.
    list0 := []
ourLast list1@(1 : list0@[])
1
    -- We're done! (And we can GC list1.)

任意の時点で、実際に割り当てられる必要があるのは 2 つのサンクだけであり、残りはまだ計算されていないか、GC できることに注意してください。を評価すると、評価は と の間をourLast list3行き来します (コルーチンのようなものです)。ourLastmkList

Haskell コンパイラがどのように機能する傾向があるかについて、「いつ、どのように割り当てが行われるか」というレベルでより正確に把握したい場合は、次の情報が役立ちます。

グラフ削減の観点から遅延評価がどのように機能するかについての一般的な理解 (たとえば、この記事) は役に立ちます。

于 2012-11-28T12:22:22.823 に答える
2

here で説明されているように、ヒーププロファイリングを行います。このためには、プロファイリング ライブラリを cabal でインストールする必要があります。説明はかなり包括的で、従うのは簡単です。

于 2012-11-28T11:16:06.963 に答える