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

Рассмотрим следующий отрезок программы:

Ьерп т! л; геа<1(п)-. [I :п] (п! питЬегя; геа! р: Ъедо геа! л,у:

Место для питЬегк должно выделяться в первой рамке стека, а для х и у - в рамке над ней. Но во время компиляции неизвестно, где должна начинаться вторая рамка, так как не известен размер чисел. Одно из решений в этой ситуации - иметь два стека: один для статической памяти, распределяемой в процессе компиляции, а другой для динамической памяти, распределяемой в процессе прогона. Однако этого обычно не делают, возможно, из-за тех проблем, которые возникают в связи с наличием более чем одного увеличивающегося и уменьшающегося стека во время прогона. Другое решение заключается в том, чтобы при компиляции выделять статическую память в каждом блоке в начале каждой рамки, а при прогоне - динамическую память над статической и каждой рамке. Это значит, что когда происходит компиляция, мы все еще не знаем, где начинаются рамки (кроме первой), но можем распределять статические адреса относительно начала определенной рамки. При прогоне точный размер рамок, соответствующих включающим блокам, известен, так что при входе в блок нужный элемент дисплея всегда можно установить так, чтобы он указывал на начало новой рамки (рис. 9.4).

Рампа

Рамка

ДИСПЛЕИ СТЕК

Рис 9.4

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

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

Динами ческая часть статическая

Рамка

Рамка

ДИСПЛЕИ

Рис. 9.5

рис. 9.4, показав на нем статическую и динамическую части массива (рис. 9.5).

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

[/ : Ю, - ,5 : 5)ш( 1аЫе

Будем считать, что элементы записаны в лексикографическом порядке индексов, т. е. элементы таблицы хранятся в следующем порядке:

1ЬIe\2, -5]], , -4]........ 1аЫе{1, 5],

1аЫе(2, -5]. , -4] ....... 1аЫе(У, 5\,

1а1е{10. -5]...........................1а1е(10.5\

Адрес конкретного элемента вычисляется как смещение по отношению к базовому адресу (адресу первого элемента) массива:

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

объема памяти. Для трехмерного массива соответствующая формула имеет вид

А!ЮК(АЩ1.К\]-АОПК(АК\11. 1„ /.,]) } (а,-/.-. /) Х<«,-/;,-/) X {/-,) +

+ («., -/я г Л X (- - /,) +К э

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

Аналогично

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

1u2 - /г • /I X -i, - /1

Он обозначается через 5]. Второй шаг

и,-i, { 1

Он обозначается через %- Третьим тагом является 1, обозначайся . он через а~3. На рис. 9.6 показаны шаги для массива

\1 : 3. 1 : 5. I . .фп! V

Если бы каждый Элемент массива ,-,-л ми мал объем памяти г, то эти шаш получали бы умножением всс.х вышеприведенных величин на г.

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

Теперь рассмотрим, как распределяется рабочая память при использовании стека. Во многих языках, например в Алголе 60, все идентификаторы должны описываться в блоке, прежде чем можно будет вычислять какие-либо выражения. Отсюда след\?т, что рабочую

память можно выделять в конкретной рамке стека над памятью, предусмотренной для значений, соответствующих идентификаторам (обычно называемой стеком идентификаторов). Конкретнее статическую рабочую память можно выделять в вершине статического стека идентификаторов, а динамическую рабочую память - в вершине динамического стека идентификаторов. В Алголе 68, где описатели идентификаторов могут появляться после вычисления выражений, • стеки идентификаторов и рабочий считают двумя разными стеками во время фазы распределения памяти, хотя для последующих проходов их можно объединять.

Б процессе компиляции статический стек идентификаторов растет по мере объявления идентификаторов. Однако статический рабочий стек может не только увеличиваться в р.азмере, но и уменьшаться, Возьмем, например,

х := о+ЙХС

При вычислении выражения (а + Ь Хс) потребуется рабочая память, чтобы записать значение Ьхс перед выполнением сложения. Ту же самую рабочую память можно использовать для хранения результата сложения. Однако после осуществления присвоения этот объем памяти можно освободить, так как он уже не нужен.

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

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

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

ргос

1ПГ 1

ет: = п-н /0;

и - т •, Ш(- ОЮ1Т5(т)

Л епй

14В-

ДИСПЛЕИ

Рнс. 9.7

Значение О161Т5 (315) составит 9, сумма цифр 3, 1 и 5, а для ее вычисления необходимо три раза входить в эту процедуру. На каждом уровне вхождения выделяется память для т и л. С этой целью можно вводить новую рамку стека при каждом (рекурсивном) входе в процедуру. Такие рамки называются динамическими (а не статическими). Стек времени прогона после третьего вхождения в процедуру будет выглядеть так, как изображено на рис. 9.7 (стек приведен лишь частично).

Методы вызова параметров

При описании распределения памяти, необходимой для осуществления процедуры О1С1Т5, подразумевалось, что нужно выделять память для формального параметра п. Объем выделяемой памяти зависит от метода сообщения мс-жду фактическим параметром в вызове процедуры, например 315 в вызове ОЮ1Т5 (315), и формальным параметром в описании процедуры, п в описании О1С1Т5. В различных языках используются различные методы «вызова параметров»; большинство языков предоставляют программисту возможность выбора по меньшей мере из двух методов.

Некоторые методы вызова параметров кратко описываются далее. Пол «телом процедуры» мы подразумеваем выполняемую часть 1ФО-цедуры. г. *?. ту ее часть, которая заключена между Ье1п и епй в О101Т8.

Вызов по значению

Фактический параметр (которым может быть выражение) вычисляется, и копия его значения помещается в память, выделенную для формального параметра. Это - один из методов, предлагаемых Алголом 60 и Паскалем, где формальный параметр может вести себя как локальная переменная и принимать присвоения в пределах тела про-целуры. Такое присвоение, однако, не влияет на значение фактической) параметра, поэтому данный метод вызова нельзя применять для вывод?! результата из процедуры. Вызов по значению является эффективным методом передачи информации в процедуру, где большие массивы позволяют делать процесс копирования недорогим.

Вызов по имени

Этот метод применяется в Алголе 60. Он заключается в текстуальной замене формального параметра в теле процедуры фактическим параметром перед выполнением тела процедуры. Там, где фактическим

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

Вызов по результату

Как и в вызове по значению, при входе в процедуру выделяется память для значения формального параметра. Однако никакое начальное значение формальному параметру не присваивается. Тело процедуры может осуществлять присвоения формальному параметру (и почти наверняка делает это), а при выходе из процедуры значение, которое в этот момент имеет формальный параметр, присваивается фактическому параметру. Этот метод удобен для передачи результата из процедуры и реализован в Алголе XV.

Вызов по значению и результату

Этот метод также применяется в Алголе \У. Он представляет собой комбинацию вызова по значению и вызова по результату. Копирование происходит при входе в процедуру и при выходе из нее.

Вызов по ссылке

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

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

вырабатывается объявление тождества

1п( п-315

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

В качестве другого примера возьмем процедуру

рг« 1</ааге=(п1 1п1 а) том):