Средства разработки приложений



              

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


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

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

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

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

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


Содержание  Назад  Вперед