Какие есть альтернативы использованию стека для представления семантики вызова функции?

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

Однако стек является деталью реализации: соглашения о вызовах могут делать разные вещи (например, x86 fastcall использует (некоторые) регистры, MIPS и последователи используют окна регистров и т. Д.), А оптимизация может делать даже другие вещи (встраивание, пропуск указателя кадра, оптимизация остаточного вызова ..).

Конечно, наличие удобных инструкций стека на многих машинах (виртуальных машинах, таких как JVM и CLR, а также на реальных машинах, таких как x86 с их PUSH / POP и т. Д.) Делает его удобным для использования в вызовах функций, но в некоторых случаях это возможно программировать таким образом, чтобы стек вызовов не был необходим (я имею в виду стиль продолжения передачи или актеры в системе передачи сообщений)

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

Кто-нибудь из вас знает, было ли это когда-либо сделано на каком-либо языке / машине / виртуальной машине, и если да, то каковы поразительные различия и недостатки?

РЕДАКТИРОВАТЬ: мое внутреннее чувство заключается в том, что разные подходы суб-вычислений могут использовать разные структуры данных. Например, лямбда-исчисление не основано на стеке (идея применения функции улавливается сокращениями), но я смотрел на реальный язык / машину / пример. Вот почему я спрашиваю ...

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

Обратитесь к FORTRAN IV (и более ранним версиям) и ранним версиям COBOL для примеров языков, которые не требуют стеков вызовов.

Обратитесь к Управляющим данным 6600 (и более ранним машинам Управляющих данных) для примера очень успешного раннего суперкомпьютера, который не обеспечивал прямую аппаратную поддержку стеков вызовов. Обратитесь к PDP-8 за примером очень успешного раннего миникомпьютера, который не поддерживал стеки вызовов.

Насколько я знаю, стековые машины Burroughs B5000 были первыми машинами с аппаратными стеками вызовов. Машины B5000 были спроектированы с нуля для работы с ALGOL, что требовало рекурсии. У них также была одна из первых дескрипторных архитектур, которая заложила основу для архитектур возможностей.

Насколько я знаю, именно PDP-6 (выросший в DEC-10) популяризировал аппаратное обеспечение стека вызовов, когда хакерское сообщество в MIT приняло его и обнаружило, что операция PUSHJ (Push Return Address and Jump) позволил сократить процедуру десятичной печати с 50 инструкций до 10.

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

Лучший пример необходимости большего, с чем я столкнулся, - это «продолжение», возможность приостановить вычисление в середине, сохранить его как замороженный пузырь состояния и снова запустить его, возможно, много раз. Продолжения стали популярными в диалекте Scheme LISP, как способ реализации, среди прочего, выходов из ошибок. Для продолжения требуется возможность снимать текущую среду выполнения и воспроизводить ее позже, а стек для этого несколько неудобен.

Abelson & Sussman «Структура и интерпретация компьютерных программ» подробно описывает продолжение.

Невозможно реализовать семантику вызова функции без использования какого-либо стека. Играть можно только в игры в слова (например, использовать для него другое имя, например, «FILO return buffer»).

Можно использовать что-то, что не реализует семантику вызова функции (например, стиль передачи продолжения, актеры), а затем построить семантику вызова функции поверх этого; но это означает добавление некоторой структуры данных для отслеживания того, где передается управление, когда функция возвращается, и эта структура данных будет представлять собой тип стека (или стека с другим именем / описанием).

Представьте, что у вас есть много функций, которые могут вызывать друг друга. Во время выполнения каждая функция должна знать, куда возвращаться при выходе из функции. Если firstзвонки, secondто у вас есть:

second returns to somewhere in first

Тогда, если secondзвонки у thirdвас есть:

third returns to somewhere in second
second returns to somewhere in first

Тогда, если thirdзвонки у fourthвас есть:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

Поскольку каждая функция вызывается, больше информации "где вернуть" должно храниться где-то.

Если функция возвращается, то используется информация «куда возвращать», и она больше не нужна. Например, если fourthвозвращается обратно куда- thirdто, то количество информации «где вернуться» станет:

third returns to somewhere in second
second returns to somewhere in first

В принципе; «семантика вызова функции» подразумевает, что:

• у вас должна быть информация "где вернуть"
• количество информации увеличивается при вызове функций и уменьшается при возврате функций
• первая часть сохраненной информации «куда возвращать» будет последней частью отброшенной информации «куда возвращать»

Это описывает буфер FILO / LIFO или стек.

Если вы попытаетесь использовать тип дерева, то у каждого узла в дереве никогда не будет более одного дочернего элемента. Примечание. Узел с несколькими дочерними элементами может возникнуть только в том случае, если функция вызывает 2 или более функций одновременно , что требует некоторого параллелизма (например, threads, fork () и т. Д.), И это не будет «семантикой вызова функции». Если каждый узел в дереве никогда не будет иметь более одного дочернего элемента; тогда это «дерево» будет использоваться только в качестве буфера FILO / LIFO или стека; и поскольку он используется только в качестве буфера FILO / LIFO или стека, можно утверждать, что «дерево» является стеком (и единственное отличие заключается в играх в слова и / или деталях реализации).

То же самое относится к любой другой структуре данных, которая могла бы использоваться для реализации «семантики вызова функции» - она ​​будет использоваться в качестве стека (и единственное отличие - это игры в слова и / или детали реализации); если это не нарушает "семантику вызова функции". Примечание: я бы привел примеры для других структур данных, если бы мог, но я не могу представить себе какую-либо другую структуру, которая была бы немного правдоподобной.

Конечно, как реализован стек - это деталь реализации. Это может быть область памяти (где вы отслеживаете «текущую вершину стека»), это может быть какой-то связанный список (где вы отслеживаете «текущую запись в списке»), или она может быть реализована в некоторых другой путь. Также не имеет значения, есть ли у оборудования встроенная поддержка или нет.

Примечание. Если в любой момент может быть активен только один вызов какой-либо процедуры; тогда вы можете статически выделять место для информации «где вернуться». Это по-прежнему стек (например, связанный список статически распределенных записей, используемых способом FILO / LIFO).

Также обратите внимание, что есть некоторые вещи, которые не следуют «семантике вызова функции». Эти вещи включают «потенциально очень различную семантику» (например, передача продолжения, модель актера); а также включает общие расширения «семантики вызовов функций», такие как параллелизм (потоки, волокна и т. д.), setjmp/ longjmp, обработка исключений и т. д.

Игрушечный конкатенативный язык XY использует для выполнения очередь вызовов и стек данных.

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

Так что если у нас есть функция для удвоения верхнего элемента:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Тогда составляющие функции +и dupимеют следующие подписи типа стека / очереди:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

И doubleкак это ни парадоксально, будет выглядеть так:

double [X Y] -> [X dup^+^Y]

Таким образом, в некотором смысле, XY не имеет стека.