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

StackOverflow https://stackoverflow.com/questions/1016218

Вопрос

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

Это было полезно?

Решение

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

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

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

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

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

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

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

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

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

Другие советы

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

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

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

В средах без стеков, с которыми я более или менее знаком (машина Тьюринга, сборка и 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;
}

Теоретически действительно умный компилятор мог бы это понять за вас.Но менее умный человек все равно мог бы сгладить его как переход:

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 просто не может этого сделать.Вы много отказываетесь?Не совсем.Это то, что обычный C тоже не может делать хорошо.Если ты мне не веришь, просто позвони fib(1000) и посмотрите, что произойдет с вашим драгоценным компьютером.

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top