Требуется ли Haskell сборщик мусора?

Мне любопытно, почему реализации Haskell используют GC.

Я не могу придумать случай, когда GC был бы необходим на чистом языке. Это просто оптимизация для уменьшения копирования, или это действительно необходимо?

Я ищу пример кода, который будет протекать, если GC не присутствовал.

8 111
haskell garbage-collection

8 ответов:

как уже указывали другие, Хаскелл требует автоматическое,динамический управление памятью: автоматическое управление памятью необходимо, потому что ручное управление памятью небезопасно; динамическое управление памятью необходимо, потому что для некоторых программ Время жизни объекта может быть определено только во время выполнения.

например, рассмотрим следующую программу:

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

в этой программе, список [1..1000] должны храниться в память до тех пор, пока пользователь не наберет "очистить"; так что время жизни этого должны определяется динамически, и именно поэтому необходимо динамическое управление памятью.

таким образом, в этом смысле автоматическое динамическое выделение памяти необходимо, и на практике это означает:да, Haskell требует сборщика мусора, так как сборщик мусора-это высокопроизводительный автоматический динамический менеджер памяти.

однако...

хотя и мусор коллектор необходим, мы могли бы попытаться найти некоторые особые случаи, когда компилятор может использовать более дешевую схему управления памятью, чем сбор мусора. Например, учитывая

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

мы можем надеяться, что компилятор обнаружит это x2 можно безопасно освободить, когда f возвращает (вместо того, чтобы ждать, пока сборщик мусора освободит x2). По сути, мы просим, чтобы компилятор выполнял Escape-анализ преобразовать выделение в мусор-собранная куча до распределения в стеке везде, где это возможно.

это не слишком неразумно просить:МХК Хаскеле компилятор делает это, хотя GHC не делает. Саймон Марлоу говорит что сборщик мусора поколения GHC делает анализ побега главным образом ненужным.

jhc фактически использует сложную форму анализа побега, известную как области вывода. Рассмотрим

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

в этом случае, упрощенный анализ побега придет к выводу, что x2 убегает от f (потому что он возвращается в кортеже), и, следовательно,x2 должно быть выделено в куче мусора. Вывод региона, с другой стороны, способен обнаружить, что x2 может быть освобожден, когда g возвращает; идея здесь заключается в том, что x2 должны быть выделены в g's регион, а не f ' s регион.

за Хаскелл

