Przestrzeń wyciek z nadmiarowym wykorzystania seq w GHC tłumacza

Question

mam wpisać ten kod do interpretera i pamięć jest szybko zużywany:

last [1..10^7] `seq`() 

Nie mogę zrozumieć, dlaczego to wymaga więcej niż O (1) przestrzeni. Jeśli zrobić właśnie (która powinna być taka sama, bo Pokaż sił słabej głowy postaci normalnej, więc nast jest zbędny):

last [1..10^7] 

... to działa dobrze.

Nie mogę odtworzyć tej sytuacji poza tłumaczem.

Co tu się dzieje?

---

Oto niektóre przypadki testowe: http://hpaste.org/69234

warte Uwaga:

• Uruchamiając w tłumacza, załadować wtf.hs bez kompilowania go, a następnie wpisz wtf<n> w ghci.
• Kompilując, wykonuję ghc --make wtf.hs && ./wtf.
• last może być zastąpiony przez sum ze ścisłym akumulatora lub funkcją, która znajduje się z max element listy i nieszczelności przestrzeni nadal zdarza
• Nie widać tego problemu przy użyciu $! zamiast seq.
• Próbowałem dodać parametr dummy (), ponieważ uważam, że może to problem CAF. Nic nie zmienia.
• To prawdopodobnie nie jest problem z funkcjami na Enum, ponieważ mogę odtworzyć zachowanie z wtf5 i późniejszymi, które w ogóle nie używają Enum.
• To prawdopodobnie nie jest problem z Num, Int lub Integer, ponieważ mogę odtworzyć zachowanie bez nich w wtf14 i wtf16.

Próbowałem odtwarzając problem z arytmetyki Peano wziąć list i całkowite z równania (pobierania na koniec 10^9), ale wpadł innych problemów dzielenie/miejsca wycieku nie rozumiem podczas próby wdrożenia *.

Answer 1

Myślę, że @ n.m ma rację. Nic nie wymusza na liście wartości o wartości, więc thunk 1 + 1 + 1 + 1 + ostatecznie zabija przestrzeń.

Zanurzę szybki test.

Answer 2

Musimy patrzeć na wystąpienie enumFromTo za całkowitą, a ostatnia:

last []     = errorEmptyList "last" 
last (x:xs)    = last' x xs 
    where last' y []  = y 
     last' _ (y:ys) = last' y ys 

To jest zdefiniowane w GHC.Enum jako:

enumFrom x    = enumDeltaInteger x 1 
enumFromThen x y  = enumDeltaInteger x (y-x) 
enumFromTo x lim  = enumDeltaToInteger x 1 lim 

gdzie

