Согласно Википедии, перевод из лямбда-исчисления в комбинаторную логику тривиален. Конкатенативные языки программирования могут полагаться исключительно на стек для распределения памяти.
Что заставляет GHC переводить Haskell на конкатенативный язык программирования, такой как комбинаторная логика, а затем просто используя распределение стека для всего?
Возможно ли выполнить этот перевод и таким образом устранить сбор мусора для таких языков, как Haskell и OCaml? Есть ли недостатки в этом?
Предположим, что у меня есть функция, которая создает связанный список некоторого размера. Размер - это параметр функции.
Вопрос: где мне нужно выделить память для списка? Я не могу выделить его в стеке функций, поскольку он недействителен после выхода из функции. И я не могу выделить его в стеке вызывающего, поскольку я не знаю, сколько памяти мне нужно выделить перед вызовом функции. Поэтому мне нужно выделить его в кучу.
Я думаю, что может быть RAII с использованием ручного управления кучей, но я не вижу, как вообще исключить выделение кучи.
Я не могу вместить все свои мысли в комментарий, поэтому я пишу их здесь.
Нет никакой магии о языках размещения на основе стека. Вам все еще нужно знать, когда ваши данные актуальны, и удалять их, когда они не являются.
Представьте, что у вас есть отдельный стек, и ваша функция имеет контроль, чтобы вставлять и вставлять данные в него. Во-первых, автоматическое управление памятью больше нет, т.е. Функция завершается, но данные не освобождаются автоматически. Во-вторых, если вы используете выделение некоторой памяти, необходимой для поддержки, например. вычисление списка, тогда все это будет перетасовано списком, который вы хотите вернуть. Нет никаких шансов, что вы можете освободить неиспользуемую память (другие списки, деревья или около того), так как у вас есть только операции push и pop. Если у вас есть другие операции, то в чем разница с кучей?
Как насчет нескольких стеков, а не одного?
Вам нужно выделить их где-нибудь, управлять их ростом и иногда возвращать их. Эти стеки представляют собой отдельные конструкции, которыми вам нужно управлять руками. Нет автоматического управления памятью.
Языки на основе стека одобрены, но забудьте о огромном количестве алгоритмов, которые были изобретены с понятием "получить память откуда-то" и "вернуть память назад", например, хеш-карты, красно-черные деревья, связанные списки, Конечно, мы можем выделить все эти структуры в стеке, но мы не можем освобождать их части, если они больше не нужны.
Как насчет "тривиального" перевода лямбда-исчисления на машину Тьюринга?
Конечно, это тривиально, если ресурсы бесконечны. Математическая теория ничего не разъясняет в отношении сложности времени и памяти таких переведенных конструкций. Он просто утверждает, что обе модели эквивалентны, и все, что мы можем сказать с машиной Тьюринга, мы можем сказать с помощью лямбда-исчисления и наоборот. Нет гарантий, что он может работать с реальными ограничениями.
Конкатенативный язык программирования - каждый бит, способный исчерпать память как функциональный язык программирования.
Фундаментальные адреса сборщиков мусора - освобождение памяти, которая не используется или не известна, используется в стиле стека. Это особенно полезно, когда в исходном коде нет четкого места, которое можно определить как конец срока жизни объекта.
Если вы просто переводите функциональный язык в конкатенативный с только распределением стека, то вы закончите переполнение стека.
На протяжении многих лет наметились различные усилия по сокращению потребности в сборке мусора. Одна интересная (но очень сложная) попытка - это система вывода области, используемая в ML Kit. К сожалению, это немного для большинства программистов, включая меня, для понимания. Я считаю, что другие люди работали над такими системами, поскольку; Я не знаю современного уровня техники.
Вывод заключается в том, что некоторые очень тяжелые машины компилятора, а также тщательная дисциплина программиста и, возможно, специальные аннотации, могут иногда сокращать или устранять необходимость сбора мусора; никакое тривиальное преобразование не собирается делать трюк.