хотя вывод региона полезен в некоторых случаях, как обсуждалось выше, кажется, что его трудно эффективно согласовать с ленивой оценкой (см. Эдвард Kmett это и Саймон Пейтон Джонс' комментарии). Например, рассмотрим

f :: Integer -> Integer
f n = product [1..n]

может возникнуть соблазн выделить список [1..n] на стеке и освободить его после f возвращается, но это было бы катастрофично: это изменило бы f от использования O(1) память(под сборкой мусора) в o (n) память.

в 1990-х и начале 2000-х годов была проделана большая работа по выведению региона для строго функциональный язык ML. Мадс Тофте, Ларс Биркедал, Мартин Эльсман, Нильс Халленберг написали вполне читаемый ретроспектива о своей работе по региональному умозаключению, большую часть которой они интегрировали в компилятор MLKit. Они экспериментировали с чисто региональным управлением памятью (т. е. нет сборщик мусора), а также управление гибридной областью/сборкой мусора и сообщили, что их тестовые программы работают "в 10 раз быстрее и в 4 раза медленнее", чем чистые версии, собранные с помощью мусора.

211

давайте возьмем тривиальный пример. Учитывая это

f (x, y)

вам нужно выделить пару (x, y) где-то перед вызовом f. Когда вы можете освободить эту пару? Ты даже не представляешь. Он не может быть освобожден, когда f возвращает, потому что f возможно, поставил пару в структуру данных (например,f p = [p]), поэтому время жизни пары может быть больше, чем возвращения из f. Теперь, скажем, что пара была помещена в список, может тот, кто разбирает список освободить пару? Нет, потому что пара может быть общей (например, let p = (x, y) in (f p, p)). Поэтому очень трудно сказать, когда пара может быть освобождена.

то же самое относится почти ко всем распределениям в Haskell. Тем не менее, возможно иметь анализ (анализ региона), который дает верхнюю границу времени жизни. Это работает достаточно хорошо в строгих языках, но менее так в ленивых языках (ленивые языки, как правило, делают намного больше мутаций, чем строгие языки в реализация.)

поэтому я хотел бы повернуть вопрос вокруг. Как вы думаете, почему Haskell не нужен GC. Как бы вы предложили выделение памяти для выполнения?

25

Haskell считается чистым отчасти потому, что побочные эффекты функций учитываются в сигнатуре типа. Поэтому, если функция имеет побочный эффект печати чего-то, должен быть IO где-то в тип возвращаемого значения.

но есть функция, которая используется неявно везде в Haskell и чья сигнатура типа не учитывает, что в некотором смысле является стороной эффект. А именно функция, которая копирует некоторые данные и дает вам две версии обратно. Под капотом это может работать либо буквально, дублируя данные в памяти, либо "виртуально", увеличивая долг, который должен быть возвращен позже.

можно создавать языки с еще более ограничительными системами типов (чисто "линейными"), которые запрещают функцию копирования. С точки зрения программиста на таком языке, Хаскелл выглядит немного грязным.

На самом деле, очистить, родственник Haskell, имеет линейные (более строго: уникальные) типы, и это может дать некоторое представление о том, как было бы запретить копирование. Но Clean по-прежнему позволяет копировать для "не уникальных" типов.

много исследования в этой области, и если вы достаточно Google, вы найдете примеры чистого линейного кода, который не требует сбора мусора. Вы найдете все виды систем типов, которые могут сигнализировать компилятору, какая память может быть использована позволяя компилятору устранить некоторые из GC.

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

также интересно сравнить с Forth (или другими языками на основе стека), которые имеют явные операции DUP, которые дают понять, когда происходит дублирование.

другой (более абстрактный) способ мышления об этом состоит в том, чтобы отметить, что Хаскелл построен из просто типизированного лямбда-исчисления, которое основано на теории декартовых замкнутых категорий и что такие категории оснащены диагональной функцией diag :: X -> (X, X). Язык, основанный на другом классе категорий, может не иметь такого понятия.

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

15

стандартные методы реализации, применяемые к Haskell, фактически требуют GC moreso, чем большинство других языков, поскольку они никогда не мутируют предыдущие значения, вместо этого создавая новые, измененные значения на основе предыдущих. Поскольку это означает, что программа постоянно выделяет и использует больше памяти, большое количество значений будет отбрасываться с течением времени.

вот почему программы GHC, как правило, имеют такие высокие общие показатели распределения (от гигабайт до терабайт): они постоянно выделяют память, и только благодаря эффективному GC они восстанавливают ее перед запуском.

14

Если язык (любой язык) позволяет выделять объекты динамически, то есть три практических способа справиться с управлением памятью:

  1. язык может позволить вам выделять память только в стеке или при запуске. Но эти ограничения серьезно ограничивают виды вычислений, которые может выполнять программа. (На практике. Теоретически вы можете эмулировать динамические структуры данных в (скажем) Fortran, представляя их в большом массиве. Это УЖАСНЫЙ... и не имеет отношения к этой дискуссии.)

  2. язык может обеспечить явное free или dispose механизм. Но это зависит от программиста, чтобы получить это право. Любая ошибка в управлении хранилищем может привести к утечке памяти ... или еще хуже.

  3. язык (или более строго, реализация языка) может обеспечить автоматический менеджер хранения для динамически выделенного хранилища; т. е. некоторая форма мусора коллекционер.

единственный другой вариант-никогда не восстанавливать динамически выделенное хранилище. Это не практичное решение, за исключением небольших программ, выполняющих небольшие вычисления.

применяя это к Haskell, язык не имеет ограничения 1., и никакая ручная деятельность deallocation согласно 2. Поэтому, чтобы быть пригодным для нетривиальных вещей, реализация Haskell должна включать сборщик мусора.

Я не могу придумать случай, когда GC был бы необходим на чистом языке.

предположительно вы имеете в виду чистый функциональный язык.

ответ заключается в том, что GC требуется под капотом, чтобы восстановить объекты кучи, которые должен создать язык. Например.

  • чистая функция должна создавать объекты кучи, потому что в некоторых случаях она должна возвращать их. Это означает, что они не могут быть выделены на стек.

  • тот факт, что могут быть циклы (в результате let rec например) означает, что подход подсчета ссылок не будет работать для объектов кучи.

  • тогда есть функция закрытия ... которые также не могут быть выделены в стеке, потому что у них есть время жизни, которое (как правило) не зависит от того кадра стека, в котором они были созданы.

Я ищу пример кода, который будет протекать, если GC не присутствовал.

почти любой пример, связанный с закрытиями или графовыми структурами данных, будет протекать в этих условиях.

10

сборщик мусора никогда не требуется, если у вас есть достаточно памяти. Однако на самом деле у нас нет бесконечной памяти, и поэтому нам нужен какой-то метод для восстановления памяти, которая больше не нужна. В нечистых языках, таких как C, вы можете явно заявить, что вы сделали с некоторой памятью, чтобы освободить ее, но это операция мутации (память, которую вы только что освободили, больше не безопасна для чтения), поэтому вы не можете использовать этот подход на чистом языке. Так что это либо как-то статически анализировать, где вы может освободить память (вероятно, невозможно в общем случае), утечка памяти, как сито (отлично работает, пока вы не закончите), или использовать GC.

8

Haskell-это нестрогий язык программирования, но большинство реализаций используют вызов по необходимости (лень) для реализации нестрогости. В call-by-need вы только оцениваете материал, когда он достигается во время выполнения, используя механизм "thunks" (выражения, которые ждут оценки, а затем перезаписывают себя, оставаясь видимыми для их значения, которое будет повторно использоваться при необходимости).

Итак, если вы реализуете свой язык лениво, используя thunks, вы отложили все рассуждения об объекте жизни до последнего момента, который является временем выполнения. Поскольку вы теперь ничего не знаете о жизни, единственное, что вы можете разумно сделать, это собирать мусор...

1

GC "должен иметь" в чистых языках FP. Зачем? Операции alloc и free нечисты! И вторая причина заключается в том, что неизменяемые рекурсивные структуры данных нуждаются в GC для существования, потому что обратное связывание создает абстрактные и недостижимые структуры для человеческого разума. Конечно, обратная связь-это благо, потому что копирование структур, которые ее используют, очень дешево.

в любом случае, если вы мне не верите, просто попробуйте реализовать язык FP, и вы увидите, что я право.

EDIT: я забыл. Лень-это АД без GC. Не веришь мне? Просто попробуйте без GC, например, C++. Вот увидишь ... вещи

0