Утечка пространства с избыточным использованием seq в интерпретаторе GHC

Question

Я набираю этот код в интерпретаторе, и память быстро расходуется:

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

Я не могу понять, почему это требует больше, чем O(1) место. Если я только что (что должно быть то же самое, потому что Show заставляет слабую голову нормальную форму, поэтому seq является избыточным?):

last [1..10^7]

... это работает отлично.

Я не могу воспроизвести эту ситуацию за пределами переводчика.

Что тут происходит?

---

Вот несколько тестов: http://hpaste.org/69234

Что следует отметить:

• Запустив интерпретатор, я загружаю wtf.hs без его компиляции и набираю wtf<n> в ghci.
• Компилируя, я делаю ghc --make wtf.hs && ./wtf,
• last можно заменить на sum со строгим аккумулятором или функцией, которая находит элемент max в списке, и утечка пространства все еще происходит
• Я не видел такого поведения при использовании $! вместо seq,
• Я пытался добавить манекен () параметр, потому что я думал, может быть, это проблема CAF. Ничего не меняет.
• Это, вероятно, не проблема с функциями на Enumпотому что я могу воспроизвести поведение с wtf5 и позже, которые не используют Enum совсем.
• Это, вероятно, не проблема с Num, Int, или же Integerпотому что я могу воспроизвести поведение без них в wtf14 а также wtf16,

Я попытался воспроизвести проблему с арифметикой Пеано, чтобы вывести списки и целые числа из уравнения (извлекая их в конце 10^9), но столкнулся с другими проблемами совместного использования / утечки пространства, которые я не понимаю при попытке реализовать *,

Answer 1

Нам нужно взглянуть на случай enumFromTo для целых чисел, и последний:

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

Это определено в GHC.Enum как:

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

где

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

а также

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 полностью ленивый, как и ожидалось.

Для класса Integer Enum у нас есть строгий аккумулятор (явно) для enumFrom, В ограниченном случае (например, [1..n]), это вызывает enumDeltaToInteger а затем в up_list, который использует рабочий, чтобы развернуть список, пока его предел не будет достигнут.

Но up_list строго в x в go помощник (см. сравнение с lim).

При запуске в GHCi ничего из этого не оптимизируется, приводя к наивным вызовам enumFromTo перед возвратом (),

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.[] @ ())))

Итак, почему мы сохраняем список в seq дело, а не в обычном случае? Обычный случай хорошо работает в постоянном пространстве, полагаясь на лень enumFromTo за Integer и для last, Ядро GHCi для этого случая выглядит так:

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.[] @ ())))

Таким образом, они почти идентичны, с различиями:

• в seq версия, last (enumFromTo ..) вынужден внутри case,
• в обычной версии это ленивый let,
• в seq версия, значение вычисляется, затем отбрасывается, получая () - ничего не смотрит на результат
• в обычном случае это проверяется и показывается.

Странно, что в этом нет ничего волшебного:

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

это заставляет его сохранять ценности.

Как видим, реализация up_list строг в своем аккумуляторе (так как он сравнивается с limа список разворачивается лениво - так last должен быть в состоянии потреблять его в постоянном пространстве). Написание выражения от руки подтверждает это.

Выполнение профиля кучи выполнения ghci показывает весь сохраняемый список:

что говорит нам, по крайней мере, что это не цепочка громов, а весь список строится строго и держится, пока не будет отброшен.

Так что загадка в том, что держит аргумент списка last в ghci, а не в ghc?

Я подозреваю некоторые внутренние (или тонкие) детали ghci - думаю, это стоит билета ghci.

Answer 2

Я думаю, что @nm прав. Ничто не заставляет значение в списке, так что thunk 1+1+1+1+... в конечном итоге убивает пространство.

Я быстро проведу тест.