Являются ли стеки единственным разумным способом структурирования программ?

74

Большинство архитектур, которые я видел, используют стек вызовов для сохранения / восстановления контекста перед вызовами функций. Это настолько распространенная парадигма, что операции push и pop встроены в большинство процессоров. Существуют ли системы, которые работают без стека? Если да, то как они работают и для чего они используются?

ConditionRacer
источник
5
Учитывая то, как функции должны вести себя на языках, подобных C (то есть вы можете вкладывать вызовы настолько глубоко, насколько хотите, и можете возвращаться обратно в обратном порядке), мне не ясно, как еще можно реализовать вызовы функций, если это не невероятно неэффективен. Например, вы могли бы заставить программиста использовать стиль передачи продолжения или какую-то другую причудливую форму программирования, но никто, кажется, на самом деле почему-то не работает с CPS очень сильно на низком уровне.
Кевин
5
GLSL работает без стека (как и другие языки в этой конкретной скобке). Это просто запрещает рекурсивные вызовы.
Леушенко
3
Вы также можете заглянуть в окна регистрации , которые используются некоторыми архитектурами RISC.
Марк Бут
2
@Kevin: «Ранние компиляторы FORTRAN не поддерживали рекурсию в подпрограммах. Ранние компьютерные архитектуры не поддерживали концепцию стека, а когда они непосредственно поддерживали вызовы подпрограмм, место возврата часто сохранялось в одном фиксированном месте рядом с кодом подпрограммы, что делает не допускать повторного вызова подпрограммы до возвращения предыдущего вызова подпрограммы. Хотя это не указано в Fortran 77, многие компиляторы F77 поддерживают рекурсию в качестве опции, хотя она стала стандартом в Fortran 90 ». ru.wikipedia.org/wiki/Fortran#FORTRAN_II
Утка мычания
3
Микроконтроллер P8X32A («Propeller») не имеет понятия стека на своем стандартном языке ассемблера (PASM). Инструкции, отвечающие за переход, также самостоятельно изменяют инструкцию возврата в ОЗУ, чтобы определить, куда возвращаться - что можно выбрать произвольно. Интересно, что язык «Spin» (интерпретируемый язык высокого уровня, работающий на одном и том же чипе) имеет традиционную семантику стека.
Wossname

Ответы:

50

(Несколько) популярной альтернативой стеку вызовов являются продолжения .

Например, виртуальная машина Parrot основана на продолжении. Это полностью без стеков: данные хранятся в регистрах (например, Dalvik или LuaVM, Parrot на основе регистров), а поток управления представлен продолжениями (в отличие от Dalvik или LuaVM, которые имеют стек вызовов).

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

Как указал @rwong , стиль передачи продолжения является альтернативой стеку вызовов. Программы, написанные (или преобразованные) в стиль передачи продолжения, никогда не возвращаются, поэтому нет необходимости в стеке.

Отвечая на ваш вопрос с другой точки зрения: возможно иметь стек вызовов без отдельного стека, выделяя кадры стека в куче. Некоторые реализации Lisp и Scheme делают это.

Йорг Миттаг
источник
4
Это зависит от вашего определения стека. Я не уверен, что наличие связанного списка (или массива указателей на или ...) стековых фреймов - это не столько «стек», сколько «другое представление стека»; и программы на языках CPS (на практике) имеют тенденцию создавать то, что эффективно связаны списки продолжений, которые очень похожи на стеки (если нет, вы можете проверить GHC, который помещает то, что он называет «продолжениями», в линейный стек для эффективности).
Джонатан В ролях
6
« Программы, написанные (или преобразованные) в стиль передачи продолжения, никогда не возвращаются » ... звучит зловеще.
Роб Пенридж
5
@RobPenridge: это немного загадочно, я согласен. CPS означает, что вместо возврата функции принимают в качестве дополнительного аргумента другую функцию, вызываемую, когда их работа завершена. Поэтому, когда вы вызываете функцию и у вас есть другая работа, которую вам нужно выполнить после ее вызова, вместо того, чтобы ждать, пока функция вернется и затем продолжит свою работу, вы оборачиваете оставшуюся работу («продолжение»). ) в функцию, и передайте эту функцию в качестве дополнительного аргумента. Затем вызванная вами функция вызывает эту функцию вместо возврата, и так далее, и так далее. Никакая функция никогда не возвращается, это просто
Йорг Миттаг
3
... вызывает следующую функцию. Поэтому вам не нужен стек вызовов, потому что вам никогда не нужно возвращаться и восстанавливать состояние привязки ранее вызванной функции. Вместо того, чтобы переносить прошлое состояние, чтобы вы могли вернуться к нему, вы переносите будущее состояние, если хотите.
Йорг Миттаг
1
@jcast: определяющей особенностью стека является IMO, что вы можете получить доступ только к самому верхнему элементу. Список продолжений, OTOH, даст вам доступ ко всем продолжениям, а не только к верхнему стековому фрейму. Например, если у вас есть возобновляемые исключения в стиле Smalltalk, вы должны иметь возможность проходить через стек, не выталкивая его. И наличие продолжений в языке, в то же время желая сохранить привычную идею стека вызовов, приводит к стекам спагетти, которые по сути являются деревом стеков, где продолжения «разветвляют» стек.
Йорг Миттаг,
36

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

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

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

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

