Как работает язык без стеков?

Question

Я слышал о языках без стеков. Однако я понятия не имею, как такой язык будет реализован. Может кто-нибудь объяснить?

Answer 1

Современные операционные системы (Windows, Linux) работают с тем, что я называю «моделью большого стека». И эта модель иногда неверна и мотивирует потребность в языках без стеков.

«Модель большого стека» предполагает, что скомпилированная программа будет выделять «кадры стека» для вызовов функций в непрерывной области памяти, используя машинные инструкции для очень быстрой настройки регистров, содержащих указатель стека (и необязательный указатель стека фреймов). Это приводит к быстрому вызову / возврату функции за счет наличия большой непрерывной области для стека. Поскольку 99,99% всех программ, работающих под управлением этих современных ОС, хорошо работают с моделью большого стека, компиляторы, загрузчики и даже ОС «знают» об этой области стека.

Одна общая проблема, с которой сталкиваются все такие приложения: "насколько большим должен быть мой стек?" . Поскольку память очень дешевая, в основном происходит то, что для стека выделяется большой кусок (по умолчанию MS равен 1 МБ), и типичная структура вызова приложения никогда не приближается к его использованию. Но если приложение использует все это, оно умирает с недопустимой ссылкой на память («Простите, Дейв, я не могу этого сделать») из-за того, что оно достигло конца своего стека.

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

Существует несколько причин для использования выделения кучи для стековых фреймов:

1) Если программа выполняет глубокую рекурсию в зависимости от конкретной проблемы, которую она решает, очень трудно заранее выделить область «большого стека», потому что необходимый размер неизвестен. Можно неуклюже организовать вызовы функций, чтобы проверить, достаточно ли осталось стека, а если нет, перераспределить больший кусок, скопировать старый стек и перенастроить все указатели в стек; это так неловко, что я не знаю ни одной реализации. Выделение кадров стека означает, что приложение никогда не должно извиняться, пока не будет Буквально не осталось выделенной памяти.

2) Программа разветвляется на подзадачи. Каждая подзадача требует своего собственного стека и поэтому не может использовать один предоставленный «большой стек». Итак, нужно выделить стеки для каждой подзадачи. Если у вас есть тысячи возможных подзадач, теперь вам могут понадобиться тысячи «больших стеков», и потребность в памяти внезапно становится нелепой. Выделение кадров стека решает эту проблему. Часто «стеки» подзадач относятся к родительским задачам для реализации лексической области видимости; в качестве ответвления подзадач создается дерево «подстаков», которое называется «стек кактусов».

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

Язык программирования PARLANSE , который я реализовал, выполняет 1) и 2). Я работаю над 3).

Answer 2

Stackless Python все еще имеет стек Python (хотя он может иметь оптимизацию хвостовых вызовов и другие приемы слияния кадров вызовов), но он полностью отделен от стека C интерпретатора.

Haskell (как обычно реализуется) не имеет стека вызовов; оценка основана на уменьшении графика .

Answer 3

Есть хорошая статья о языковой платформе Parrot на http://www.linux -mag.com / cache / 7373 / 1.html . Parrot не использует стек для вызовов, и эта статья немного объясняет эту технику.

Answer 4

В средах без стеков, с которыми я более или менее знаком (машина Тьюринга, сборка и Brainfuck), принято реализовывать свой собственный стек. Нет ничего фундаментального в том, что в язык встроен стек.

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

РЕДАКТИРОВАТЬ: Я знаю, что некоторые архитектуры имеют выделенные стеки, но они не нужны.

Answer 5

Скажем, вы хотели реализовать 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) и посмотрите, что произойдет с вашим драгоценным компьютером.

Answer 6

Назовите меня древним, но я могу вспомнить, когда стандарты FORTRAN и COBOL не поддерживали рекурсивные вызовы и, следовательно, не требовали стека. Действительно, я вспоминаю реализации для машин серии CDC 6000, где не было стека, и FORTRAN делал бы странные вещи, если бы вы попытались вызвать подпрограмму рекурсивно.

Для записи вместо стека вызовов набор команд серии CDC 6000 использовал инструкцию RJ для вызова подпрограммы. Это сохранило текущее значение ПК в целевом местоположении вызова и затем ответвляется в местоположение, следующее за ним. В конце подпрограмма выполнит косвенный переход к месту назначения вызова. Это перезагружало сохраненный ПК, фактически возвращая звонящему.

Очевидно, что это не работает с рекурсивными вызовами. (И я помню, что компилятор CDC FORTRAN IV будет генерировать неработающий код, если вы попытаетесь выполнить рекурсию ...)

Answer 7

Существует простое для понимания описание продолжений этой статьи: http://www.defmacro.org/ramblings/fp.html

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

Answer 8

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