Dlaczego s ++ t nie doprowadzić do przepełnienia stosu dla dużych s?

Question

Zastanawiam się dlaczego

Prelude> head $ reverse $ [1..10000000] ++ [99] 
99 

nie prowadzi do błędu przepełnienia stosu. ++ w preludium wydaje się proste i non-tail-rekurencyjne:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

EDIT: Początkowo myślałem, że problem ma coś wspólnego ze sposobem ++ jest zdefiniowany w preludium, zwłaszcza z przepisywania zasady, stąd pytanie kontynuowane, jak poniżej. Dyskusja pokazała mi, że tak nie jest. Teraz myślę, że jakiś leniwy efekt oceny powoduje, że kod działa bez przepełnienia stosu, ale nie wiem, jak to zrobić.

Więc po prostu z tym, należy go uruchomić na przepełnienie stosu, prawda? Więc postać to chyba ma coś z magii, który następuje ghc definicję ++

{- # Reguły "++" [~ 1] forall xs ys. XS ++ ys = Augment (\ c n -> foldr c n xs) ys # -}

* Czy to, co pomaga uniknąć przepełnienia stosu? Może ktoś podać kilka podpowiedzi dla tego, co dzieje się w tym kawałku kodu **

Answer 1

nie przepełnienie stosu - nawet w tłumacza, gdzie istnieją żadne optymalizacje i żadnych reguł przepisywania - ponieważ nie używa stosu.

Spójrz na definicji (++), na przykład ,:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

Kluczową rzeczą jest x : (xs ++ ys) - to znaczy, że jest chroniony przez rekurencji (:) "przeciw" konstruktora. Ponieważ Haskell jest leniwy, alokuje thunk dla operacji cons, a wywołanie rekursywne przechodzi na to (przydzielane sterty) thunk. A zatem przydzielanie sterty to teraz alokacja sterty, która może się nieco rozwinąć. A więc wszystko to odbywa się na dużej liście, przydzielając nowe obiekty na kupie, aby zastąpić te, które krąży. Łatwo!

„reverse” jest nieco inna:

reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 

To rekursywne ogona, funkcję akumulatora stylu więc ponownie, to przydziela się na stosie.

Tak więc, funkcje polegają na użyciu komórek na kupie, zamiast na stosie, a więc nie ma przepełnienia stosu.

Aby naprawdę paznokci to, spojrzeć na statystyki uruchomieniowych z VM GC:

$ time ./B +RTS -s 
99 

     833 MB total memory in use (13 MB lost due to fragmentation) 
     Generation 0: 3054 collections,  0 parallel, 0.99s, 1.00s elapsed 
     %GC time  82.2% (85.8% elapsed) 

Jest twoja wielka lista - jest ona przydzielona na stercie i spędzamy 80% czasu czyszczenia minusy węzły utworzone przez (++).

Lekcja: często można wymieniać stosy na kupę.

Answer 2

EDIT: Poniższa odpowiedź jest całkowicie bez znaczenia, jeśli nie wręcz błędne. Don Stewart, który demonstruje, że w rzeczywistości jest on leniwy, ma odpowiednie wyjaśnienie.

---

Jeśli prowadzisz ghc -ddump-simpl, zobaczysz, że funkcje wykorzystywane są GHC.Base.++ i GHC.List.reverse. Te funkcje zostały zaprojektowane tak, aby nie przepełniały stosu na dużych listach. To, co widzisz w Prelude, to "implementacja referencyjna", a nie kod, który jest faktycznie skompilowany.

Oto niektóre kodu I kopany z dystrybucji źródłowej GHC:

reverse     :: [a] -> [a] 
#ifdef USE_REPORT_PRELUDE 
reverse     = foldl (flip (:)) [] 
#else 
reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 
#endif 

a to:

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

{-# RULES 
"++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)  ys 
    #-} 

W pierwszym przypadku, powinno być jasne, co się dzieje. W drugim, jestem trochę rozmyta w sprawie zasad przepisywania ...

Answer 3

++ w preludium wydaje się proste i non-tail-rekurencyjne ... Więc po prostu z tym, należy go uruchomić w przepełnienie stosu, prawda?

Not-tail-rekurencyjne jest często lepsze niż ogon rekurencyjnej w Haskell, ponieważ nie-tail-rekurencyjne rzeczy może być leniwy. Definicja, którą tam podasz, jest znacznie lepsza niż rekursywna, ponieważ rekursywna rekurencja utrzymywałaby powtarzalność i generowała całą listę, nawet jeśli potrzebujesz tylko pierwszego elementu; mając na uwadze, że rekurencyjny non-tail wykonywałby tylko tyle pracy, ile potrzeba.