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

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

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 со строгим аккумулятором или функцией, которая находит максимальный элемент в списке, а утечка пространства все равно происходит
Я не видел этого поведения при использовании $! вместо seq.
Я попытался добавить параметр dummy (), потому что я подумал, что это проблема CAF. Ничего не изменяет.
Вероятно, это не проблема с функциями на Enum, потому что я могу воспроизвести поведение с помощью wtf5 и более поздних версий, которые вообще не используют Enum.
Вероятно, это не проблема с Num, Int или Integer, потому что я могу воспроизвести поведение без них в wtf14 и wtf16.

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

Ответ 1

Нам нужно посмотреть экземпляр enumFromTo для Integer и last:

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, а не в обычном случае? Обычный случай отлично работает в пространстве const, полагаясь на лень 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.

Ответ 2

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

Я выпью быстрый тест.