3. Стеки выражений

Язык Algol 60 оказал сильное влияние на разработку последующих языков программирования и, в меньшей степени, архитектур компьютеров. Это не удивительно, поскольку язык, компилятор и компьютер образуют неразрывный комплекс.

В Algol можно было вычислять выражения произвольной сложности с подвыражениями, заключенными в скобки, и операциями с индивидуальной связующей способностью. Результаты подвыражений временно сохранялись. Фридрих Бауер (Friedrich Ludwig Bauer) и Эдсгер Дийкстра (Edsger Wybe Dijkstra) независимо предложили схему вычисления произвольных выражений. Они заметили, что при вычислении выражения слева направо с учетом правил приоритетов операций и скобок первым всегда потребуется последний сохраненный элемент. Поэтому его можно помещать в список с проталкиванием вниз, или стек.

Эта простая стратегия очевидным образом реализовывалась с использованием группы регистров путем добавления неявного реверсивного счетчика, сохраняющего верхний индекс регистра. Применение такого стека сокращало число обращений к памяти и позволяло избежать явного указания в инструкциях конкретных регистров. Коротко говоря, стековые компьютеры казались отличной идеей, и эта схема была реализована в компьютерах English Electric KDF-9 и Burroughs B5000, хотя это, очевидно, повысило сложность аппаратуры.

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

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

4. Сохранение адреса возврата в коде

Инструкция перехода на подпрограмму, предложенная Дэвидом Уилером (David John Wheeler), сохраняет значение счетчика команд, которое должно быть восстановлено при завершении подпрограммы. Проблема состоит в выборе места для сохранения этого значения. В нескольких компьютерах, в основном, в миникомпьютерах, но также и в мейнфрейме CDC 6000, инструкция такого перехода на ячейку с адресом d сохраняла адрес возврата в этой ячейке и продолжала выполнение с адреса d+1:

mem[d] := PC+1; PC := d+1.

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

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

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