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

57

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

Ваш Ответ

8   ответов
1

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
3

http://www.defmacro.org/ramblings/fp.html

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

84

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

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

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

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

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

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

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededgcc.gnu.org/wiki/SplitStacks
Error: User Rate Limit Exceeded
3

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

Error: User Rate Limit Exceeded
4

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

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

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

Error: User Rate Limit Exceededwolframscience.com/prizes/tm23/background.htmlError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
14

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

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

Error: User Rate Limit ExceededdoesError: User Rate Limit Exceededstackoverflow.com/questions/1016218/…
3

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

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

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
5

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

Похожие вопросы