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

19

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

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

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

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

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

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

Лоренцо Дематте
источник
Clean использует граф и машину переписывания графов, которая, в свою очередь, реализуется с использованием машины с тремя стеками, но с содержанием, отличным от обычного.
Для виртуальных машин можно использовать связанный список. Каждый узел списка является фреймом. Поскольку аппаратный стек используется виртуальной машиной, это позволяет кадрам существовать в куче без дополнительных затрат realloc().
Shawnhcorey

Ответы:

19

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

Обратитесь к 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 «Структура и интерпретация компьютерных программ» подробно описывает продолжение.

Джон Р. Штром
источник
2
Это было большое историческое понимание, спасибо! Когда я задал свой вопрос, я действительно имел в виду продолжения, особенно стиль передачи продолжения (CPS). В этом случае стек не только неудобен, но, вероятно, и не нужен: вам не нужно помнить, куда возвращать, вы указываете точку, где продолжить выполнение. Я задавался вопросом, были ли другие подходы без стеков там, где они распространены, а вы дали несколько очень хороших, о которых я не знал.
Лоренцо Дематте
Немного связано: вы правильно указали «если язык не позволяет рекурсию». А как насчет языка с рекурсией, в частности функций, которые не являются хвостово-рекурсивными? Нужен ли им стек «по замыслу»?
Лоренцо Дематте
«Стеки вызовов необходимы только в тех языках, которые допускают рекурсию или взаимную рекурсию» - нет. Если функция может быть вызвана из более чем одного места (например, оба fooи barмогут вызывать baz), то функция должна знать, к чему возвращаться. Если вы вкладываете эту информацию «кому возвращаться», то в итоге вы получаете стек. Неважно, как вы это называете, поддерживается ли оно аппаратным обеспечением ЦП или чем-то, что вы эмулируете в программном обеспечении (или даже если это связанный список статически распределенных записей), это все равно стек.
Брендан
@ Брендан не обязательно (по крайней мере, в этом вся цель моего вопроса). «Куда возвращаться» или «лучше», куда идти дальше », должен ли это быть стек, то есть структура LIFO? Может ли это быть дерево, карта, очередь или что-то еще?
Лоренцо Дематте
Например, мои интуитивные ощущения таковы, что CPS просто нужно дерево, но я не уверен и не знаю, где искать. Вот почему я спрашиваю ..
Лоренцо Дематте
6

Невозможно реализовать семантику вызова функции без использования какого-либо стека. Играть можно только в игры в слова (например, использовать для него другое имя, например, «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, обработка исключений и т. д.

Brendan
источник
По определению, стек является коллекцией LIFO: первым пришел, первым вышел. Очередь - это коллекция FIFO.
Джон Р. Штром
Так является ли стек единственно приемлемой структурой данных? Если так, то почему?
Лоренцо Дематте
@ JohnR.Strohm: исправлено :-)
Брендан
1
Для языков без рекурсии (прямой или взаимный) можно статически выделить для каждого метода переменную, которая будет определять место, из которого этот метод последний раз вызывался. Если компоновщик знает о таких вещах, он может распределять такие переменные таким образом, который будет не хуже, чем стек, если бы фактически был выбран каждый статически возможный путь выполнения .
суперкат
4

Игрушечный конкатенативный язык 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 не имеет стека.

Карл Дамгаард Асмуссен
источник
Вау, спасибо! Я посмотрю на это ... не уверен, что это действительно относится к вызовам функций, но в любом случае стоит посмотреть
Lorenzo Dematté
1
@ Карл Дамгаард Асмуссен "толкает слова, составляющие его в начало очереди" "толкает фронт" Разве это не стек?
@ guesttttttt222222222 не совсем. В коллстаке хранятся указатели возврата, а когда функция возвращается, коллстак извлекается. В очереди выполнения хранятся только указатели на функции, и при выполнении следующей функции она расширяется до ее определения и помещается в начало очереди. В XY очередь выполнения на самом деле является deque, поскольку есть операции, которые также работают в конце очереди выполнения.
Карл Дамгаард Асмуссен