(Мы могли бы также добавить изменчивость структур данных ...)

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

Эрик Эйдт
источник
9
На самом деле, у графических процессоров до сих пор нет стеков вообще. Вам запрещено повторять в GLSL / SPIR-V / OpenCL (не уверен насчет HLSL, но, вероятно, я не вижу причин, почему это будет иначе). В действительности они обрабатывают «стеки» вызова функций, используя абсурдно большое количество регистров.
LinearZoetrope
@Jsor: Это в значительной степени детали реализации, как видно из архитектуры SPARC. Как и у ваших графических процессоров, SPARC имеет огромный набор регистров, но он уникален тем, что имеет скользящее окно, которое при циклическом переносе выливает очень старые регистры в стек в ОЗУ. Так что это действительно гибрид между двумя моделями. И SPARC не указал точно, сколько было физических регистров, насколько велико было окно регистров, поэтому различные реализации могли находиться где угодно в этом масштабе от «огромного количества регистров» до «достаточно для одного окна при каждом вызове функции». разливать прямо в стек "
MSalters
Недостатком модели стека вызовов является то, что за переполнением массива и / или адреса следует очень внимательно следить, поскольку самоизменяющиеся программы в качестве эксплойта возможны, если произвольные биты кучи являются исполняемыми.
BenPen
14

TL; DR

  • Стек вызовов как механизм вызова функций:
    1. Обычно моделируется аппаратным обеспечением, но не является фундаментальным для построения аппаратного обеспечения
    2. Основа для императивного программирования
    3. Не является фундаментальным для функционального программирования
  • Стек как абстракция «первым пришел - первым вышел» (LIFO) имеет фундаментальное значение для информатики, алгоритмов и даже некоторых нетехнических областей.
  • Некоторые примеры организации программы, которые не используют стеки вызовов:
    • Стиль продолжения прохождения (CPS)
    • Конечный автомат - гигантская петля, со всем встроенным. (Предполагается, что вдохновлен архитектурой прошивки Saab Gripen, и приписывается сообщению Генри Спенсера и воспроизведено Джоном Кармаком.) (Примечание № 1)
    • Архитектура потока данных - сеть субъектов, связанных очередями (FIFO). Очереди иногда называют каналами.

Остальная часть этого ответа - случайная коллекция мыслей и анекдотов, и поэтому несколько дезорганизована.


Стек, который вы описали (как механизм вызова функции), специфичен для императивного программирования.

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

Ниже машинного кода вы найдете оборудование, ответственное за выполнение программного обеспечения. Хотя современный микропроцессор слишком сложен, чтобы описывать его здесь, можно представить, что существует очень простая конструкция, которая медленная, но все еще способна выполнять тот же машинный код. Такой простой дизайн будет использовать основные элементы цифровой логики:

  1. Комбинационная логика, то есть соединение логических элементов (и, или, нет, ...) Обратите внимание, что «комбинационная логика» исключает обратную связь.
  2. Память, то есть триггеры, защелки, регистры, SRAM, DRAM и т. Д.
  3. Конечный автомат, состоящий из некоторой комбинационной логики и некоторой памяти, достаточный для того, чтобы он мог реализовать «контроллер», который управляет остальной частью аппаратного обеспечения.

