Стек

Продолжение. Начало см. “В мир информатики” № 102
(“Информатика” № 2/2008)

1.4. Роль стека в вычислительной технике

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

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

Рассмотрим простой пример для процессоров с системой команд, принятой в IBM-совместимых компьютерах. Пусть некоторый фрагмент программы должен использовать для промежуточных данных регистры BX и CX. Надежное решение проблемы такое:

PUSH BX

PUSH CX

<здесь любые манипуляции с BX и CX>

POP CX

POP BX

После завершения работы указанного фрагмента постоянство значений сохраняемых регистров гарантируется независимо от длины и сложности фрагмента.

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

Подобные фрагменты программисты используют настолько часто, что, начиная с процессора Intel 80286, к системе команд записи в стек была добавлена инструкция PUSHA (от push all), сохраняющая в стеке сразу все(!) регистры процессора [1].

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

Ci = N mod 10; N = N div 10.

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

Использование стека для вычисления выражений. Стек является идеальным средством для вычисления произвольных арифметических и логических выражений. Это вполне самостоятельный вопрос, он многократно обсуждался в литературе, так что мы кратко разберем его на примере. Пусть требуется вычислить выражение 2 * (3 + 4). Ход вычислений с помощью стека иллюстрирует следующая таблица:

Подчеркнем, что при использовании стековой формы вычислений скобки исчезают, поэтому такую форму записи выражений называют “обратной бесскобочной записью”, или часто, подчеркивая происхождение данной нотации, — “обратной польской записью”: ее автором является известный польский математик Ян Лукасевич (1878–1956). Достоинством польской системы представления арифметических выражений является полная однозначность ее интерпретации, причем без всяких скобок.

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

Использование стека для организации механизма подпрограмм. Одним из важнейших предназначений стека является создание возможностей для вызова подпрограмм. Подпрограммой называют некоторый функционально законченный (в котором решается какая-то частная задача) фрагмент программы, оформленный так, чтобы им можно было пользоваться из различных точек основной программы. Главной проблемой организации подпрограммы является не столько возможность перехода к ней, сколько создание механизма возврата в ту точку, откуда подпрограмма была вызвана, после окончания ее работы. Именно здесь стек и оказывается необычайно полезен. Логика работы подпрограмм является стандартной и строится следующим образом. В конце выделенного фрагмента, оформляемого в виде подпрограммы, ставится специальная инструкция возврата RET (сокращение происходит от return — вернуться). А в любом месте программы, где потребуется выполнить подпрограмму, помещается ее вызов CALL A, где A — адрес начала подпрограммы. Рассмотрим, как происходит процесс вызова подпрограммы, подробнее.

Пусть подпрограмма расположена начиная с адреса A, ее вызов — в адресе C, а следующая за вызовом инструкция (точка возврата) — в адресе N (см. рис. 2).

Примечание. Значения N и С, разумеется, связаны друг с другом: N = С + L, где L — длина команды CALL A. Учитывая, что L может в разных ситуациях иметь разную длину, мы не будем здесь вычислять значение N через С.

В принятых обозначениях для перехода к подпрограмме необходимо выполнить два действия:

1) сохранить (в стеке) значение N для последующего возврата;

2) перейти к подпрограмме по адресу A.

Смысл производимых действий становится гораздо более понятным, если учесть, что для хранения адреса очередной команды программы процессор использует специальный регистр — счетчик команд. В процессорах Intel этот регистр обозначается IP (Instruction Pointer). В новой терминологии смысл перехода к подпрограмме можно сформулировать короче:

1) сохранить в стеке значение IP (PUSH IP);

2) занести A в регистр IP (JMP A).

При возврате из подпрограммы проделывается обратное действие: из стека извлекается адрес возврата и заносится в IP (POP IP), что обеспечивает переход к этому адресу.

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

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

Примечание. Строго говоря, степень вложенности все же ограничена размером оперативной памяти, выделенным под стек!

Подчеркнем, что с точки зрения описанного механизма вызова вложенных подпрограмм ситуация, когда подпрограмма вызывает сама себя (на этом базируется так называемая “рекурсия”), ничем не нарушает алгоритма работы (более того, процессору необычайно трудно проверить, вызывает ли подпрограмма другую или саму себя!). Как было указано выше, проблемы здесь заключаются в передаче параметров и создании локальных переменных так, чтобы они “не портили друг друга” при рекурсивных вызовах. Рассмотрим данную проблему подробнее.

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

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

Примечание. Описанный выше механизм требует выделения достаточного объема стековой памяти. При неправильной организации (бесконечной) рекурсии программа “вылетает” именно в связи с достижением границы стека.

Отметим, что параметры подпрограмм (точнее говоря, их значения или адреса; в первом случае говорят о передаче параметра по значению, а во втором — по ссылке) также передаются при обращении к подпрограмме через стек.

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

Пример

Вспомним, как записываются вложенные циклы в языке Бейсик:

FOR i = 1 TO im

FOR j = 1 TO jm

FOR k = 1 TO km

...

NEXT k: NEXT j: NEXT i

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

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

Возможно построение вычислительной машины на основе стековых принципов (вспомните уже упоминавшиеся выше калькуляторы). Хорошим примером стековой организации может служить виртуальная Java-машина.

Литература

1. Гук М.Ю. Процессоры Intel от 8086 до Pentium II. СПб.: Питер, 1997.

2. Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992.

Продолжение в следующем выпуске.

---

¹ Существует также вариант записи, в котором знак операции ставится перед операндами:
+ 3 4. Такой вариант называют “польской записью” (в отличие от обратной польской записи). — Прим. ред.