Как работает язык без стеков?
Я слышал о языках без стеков. Однако я понятия не имею, как такой язык будет реализован. Может кто-нибудь объяснить?
8 ответов
Современные операционные системы (Windows, Linux) работают с тем, что я называю "моделью большого стека". И эта модель иногда ошибочна и мотивирует потребность в языках без стеков.
"Модель большого стека" предполагает, что скомпилированная программа будет выделять "кадры стека" для вызовов функций в непрерывной области памяти, используя машинные инструкции для очень быстрой корректировки регистров, содержащих указатель стека (и необязательный указатель фрейма стека). Это приводит к быстрому вызову / возврату функции за счет наличия большой непрерывной области для стека. Поскольку 99,99% всех программ, работающих под управлением этих современных ОС, хорошо работают с моделью большого стека, компиляторы, загрузчики и даже ОС "знают" об этой области стека.
Одна из распространенных проблем, с которыми сталкиваются все такие приложения, - "насколько большим должен быть мой стек?", Поскольку память очень дешевая, в основном получается то, что для стека выделяется большой кусок (по умолчанию MS равен 1 Мб), и типичная структура вызова приложения никогда не приближается к его использованию. Но если приложение использует все это, оно умирает с недопустимой ссылкой на память ("Извини, Дейв, я не могу этого сделать") из-за того, что оно достигло конца своего стека.
Большинство так называемых языков без стеков не являются на самом деле без стеков. Они просто не используют непрерывный стек, предоставляемый этими системами. Вместо этого они выделяют кадр стека из кучи при каждом вызове функции. Стоимость вызова функции несколько возрастает; если функции обычно сложные или язык интерпретирующий, эти дополнительные расходы незначительны. (Можно также определить группы обеспечения доступности баз данных в графе вызовов программ и выделить сегмент кучи для охвата всей группы обеспечения доступности баз данных; таким образом вы получаете как распределение кучи, так и скорость классических вызовов функций большого стека для всех вызовов внутри группы вызовов).
Есть несколько причин для использования выделения кучи для стековых фреймов:
1) Если программа выполняет глубокую рекурсию в зависимости от конкретной проблемы, которую она решает, очень трудно заранее выделить область "большого стека", поскольку необходимый размер неизвестен. Можно неуклюже организовать вызовы функций, чтобы проверить, достаточно ли осталось стека, а если нет, перераспределить больший кусок, скопировать старый стек и перенастроить все указатели в стек; это так неловко, что я не знаю ни одной реализации. Выделение стековых фреймов означает, что приложению никогда не придется извиняться, пока не останется буквально выделенной памяти.
2) Программа разветвляется на подзадачи. Каждая подзадача требует своего собственного стека и поэтому не может использовать один предоставленный "большой стек". Итак, нужно выделить стеки для каждой подзадачи. Если у вас есть тысячи возможных подзадач, теперь вам могут понадобиться тысячи "больших стеков", и потребность в памяти внезапно становится нелепой. Выделение кадров стека решает эту проблему. Часто "стеки" подзадач относятся к родительским задачам для реализации лексической области видимости; в качестве ответвления подзадач создается дерево "подстаков", которое называется "стек кактусов".
3) У вашего языка есть продолжения. Они требуют, чтобы данные в лексической области видимости текущей функции каким-то образом были сохранены для последующего повторного использования. Это может быть реализовано путем копирования кадров родительского стека, подъема вверх по стеку кактусов и продолжения.
Язык программирования PARLANSE, который я реализовал, выполняет 1) и 2). Я работаю над 3).
У Stackless Python все еще есть стек Python (хотя он может иметь оптимизацию хвостовых вызовов и другие приемы слияния фреймов вызовов), но он полностью отделен от стека C интерпретатора.
У Haskell (как это обычно реализуется) нет стека вызовов; оценка основана на сокращении графика.
На http://www.linux-mag.com/cache/7373/1.html есть хорошая статья о языковой платформе Parrot. Parrot не использует стек для вызовов, и эта статья немного объясняет эту технику.
Назовите меня древним, но я могу вспомнить, когда стандарты FORTRAN и COBOL не поддерживали рекурсивные вызовы, и поэтому не требовали стека. Действительно, я вспоминаю реализации для машин серии CDC 6000, где не было стека, и FORTRAN делал бы странные вещи, если бы вы попытались вызвать подпрограмму рекурсивно.
Для записи вместо стека вызовов набор команд серии CDC 6000 использовал инструкцию RJ для вызова подпрограммы. Это сохранило текущее значение ПК в целевом местоположении вызова и затем ответвляется в местоположение, следующее за ним. В конце подпрограмма выполнит косвенный переход к месту назначения вызова. После этого перезагруженный сохраненный компьютер, по сути, возвращается к звонящему.
Очевидно, что это не работает с рекурсивными вызовами. (И я помню, что компилятор CDC FORTRAN IV будет генерировать неработающий код, если вы попытаетесь выполнить рекурсию...)
В средах без стеков, с которыми я более или менее знаком (машина Тьюринга, сборка и Brainfuck), принято реализовывать свой собственный стек. Нет ничего фундаментального в том, что в язык встроен стек.
В наиболее практичной из них, сборка, вы просто выбираете область памяти, доступную вам, устанавливаете регистр стека так, чтобы он указывал на дно, а затем увеличиваете или уменьшаете его для реализации ваших нажатий и всплывающих окон.
РЕДАКТИРОВАТЬ: Я знаю, что некоторые архитектуры имеют выделенные стеки, но они не нужны.
Существует простое для понимания описание продолжений этой статьи: http://www.defmacro.org/ramblings/fp.html
Продолжения - это то, что вы можете передать в функцию на языке, основанном на стеке, но которое также может быть использовано собственной семантикой языка, чтобы сделать его "стековым". Конечно, стек все еще там, но, как описала Ира Бакстер, это не один большой непрерывный сегмент.
Скажем, вы хотели реализовать C без стека. Первое, что нужно понять, это то, что для этого не требуется стек
a == b
Но так ли это?
isequal(a, b) { return a == b; }
Нет. Потому что умный компилятор встроит вызовы isequalпревращая их в a == b, Так почему бы просто не встроить все? Конечно, вы будете генерировать больше кода, но если избавление от стека стоит того, то это легко с небольшим компромиссом.
Как насчет рекурсии? Нет проблем. Хвостово-рекурсивная функция типа:
bang(x) { return x == 1 ? 1 : x * bang(x-1); }
Все еще может быть встроенным, потому что на самом деле это просто скрытый цикл for:
bang(x) {
for(int i = x; i >=1; i--) x *= x-1;
return x;
}
Теоретически, действительно умный компилятор может понять это за вас. Но менее умный мог все еще сгладить это как goto:
ax = x;
NOTDONE:
if(ax > 1) {
x = x*(--ax);
goto NOTDONE;
}
Есть один случай, когда вы должны сделать небольшую сделку. Это не может быть встроено:
fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }
Stackless C просто не может этого сделать. Ты много сдаешься? На самом деле, нет. Это что-то нормальное, С тоже не очень хорошо справляется. Если ты мне не веришь, просто позвони fib(1000) и посмотрим, что происходит с вашим драгоценным компьютером.
Пожалуйста, не стесняйтесь исправлять меня, если я ошибаюсь, но я думаю, что выделение памяти в куче для каждого фрейма вызова функции приведет к чрезмерному перегрузке памяти. Операционная система все-таки должна управлять этой памятью. Я бы подумал, что способ избежать этой перегрузки памяти будет кеш для фреймов вызовов. Так что, если вам все равно нужен кеш, мы можем также сделать его конгресным в памяти и назвать его стеком.