Следующие обсуждения содержали множество примеров альтернативных способов структурирования императивных программ.

Структура такой программы будет выглядеть так:

void main(void)
{
    do
    {
        // validate inputs for task 1
        // execute task 1, inlined, 
        // must complete in a deterministically short amount of time
        // and limited to a statically allocated amount of memory
        // ...
        // validate inputs for task 2
        // execute task 2, inlined
        // ...
        // validate inputs for task N
        // execute task N, inlined
    }
    while (true);
    // if this line is reached, tell the programmers to prepare
    // themselves to appear before an accident investigation board.
    return 0; 
}

Этот стиль будет подходящим для микроконтроллеров, то есть для тех, кто видит программное обеспечение как дополнение к функциям аппаратного обеспечения.


rwong
источник
@Peteris: стеки являются структурами данных LIFO.
Кристофер Кройциг
1
Интересно. Я бы подумал об этом наоборот. Например, FORTRAN является императивным языком программирования, и ранние версии не использовали стек вызовов. Однако рекурсия имеет основополагающее значение для функционального программирования, и я не думаю, что ее можно реализовать в общем случае без использования стека.
TED
@TED ​​- в реализации функционального языка есть стековая (или, как правило, древовидная) структура данных, представляющая отложенные вычисления, но вы не обязательно выполняете ее с инструкциями, использующими стековые режимы адресации машины, или даже с инструкциями вызова / возврата (вложенным / рекурсивным способом - возможно, просто как часть цикла конечного автомата).
Давидбак
@davidbak - IIRC, рекурсивный алгоритм в значительной степени должен быть хвост-рекурсивным, чтобы иметь возможность избавиться от стека. Возможно, есть и другие случаи, когда вы можете оптимизировать его, но в общем случае вам нужен стек . На самом деле, мне сказали, что есть математическое доказательство того, что это где-то плавает. В этом ответе утверждается, что это теорема Черча-Тьюринга (я думаю, основанная на том факте, что машины Тьюринга используют стек?)
TED
1
@TED ​​- Я согласен с тобой. Я считаю, что недоразумение заключается в том, что я прочитал статью ОП, в которой говорится о системной архитектуре, которая значила для меня машинную архитектуру . Я думаю, что другие, кто ответил здесь, имеют то же понимание. Таким образом, те из нас, кто понял, что это контекст, ответили, что вам не нужен стек на уровне машинных инструкций / адресации. Но я вижу, что этот вопрос также можно интерпретировать так, что он означает, что языковой системе вообще нужен стек вызовов. Такого ответа тоже нет, но по разным причинам.
Давидбак
11

Нет, не обязательно

Прочитать старую статью Аппеля Сбор мусора может быть быстрее, чем распределение стеков . Он использует стиль передачи продолжения и показывает реализацию без стеков.

Также обратите внимание, что старые компьютерные архитектуры (например, IBM / 360 ) не имели никакого аппаратного регистра стека. Но ОС и компилятор зарезервировали регистр для указателя стека по соглашению (связанному с соглашениями о вызовах ), чтобы они могли иметь программный стек вызовов .

В принципе, весь программный компилятор и оптимизатор C могут обнаружить случай (несколько распространенный для встроенных систем), когда граф вызовов статически известен и без какой-либо рекурсии (или указателей на функции). В такой системе каждая функция могла сохранять свой обратный адрес в фиксированном статическом местоположении (и именно так Fortran77 работал на компьютерах эпохи 1970 года).

В наши дни процессоры также имеют стеки вызовов (и машинные инструкции вызова и возврата), осведомленные о кэш- памяти ЦП .

