Как реализовать замыкания без gc?

Question

Я создаю язык. Во-первых, я хочу решить, какой код генерировать. Язык будет иметь лексические замыкания и наследование на основе прототипов, подобное javascript. Но я не фанат gc и стараюсь избегать как можно больше. Итак, вопрос: существует ли элегантный способ реализовать замыкания, не прибегая к выделению кадра стека в куче и предоставлению его сборщику мусора?

Мои первые мысли:

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

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

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

Answer 1

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

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

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

Короткая версия, у вас есть три основных варианта:

• выделяет замыкания в стеке и не разрешает их использование после выхода из их содержащей функции.
• выделяет замыкания в куче и использует какую-то сборку мусора.
• проводите оригинальные исследования, возможно, начиная с того, что есть у ML, Cyclone и т. Д.

Answer 2

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

Я считаю, что для полной поддержки замыканий действительно требуется GC, но в некоторых особых случаях выделение стека является безопасным. Определение этих особых случаев требует некоторого анализа побега. Я предлагаю вам взглянуть на документы на языке BitC , такие как Реализация замыкания в BitC . (Хотя я сомневаюсь, что документы отражают текущие планы.) У разработчиков BitC была та же проблема, что и у вас. Они решили реализовать специальный режим не для сбора для компилятора, который запрещает все замыкания, которые могут выйти. Если включено, это значительно ограничит язык. Однако эта функция еще не реализована.

Я бы посоветовал вам использовать коллектор - это самый элегантный способ. Также следует учитывать, что хорошо собранный сборщик мусора выделяет память быстрее, чем malloc. Пользователи BitC действительно ценят производительность, и они все еще думают, что GC подходит даже для большинства частей их операционной системы, Coyotos. Вы можете перенести недостатки, используя простые средства:

• создает только минимальное количество мусора
• пусть программист управляет коллектором
• оптимизировать использование стека / кучи с помощью escape-анализа
• использовать инкрементный или параллельный коллектор
• если возможно, разделите кучу, как Эрланг

Многие боятся сборщиков мусора из-за своего опыта работы с Java. У Java фантастический сборщик, но приложения, написанные на Java, имеют проблемы с производительностью из-за огромного количества создаваемого мусора. Кроме того, раздутая среда выполнения и необычная JIT-компиляция не очень хорошая идея для настольных приложений из-за более длительного времени запуска и отклика.

Answer 3

Эта ветка может помочь, хотя некоторые ответы здесь отражают ответы там уже.

Один постер говорит о хорошем:

Кажется, вы хотите сборку мусора для замыканий "при отсутствии настоящей сборки мусора". Обратите внимание, что замыкания могут быть использованы для реализации минусов. Так твой вопрос вроде бы про сборку мусора »при отсутствии Сборка мусора »- есть богатая сопутствующая литература. Ограничение проблемы замыканиями на самом деле не меняет ее.

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

Итак, мой вопрос отражает некоторые другие здесь - почему вы не хотите внедрять GC? Простая метка + развертка или остановка + копирование занимает около 2-300 строк кода (схемы), и это не так уж плохо с точки зрения программирования. С точки зрения замедления ваших программ:

1. Вы можете реализовать более сложный GC, который имеет лучшую производительность.
2. Подумайте только, от каких программ утечки памяти на вашем языке не пострадает.
3. Кодирование с доступным ГХ - это благословение. (Вспомните C #, Java, Python, Perl и т. Д. Против C ++ или C).

Answer 4

Используйте подсчет ссылок и собирайте циклы мусора (мне это не очень нравится)

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

Answer 5

Спецификация C ++ 0x определяет лямбды без сборки мусора. Короче говоря, спецификация допускает недетерминированное поведение в случаях, когда лямбда-замыкание содержит ссылки, которые больше не действительны. Например (псевдосинтаксис):

(int)=>int create_lambda(int a)
{
    return { (int x) => x + a }
}

create_lambda(5)(4)    // undefined result

Лямбда в этом примере относится к переменной (a), которая размещается в стеке. Тем не менее, этот кадр стека был вытолкнут и не обязательно доступен после возврата из функции. В этом случае он, вероятно, сработает и вернет 9 в результате (при условии нормальной семантики компилятора), но нет способа гарантировать это.

Если вы избегаете сборки мусора, то я предполагаю, что вы также разрешаете явное распределение кучи и стека и (возможно) указатели. Если это так, то вы можете делать то же самое, что и C ++, и просто предполагать, что разработчики, использующие ваш язык, будут достаточно умны, чтобы выявлять проблемы с лямбдами и явно копировать их в кучу (точно так же, как если бы вы возвращали значение, синтезированное в функция).

Answer 6

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

Вы также можете взглянуть на подход C ++ 0x ( N1968 ), хотя, как и следовало ожидать от C ++, он состоит в том, чтобы рассчитывать, что программист определит, что копируется и на что ссылаются, и если если вы ошибетесь, вы получите недопустимый доступ.

Answer 7

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

GC является единственным решением для общего случая.

Answer 8

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

Как вы планируете иметь дело с возвращением предметов? Они должны быть очищены в какой-то момент, что является точно такой же проблемой с замыканиями.

Answer 9

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

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

@ Аллен

Что хорошего в замыкании, если вы не можете использовать его при выходе из содержащей функции? Насколько я понимаю, в этом весь смысл замыканий.

Answer 10

Лучше поздно, чем никогда?

Может показаться вам интересным: Дифференциальное выполнение .

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

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