enumDeltaInteger :: Integer -> Integer -> [Integer] 
enumDeltaInteger x d = x `seq` (x : enumDeltaInteger (x+d) d) 
-- strict accumulator, so 
--  head (drop 1000000 [1 .. ] 
-- works 

i

enumDeltaToInteger :: Integer -> Integer -> Integer -> [Integer] 
enumDeltaToInteger x delta lim 
    | delta >= 0 = up_list x delta lim 
    | otherwise = dn_list x delta lim 

up_list :: Integer -> Integer -> Integer -> [Integer] 
up_list x0 delta lim = go (x0 :: Integer) 
       where 
        go x | x > lim = [] 
         | otherwise = x : go (x+delta) 

last jest całkowicie leniwy, jak oczekiwano.

Dla klasy Integer Enum mamy ścisły akumulator (jawnie) dla enumFrom. W ograniczonym przypadku (na przykład [1..n]) wywołuje enumDeltaToInteger, a następnie up_list, który używa pracownika do rozwinięcia listy, aż do osiągnięcia limitu.

Ale up_list jest ścisłe w x w pomocniku go (patrz porównanie z lim).

Po uruchomieniu w GHCi żadna z tych opcji nie jest zoptymalizowana, co powoduje nieskuteczne wywołania enumFromTo, przed zwróceniem ().

let 
    it_ax6 ::()  
    it_ax6 = 
    case last 
      @ GHC.Integer.Type.Integer 
      (GHC.Enum.enumFromTo 
       @ GHC.Integer.Type.Integer 
       GHC.Num.$fEnumInteger 
       (GHC.Integer.smallInteger 1) 
       (GHC.Real.^ 
       @ GHC.Integer.Type.Integer 
       @ GHC.Integer.Type.Integer 
       GHC.Num.$fNumInteger 
       GHC.Real.$fIntegralInteger 
       (GHC.Integer.smallInteger 10) 
       (GHC.Integer.smallInteger 7))) 
    of _ -> GHC.Unit.() 
in 
    GHC.Base.thenIO 
    @() 
    @ [()] 
    (System.IO.print @() GHC.Show.$fShow() it_ax6) 
    (GHC.Base.returnIO 
     @ [()] (GHC.Types.: @() it_ax6 (GHC.Types.[] @()))) 

Więc dlaczego my zachowując listę w przypadku seq, a nie w zwykłej sprawie? Standardowa obudowa ładnie działa w przestrzeni stałej, polegając na lenistwie enumFromTo dla Integer i dla last. Rdzeń GHCi w tym przypadku wygląda następująco:

let { 
    it_aKj :: GHC.Integer.Type.Integer 
    [LclId, 
    Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False, 
      ConLike=False, Cheap=False, Expandable=False, 
      Guidance=IF_ARGS [] 170 0}] 
    it_aKj = 
    GHC.List.last 
     @ GHC.Integer.Type.Integer 
     (GHC.Enum.enumFromTo 
     @ GHC.Integer.Type.Integer 
     GHC.Num.$fEnumInteger 
     (GHC.Integer.smallInteger 1) 
     (GHC.Real.^ 
      @ GHC.Integer.Type.Integer 
      @ GHC.Integer.Type.Integer 
      GHC.Num.$fNumInteger 
      GHC.Real.$fIntegralInteger 
      (GHC.Integer.smallInteger 10) 
      (GHC.Integer.smallInteger 7))) } in 
GHC.Base.thenIO 
    @() 
    @ [()] 
    (System.IO.print 
    @ GHC.Integer.Type.Integer GHC.Num.$fShowInteger it_aKj) 
    (GHC.Base.returnIO 
    @ [()] 
    (GHC.Types.: 
     @() 
     (it_aKj 
     `cast` (UnsafeCo GHC.Integer.Type.Integer() 
       :: GHC.Integer.Type.Integer ~())) 
     (GHC.Types.[] @()))) 

więc są prawie identyczne, z różnicami są:

• w wersji seq, last (enumFromTo ..) jest zmuszony wewnątrz case.
• w wersji regularnej jest to lazy let.
• w wersji seq wartość obliczana jest następnie wyrzucić, uzyskując () - nic patrzy na skutek
• w zwykłej sprawie, to jest kontrolowane i wyświetlane.

Co jest dziwne jest to, że nie ma nic magicznego:

let x = case last (enumFromTo 1 n) of _ ->() 

sprawia, że ​​zachowują wartości.

Jak widzimy, realizacja up_list jest ścisłe w akumulatorze (ponieważ porównuje przeciwko lim, a lista jest rozłożył się leniwie - tak last powinien móc spożywać go w stałym miejscu). Ręczne wpisanie wyrażenia potwierdza to.

Doing profil sterty wykonanie ghci pokazuje całą listę zatrzymywanych:

który mówi nam przynajmniej, że nie jest to sieć z łącznikami, ale cała lista jest są ściśle zbudowane i trzymane, dopóki nie zostaną odrzucone.

Tajemnica brzmi: co trzyma argument listy na last w ghci, a nie w ghc?

Podejrzewam, że niektóre wewnętrzne (lub subtelne) szczegóły ghci teraz - myślę, że to jest warte biletu ghci.