Мне любопытно, почему в реализациях Haskell используется GC.
Я не могу придумать случай, когда GC понадобится на чистом языке. Это просто оптимизация для сокращения копирования, или это действительно необходимо?
Я ищу пример кода, который бы протекал, если GC отсутствовал.
Как уже отмечалось другими, Haskell требует автоматического, динамического управления памятью: требуется автоматическое управление памятью, поскольку управление ручной памятью небезопасно; динамическое управление памятью необходимо, потому что для некоторых программ время жизни объекта может быть определено только во время выполнения.
Например, рассмотрим следующую программу:
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] должен храниться в памяти до тех пор, пока пользователь не наберет "clear"; поэтому время жизни этого должно определяться динамически, поэтому необходимо динамическое управление памятью.
Итак, в этом смысле необходимо автоматическое распределение динамической памяти, и на практике это означает: да, Haskell требует сборщика мусора, поскольку сбор мусора - это менеджер динамической памяти с высокой производительностью.
Хотя сборщик мусора необходим, мы можем попытаться найти некоторые особые случаи, когда компилятор может использовать более дешевую схему управления памятью, чем сбор мусора. Например, данный
f :: Integer -> Integer
f x = let x2 = x*x in x2*x2
мы могли бы надеяться, что компилятор обнаружит, что x2 можно безопасно освободить, когда возвращается f (а не ждет, когда сборщик мусора освободит x2). По сути, мы просим, чтобы компилятор выполнил анализ утечки, чтобы преобразовать распределения в сборку мусора в распределения в стеке, где это возможно.
Это не слишком необоснованно просить: jhc haskell компилятор делает это, хотя 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, а не в области f.
В то время как вывод о регистре полезен в некоторых случаях, как обсуждалось выше, кажется, что трудно смириться с ленивой оценкой (см. Эдварда Кемта и комментарии Саймона Пейтона Джонса. Например, рассмотрим
f :: Integer -> Integer
f n = product [1..n]
Возможно, у вас возникнет соблазн выделить список [1..n] в стеке и освободить его после возврата f, но это будет катастрофично: это изменит f на использование O (1) памяти (под сборку мусора) к O (n) памяти.
В 1990-х и начале 2000-х годов была проведена обширная работа по выводу региона для строгого функционального языка ML. Мадс Тофте, Ларс Биркедал, Мартин Элсман, Нильс Халленберг написали довольно читаемую ретроспективу о своей работе над выводом из области, большая часть которой они интегрировали в компилятор MLKit. Они экспериментировали с чисто региональным управлением памятью (то есть без сборщика мусора), а также с управлением памятью на основе гибридного региона/мусора и сообщали, что их тестовые программы выполнялись" в 10 раз быстрее и в 4 раза медленнее", чем чистый мусор- собранные версии.
Возьмем тривиальный пример. Учитывая это
f (x, y)
вам нужно выделить пару (x, y) где-то перед вызовом f. Когда вы можете освободить эту пару? Ты понятия не имеешь. Он не может быть освобожден при возврате f, поскольку f мог бы поместить пару в структуру данных (например, f p = [p]), поэтому время жизни пары может быть больше, чем возврат из f. Теперь, скажем, что пара была помещена в список, может ли кто-либо, кто забирает список, освободить пару? Нет, потому что пара может быть разделена (например, let p = (x, y) in (f p, p)). Так что действительно сложно сказать, когда пара может быть освобождена.
То же самое справедливо для почти всех распределений в Haskell. Тем не менее, возможно провести анализ (региональный анализ), который дает верхнюю оценку на время жизни. Это работает достаточно хорошо на строгих языках, но в меньшей степени на ленивых языках (ленивые языки имеют тенденцию делать гораздо больше мутаций, чем строгие языки в реализации).
Поэтому я хотел бы задать вопрос. Почему, по вашему мнению, Haskell не нуждается в GC. Как вы предлагаете выделение памяти?
Ваша интуиция, что это имеет какое-то отношение к чистоте, имеет для нее некоторую правду.
Haskell считается чистым, потому что побочные эффекты функций учитываются в сигнатуре типа. Поэтому, если функция имеет побочный эффект от печати, то в возвращаемом типе должен быть IO.
Но существует функция, которая неявно используется везде в Haskell и чья подпись типа не учитывает, что в некотором смысле является побочным эффектом. А именно функция, которая копирует некоторые данные и возвращает вам две версии. Под капотом это может работать буквально, дублируя данные в памяти или "фактически", увеличивая задолженность, которую нужно вернуть позже.
Возможно создание языков с еще более ограничительными типами (чисто "линейными" ), которые запрещают функцию копирования. С точки зрения программиста на таком языке, Haskell выглядит немного нечистым.
Фактически Clean, родственник Haskell, имеет линейные (более строго: уникальные) типы, и это может дать некоторое представление о том, что это будет как запретить копирование. Но Clean по-прежнему позволяет копировать "не-уникальные" типы.
В этой области существует много исследований, и если вы достаточно Google, вы найдете примеры чистого линейного кода, который не требует сбора мусора. Вы найдете все типы систем типов, которые могут сигнализировать компилятору, какая память может использоваться, позволяя компилятору устранить некоторые из GC.
Существует смысл, в котором квантовые алгоритмы также являются чисто линейными. Каждая операция обратима и поэтому никакие данные не могут быть созданы, скопированы или уничтожены. (Они также линейны в обычном математическом смысле.)
Также интересно сравнить с Forth (или другими языками на основе стека), которые имеют явные операции DUP, которые четко указывают, когда происходит дублирование.
Другой (более абстрактный) способ думать об этом состоит в том, чтобы отметить, что Haskell построен из просто типизированного лямбда-исчисления, основанного на теории декартовых замкнутых категорий и что такие категории снабжены диагональной функциейdiag :: X -> (X, X). Язык, основанный на другом классе категории, может не иметь такой вещи.
Но в целом, чисто линейное программирование слишком сложно, чтобы быть полезным, поэтому мы соглашаемся на GC.
Стандартные методы реализации, применяемые к Haskell, на самом деле требуют GC moreso, чем большинство других языков, поскольку они никогда не мутируют предыдущие значения, вместо этого создают новые измененные значения, основанные на предыдущих. Поскольку это означает, что программа постоянно выделяет и использует больше памяти, большое количество значений будет отбрасываться с течением времени.
Вот почему программы GHC имеют такие высокие общие показатели распределения (от гигабайт до терабайт): они постоянно выделяют память, и только благодаря эффективному GC они восстанавливают его до истечения срока.
Если язык (любой язык) позволяет динамически выделять объекты, то есть три практических способа управления памятью:
Язык может позволить вам выделять память в стеке или при запуске. Но эти ограничения сильно ограничивают виды вычислений, которые может выполнять программа. (На практике. В теории вы можете эмулировать динамические структуры данных в (скажем) Fortran, представляя их в большом массиве. Это УЖАСНО... и не имеет отношения к этому обсуждению.)
Язык может предоставить явный механизм free или dispose. Но это зависит от программиста, чтобы понять это правильно. Любая ошибка в управлении хранилищем может привести к утечке памяти... или еще хуже.
Язык (или, более строго, реализация языка) может обеспечить автоматический менеджер хранения для динамически распределенного хранилища; т.е. некоторая форма сборщика мусора.
Единственный другой вариант - никогда не восстанавливать динамически распределенное хранилище. Это не практическое решение, за исключением небольших программ, выполняющих небольшие вычисления.
Применяя это к Haskell, язык не имеет ограничения на 1., и нет операции ручного освобождения в соответствии с 2. Поэтому, чтобы использовать ее для нетривиальных вещей, реализация Haskell должна включать сборщик мусора.
Я не могу придумать случай, когда GC понадобится на чистом языке.
Предположительно, вы имеете в виду чистый функциональный язык.
Ответ заключается в том, что под капотом требуется GC, чтобы вернуть объекты кучи, которые язык ДОЛЖЕН создать. Например.
Чистая функция должна создавать объекты кучи, потому что в некоторых случаях она должна возвращать их. Это означает, что они не могут быть выделены в стеке.
Тот факт, что могут быть циклы (например, из let rec), означает, что метод подсчета ссылок не будет работать для объектов кучи.
Затем есть закрытие функций... которые также не могут быть выделены в стеке, потому что они имеют время жизни, которое (как правило) не зависит от этого стекового кадра, в котором они были созданы.
Я ищу пример кода, который бы протекал, если GC отсутствовал.
Примерно любой пример, связанный с закрытием или графическими структурами данных, будет протекать в этих условиях.
Сборщик мусора никогда не нужен, если у вас достаточно памяти. Однако на самом деле у нас нет бесконечной памяти, поэтому нам нужен какой-то метод для восстановления памяти, которая больше не нужна. На нечистых языках, таких как C, вы можете явно указать, что вы сделали с некоторой памятью, чтобы освободить его - но это мутирующая операция (освобожденная память больше не безопасна для чтения), поэтому вы не можете использовать этот подход в чистый язык. Поэтому он либо как-то статически анализирует, где вы можете освободить память (возможно, невозможно в общем случае), утечка памяти, как сито (отлично работает, пока вы не закончите), или используйте GC.
Haskell - это нестрогий язык программирования, но большинство реализаций используют по требованию (лень) для реализации нестрогости. При необходимости по вызову вы оцениваете материал только тогда, когда он достигнут во время выполнения, используя механизм "thunks" (выражения, которые ждут, чтобы их оценивали, а затем перезаписывали, оставаясь видимыми для повторного использования их значения при необходимости).
Итак, если вы лениво реализуете свой язык с помощью thunks, вы отложили все рассуждения о времени жизни объекта до последнего момента, который является временем выполнения. Поскольку вы ничего не знаете о жизни, единственное, что вы можете разумно сделать, это сбор мусора...
GC "должен иметь" на чистых языках FP. Зачем? Операции распределяются и освобождаются нечисто! И вторая причина заключается в том, что неизменяемые рекурсивные структуры данных нуждаются в GC для существования, потому что обратная связь создает заумные и недостижимые структуры для человеческого разума. Конечно, обратная связь - это благословение, потому что копирование структур, которые его используют, очень дешево.
В любом случае, если вы мне не верите, просто попробуйте реализовать язык FP, и вы увидите, что я прав.
EDIT: Я забыл. Лень - это HELL без GC. Не верьте мне? Просто попробуйте его без GC в, например, С++. Вы увидите... вещи