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

Мне любопытно, почему реализации Haskell используют 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] должен храниться в памяти, пока пользователь не наберет «очистить»; поэтому время жизни этого должно определяться динамически, и поэтому необходимо динамическое управление памятью.

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

Тем не мение...

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

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

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

Это не так уж и неразумно: компилятор 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 регионе России.

За пределами Haskell

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

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 не нуждается в сборке мусора. Как бы вы посоветовали сделать распределение памяти?

В вашей интуиции, что это имеет какое-то отношение к чистоте, есть доля правды.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ заключается в том, что для восстановления объектов кучи, которые ДОЛЖЕН создать язык, требуется сборщик мусора. Например.

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

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

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

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

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

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

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

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

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

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

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