Почему функциональные языки программирования требуют сборки мусора?

14

Что мешает ghc перевести Haskell на конкатенативный язык программирования, такой как комбинаторная логика, а затем просто использовать выделение стека для всего? Согласно Википедии, перевод из лямбда-исчисления в комбинаторную логику тривиален, и конкатенативные языки программирования могут полагаться исключительно на стек при распределении памяти. Реально ли выполнить этот перевод и тем самым исключить сборку мусора для таких языков, как Haskell и ocaml? Есть ли недостатки в этом?

РЕДАКТИРОВАТЬ: перенесено сюда /programming/39440412/why-do-functional-programming-languages-require-garbage-collection

Николай Грасевский
источник
Язык программирования Cat выглядит как пример функции, основанной на стеке.
Петр Пудлак
1
Это не вопрос исследовательского уровня, так как сбор мусора рассматривается на курсах бакалавриата по языкам программирования (а также о необходимости этого). Пожалуйста, перейдите на cs.stackexchange.com
Андрей Бауэр
Моя ошибка. Ты знаешь ответ на мой вопрос?
Николай Грасевский
5
Я думаю, что на этот вопрос нужно дать ответ на уровне исследования, так как я помню, как боролся с ним и во время обучения в аспирантуре: все в языке, подобном Haskell, выглядит как приложение функции, которое живет в стеке. Я думаю, объяснение, почему замыкания необходимы, почему они живут в куче, и, возможно, то, что «данные, выходящие за пределы области действия», имеют к этому отношение, дало бы очень информативный ответ (который я не уверен, что могу дать, К сожалению).
Коди
2
λ

Ответы:

16

Все последующие комментарии основаны на выборе стандартной стратегии реализации с использованием замыканий для представления значений функций и порядка оценки по вызовам:

  1. Для чистого лямбда-исчисления сбор мусора не является необходимым. Это связано с тем, что невозможно сформировать циклы в куче: каждое вновь выделенное значение может содержать только ссылки на ранее выделенные значения, и поэтому граф памяти образует DAG - поэтому для управления памятью достаточно подсчета ссылок.

  2. Большинство реализаций не используют подсчет ссылок по двум причинам.

    1. Они поддерживают форму указателя типа (например, refконструктор типа в ML), и поэтому могут формироваться истинные циклы в куче.
    2. Подсчет ссылок гораздо менее эффективен, чем сборка мусора, так как
      • это требует много дополнительного места для хранения счетчиков ссылок, и
      • обновление счетчиков, как правило, тратится впустую, и
      • Обновление счетчиков создает множество конфликтов записи, что убивает параллельную производительность.
  3. Языки с линейной типизацией могут исключить счетчик ссылок (в основном потому, что счетчики равны 0-1: либо значение имеет единственную ссылку на него, либо оно мертвое и может быть освобождено).

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

  5. Вы можете получить правильную асимптотику, заменив стек «стеком спагетти» (т. Е. Реализуйте этот стек как связанный список в куче, чтобы при необходимости можно было вырезать мертвые кадры).

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

Нил Кришнасвами
источник
2
Не является ли более основной причиной (2), что - даже без наблюдаемых побочных эффектов - реализации хотят иметь эффективный оператор (взаимной) рекурсии, т. Е. Тот, который фактически формирует цикл в куче?
Андреас Россберг
@andreasrossberg: Я думал об этом упомянуть, но не упомянул об этом, так как вы можете использовать Y-комбинатор для рекурсии.
Нил Кришнасвами