Василий Старынкевич
источник
1
Уверен, что FORTRAN прекратил использовать статические места возврата, когда вышел FORTRAN-66 и потребовалась поддержка SUBROUTINEи FUNCTION. Вы правы для более ранних версий, хотя (FORTRAN-IV и, возможно, WATFIV).
TMN
И Кобол, конечно. И отличное замечание о IBM / 360 - он получил довольно широкое применение, несмотря на отсутствие режимов адресации аппаратного стека. (R14, я так думаю?) И у него были компиляторы для стековых языков, например, PL / I, Ada, Algol, C.
davidbak
Действительно, я изучал 360 в колледже и сначала это показалось мне странным.
JDługosz
1
@ JDługosz Лучший способ для современных студентов, изучающих компьютерную архитектуру, рассмотреть 360 - это очень простая машина RISC ... хотя и с более чем одним форматом инструкций ... и несколькими аномалиями, такими как TRи TRT.
Давидбак
Как насчет "нуля и добавить упакованный", чтобы переместить регистр? Но «ответвление и ссылка», а не стек для адреса возврата, сделали возврат назад.
JDługosz
10

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

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Мы помещаем эту программу в строку, и мы оцениваем программу по текстовой подстановке. Поэтому, когда мы оцениваем f(3), мы выполняем поиск и заменяем на 3 для i, например так:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)

Отлично. Теперь мы выполняем другую текстовую подстановку: мы видим, что условие «if» ложно, и выполняем замену другой строки, создавая программу:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)

Теперь мы заменим еще одну строку для всех подвыражений, содержащих константы:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

И вы видите, как это происходит; Я не буду вдаваться в подробности. Мы могли бы продолжать выполнять серию подстановок строк, пока мы не приступим к работе let x = 6и не закончим.

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

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

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

Эрик Липперт
источник
3
Retina является примером языка программирования на основе Regex, который использует строковые операции для вычислений.
Эндрю Пилизер
2
@AndrewPiliser Разработан и реализован этим крутым чуваком .
кот
3

Со времени публикации Parnas в 1972 г. « О критериях, которые будут использоваться при разложении систем на модули », было разумно принято, что информация, скрывающаяся в программном обеспечении, - это хорошо. Это следует из долгих дебатов 60-х годов о структурной декомпозиции и модульном программировании.

модульность

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

Динамический обзор

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

Поскольку любой поток (по определению) имеет только один текущий указатель инструкций, LIFO-стек подходит для отслеживания каждого вызова.

Исключения

Таким образом, хотя модель продолжения не поддерживает структуру данных явно для стека, все еще существует вложенный вызов модулей, который необходимо где-то поддерживать!

Даже декларативные языки либо поддерживают историю оценки, либо наоборот выравнивают план выполнения по соображениям производительности и поддерживают прогресс каким-либо другим способом.

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

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

Пекка
источник
1
Вы рисуете себя в углу, предполагая, что « любая многопоточная система». Связанные конечные автоматы могут иметь несколько потоков в своей реализации, но не требуют стека LIFO. В FSM нет никаких ограничений, что вы возвращаетесь в любое предыдущее состояние, не говоря уже о порядке LIFO. Так что это настоящая многопоточная система, для которой она не подходит. И если вы ограничиваете себя определением многопоточности как «параллельные независимые стеки вызовов функций», вы получаете циклическое определение.
MSalters
Я так не читаю вопрос. ОП знаком с вызовами функций, но спрашивает о других системах.
MSalters
@MSalters Обновлен, чтобы включать параллельные бесконечные циклы. Модель действительна, но ограничивает масштабируемость. Я бы предположил, что даже машины с умеренным состоянием включают вызовы функций для повторного использования кода.
Пекка
2

Все старые мэйнфреймы (IBM System / 360) вообще не имели понятия о стеке. Например, в 260 параметры создавались в фиксированном месте в памяти, а когда вызывалась подпрограмма, она вызывалась с R1указанием на блок параметров и R14с адресом возврата. Вызванная подпрограмма, если она хочет вызвать другую подпрограмму, должна была бы быть сохранена R14в известном месте перед выполнением этого вызова.

Это гораздо надежнее, чем стек, потому что все может храниться в фиксированных местах памяти, установленных во время компиляции, и на 100% гарантируется, что процессы никогда не исчерпают стек. В настоящее время нам не нужно заниматься «выделением 1 МБ и скрестить пальцы».

Рекурсивные вызовы подпрограмм были разрешены в PL / I, указав ключевое слово RECURSIVE. Они означали, что память, используемая подпрограммой, была динамически, а не статически распределена. Но рекурсивные вызовы были такими же редкими, как и сейчас.

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

Мартин Кочански
источник