В результате вызова $1/иаге(р) при входе в процедуру вырабатывается объявление тождества

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

Обстановка выполнения процедур

Выпапнение процедуры в Алголе 68 происходит в обстановке ее описания, а не вызова. Рассмотрим, например, следующий отрезок программы: . . ,

г Ьсдо 1П1 < = -•

ргос тсгетеп> = (геГ ш( н\ >оМ:

ч р! и$аЬ а : Ье§1п 1п1 а = 3: [п1 р : = 4: шсгетеш (р)

Вызов 1псгетсп1(р) добавит 2 к р, т.е. а, появляющаяся в теле процедуры -это а, описанная в начале программы, а не во внутреннем блоке Поэтому при вызове процедуры необходимо внести поправку в стек рабочего времени, чтобы рамка, соответствующая телу процедуры была немедленно помещена над рамкой, соответствующей блоку. в котором содержим ее описание. Инач- адреса, внеде.гые во время поогона (номер блока, смещение), будут относиться к другой рамке. На практике, чтобы не изменять стек при исключении из него нескольких рамок, можно изменить дисплей, тогда доступ через него дает измененный вид стека. Это изменение должно выполняться сразу же после вычисления параметров, так как они вычисляются в языковой обстановке вызова (рис. 9.8).

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

Один из способов осуществления связи между фактическими и формальными параметрами заключается в «ведении блока дополнительно бхожйения 6 t еУОЖ()е.чир процедуру

npoueuypij

ДИСПЛЕЙ СТЕК

ДИСПЛЕИ С1ЕИ

Рис. 9.Я

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

Очевидно, что входы и выходы из блоков и процедур нам дорого обходятся в смысле времени. Возникает вопрос, нельзя ли как-то сократить время настройки дисплея, особенно когда это касается программ с множеством уровнен блоков? Можно не создавать новую рамку для стека каждый раз при входе в новый блок, а, если речь не идет о процедурах (что мы вскоре обсудим}, иметь единую рамку для всех значений стека. При этом полностью устранятся все издержки, связанные с входом и выходом из блока, но неперекрещивающиеся блоки не смогут пользоваться одной и той же памятью, и, следовательно, в обмен на сэкономленное время мы получим увеличение объема памяти. Возможно, какой-либо настраивающийся компилятор сможет работать попеременно в двух режимах. В одном режиме он будет оптимизировать скорость выполнения программы (никаких перегрузок при входе в блок и выходе из него}, в другом - объем памяти, занимаемой объектной программой во время прогона (обычный метод в отношении входа и выхода из блока). Режим работы компилятора программист может задавать через переключатель. В Алголе 68 это, вероятно, осуществлялось бы с помощью прагмата. Если предоставлять программисту такую возможность выбора нежелательно или если эти две меры являются чересчур крайними, разработчик компилятора в тех случаях, когда он предполагает, что недостатки перевесят преимущества, может не создавать новую рамку стека там, где он в обычных условиях это бы сделал. Например, в Алголе 68 необходимость создания новой рамки в цикле

1ог 1 1о 10 йо

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

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

Параллельная обработка

Если в реализуемом языке возможна параллельная обработка, т. е. одновременно .могут быть активными несколько процессов или процессы мог\т сливаться каким-либо произвольным способом, стек становится неприемлемым как модель распределения памяти, поскольку объем памяти уже необязательно будет высвобождаться в порядке, обратном тому, в каком он выделяется. (Принцип «первым.вошел - первым вышел» уже не применим.) Но можно воспользоваться подходящим обобщением стека, а именно позволить ему иметь ветви, как у дерева, чтобы каждая ветвь соответствовала одному из параллельных

Рнс. 9.9

процессов. Например, реализация параллельного предложения в Алголе 68

раг (А, В. С)

где А, В и С - параллельно выполняющиеся процессы, потребовала бы распределения памяти, как на рис. 9.9.

Хранение в памяти других значений

Теперь рассмотрим, как хранятся некоторые более сложные значения.

1. Структуры в Алголе 68 (записи в некотор1х других языках) могут занимать сплошной объем памяти в стеке. Например, значе ние вида

5(гис1 (1п( /. геа! г. Ьоо[ Ь)

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

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

3. Для локальных генераторов в Алголе 68 память должна вы деляться в динамическом стеке, так как требуемый объем памяти не всегда известен во время компиляции (локальный генератор, например, может появиться внутри цикла). Однако каждое статическое появ ление локального генератора может отмечаться во время компиляции, и в статическом стеке может выделяться память для указателя на его

текущую динамическую реализацию, во время прогона. Более подробно организационные методы при прогоне для Алгола 68 рассмотрены в [26].

9.2 КУЧА

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

Рис. 9.11

В качестве примера рассмотрим, как организовать список литер в Алголе 68. Подходящим описанием вида служит следующее:

тсн1е $1-г51гис1 (иптоп (сНаг, ге( ]!$() 1чаЛ, ге( к!

Обычный список можно показать схематически, как на рис. 9.11, где А представляет литеру «.А * а т. д. Каждый список состоит из головной части - литеры или указателя на другой список - и хвостовой - указателя на другой список или нулевого списка, представленного на рисунке перечеркнутым квадратом. Этот же список можно записать иначе:

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

ргос геасИ = гкГ 11м : Ьедш сНаг :п,

геи/1 (т);

геаЛ(т)-, И 1п

= "у ; (Ьеп ш!

е!зе геГ 1&1 / = Ьеар Нк( ;

\! т = "("

1Ьеп гене! (ЬасЬярасе)-, 1нси1 о( / ; = геасИ

Фактический вид Статическая часть

Указатель на -динамическую часть (если она есть)

Тис. 9.10

геоЛ (Ьас/сзрисе) ; шИо! I : =

П спи

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

ь*ар 1Ы

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

ге( Из! / := гаи11; I

(/- это «указатель» на список). Глобальная память выделяется с помощью тешИ, и после первого присваивания обращение к ней осуществляется посредством идентификатора /. Однако после второго присвоения эта память окажется недоступной, тик как I теперь будет иметь другое значение. Хотя обычно термин «глобальная память> подразумевает, что память выделяется на время действия всей программы, попытка вновь использовать тот объем памяти, который уже становится недоступным программе, представляется вполне разумной. Даже в тех случаях, когда подобная стратегия несколько противоречит духу глобального распределения памяти в таких языках, как Алгол 68, ее це-лесообразло одобрить, если она не изменяет значения ни одной из программ, т. е. процесс восстановления памяти происходит без участия программиста. Поскольку не существует метода обращения к какому-либо конкретному участку памяти, программист не имеет возможности выясннть, перераспределяется ли эта память для других целен.

Глобальная память может также стать недоступной из-за блочной структуры программы, например в Алголе 68

ге( !п! с - Ьгар 1п1

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

(/ : - с

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

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

стек куче

Рис 3.12

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

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

Счетчики сс1лок

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

Для простоты допустим, что в каждой ячейке имеются три поля, первое из которых отводится для счетчика ссылок. Это позволит нам показать, как < ШР..ОШЬЮ счетчика ссылок можно регулировать ничуть в виде списки. Э]\ идею легко распространить и па более сложные структуры. Если X-идентификатор, указывающий на список, его значение может быть таким, как на рис. 9.13:

у - - 1чи о( х

Результат присвоения показан на рис. 9.14.

x . - 1

урм. 9.14

Следующее присвоение может дать результат, приведенный на рис. 9.15.

На единицу уменьшился не только счегчик ссылок ячейки, на которую указывает А, но и ячейка, на которую указывает данная ячейка.