Cтраница 3
Тот факт, что любая цепочка может быть без дополнительных указаний использована в качестве переменной и, следовательно, должна входить в текущую среду ссылок, позволяет использовать центральную таблицу цепочек также в роли центральной таблицы среды ссылок. При последующих ссылках ей может быть присвоено непустое значение или выбрано ее значение. В конце концов те цепочки, которые находятся в таблице, но недоступны из остальных мест, могут быть собраны как мусор, а занимаемая ими память может быть использована повторно. Новые цепочки всегда вносятся в центральную таблицу как глобальные переменные, поэтому на их существование не влияют последующие входы в подпрограммы и выходы из подпрограмм. [31]
Специально предусмотрена возможность передачи вместе с именем функции ( в том случае, когда функция передается в подпрограмму как фактический параметр) среды ссылок; для этой цели служит примитив FUNCTION. Среда ссылок в момент передачи представляется указателем на текущую вершину А-списка. [32]
В общем случае простые переменные и массивы локальны для подпрограммы, в которой они описаны и используются. Ло-кальная среда ссылок для каждой подпрограммы создается во время трансляции. Во время выполнения ассоциации активируются при каждом входе в подпрограмму и дезактивируются при каждом выходе из нее; таким образом, при повторном входе в подпрограмму все локальные переменные и массивы имеют значения, которые они имели при последнем выходе из нее. Эта структура отражает основную структуру времени выполнения: память для переменных и массивов выделяется статически во время трансляции, а ссылки при трансляции заменяются прямыми адресами ( обычно базовый адрес смещение) тех ячеек памяти, где хранятся данные. Таким образом, во время выполнения нет необходимости в явных таблицах среды ссылок - среда компилируется в выполняемый машинный код. Благодаря этой структуре не требуется явно модифицировать среду ссылок при входе в подпрограмму или при выходе из нее; передача управления подпрограмме соответствующим образом неявно изменяет локальную среду ссылок. Такой способ прямой обработки локальных ссылок применим к простым переменным, массивам, меткам инструкций и к инструкциям формата ввода-вывода. [33]
В каждом языке программирования существуют свои, правила определения областей активности и областей существования ассоциаций. Изменение среды ссылок ifpo - исходит при передаче управления подпрограмме, возврате управления из подпрограммы, при входе и выходе из блока. Понятие блока, блочной структуры получило широкое распространение и используется во многих языках: среди них Алгол-60, PL-1, Паскаль, Симула и др. В языках с блочной структурой программный модуль ( головная программа или подпрограмма) представляется набором вложенных блоков. [34]
В каждый момент выполнения программы имеется множество активных ассоциаций. Это множество называют средой ссылок в данной точке программы. Среда ссылок определяет для каждой встретившейся ссылки на идентификатор соответствующую ассоциацию. Кроме операций именования и разыменования на среду ссылок влияют операции активации и деактивации ассоциаций. Операция активации делает имеющуюся ассоциацию между идентификатором и объектом программы или данных пригодной для использования в ссылках. [35]
На каждом из этих шагов нужно изменять среду ссылок. На рис. 6.16 изображены среды ссылок, действующие между любыми двумя соседними шагами. Заметим, что, когда процедура или метка передается новой активации подпрограммы в каче-стве параметра, передается также указатель на локальную таб-лицу, в которой была найдена ассоциация для фактического параметра. Например, на шаге 2 в качестве фактического параметра Р передается QHUM, а также указатель на локальную таблицу В, в которой имеется ассоциация для Q. На шаге 3, когда Р вызывает QHUxc через формальный параметр X, указатель статической цепи в таблице для ( ниж можно установить так, чтобы он указывал на таблицу В, создавая тем самым нужную для выполнения Qh m нелокальную среду. Читателю рекомендуется для каждого шага самостоятельно определить: каким образом можно перейти от предыдущей среды к следующей, имея только эту предыдущую среду; форматы таблиц, показанные на рис. 6.15; и выполняемую инструкцию программы. Заметим, что текущая локальная среда на каждом шаге задается специальным указателем головы статической цепи ( ГСЦ), который хранится в фиксированном месте. Чтобы яснее показать различные среды ссылок в разные моменты выполнения, мы использовали представление в виде дерева, а не непо средственно стековую структуру. Заметим, что локальные таблицы уничтожаются в порядке, строго обратном порядку их со-здания, и поэтому можно создавать и уничтожать таблицы, помещая их в единственный стек. [36]
С проблемой вложенной структуры операторов тесно свя зама проблема вложенной статической среды ссылок, являющаяся следствием организации программы в иерархию определений блоков и подпрограмм. Компилятору приходится следить за статической средой ссылок ( например, в таблице символов со стековой структурой), чтобы можно было определить тип идентификаторов в операторах, которые транслируются. Оптимизация также является важной частью многих компиляторов с Алгола, хотя из-за более сложной структуры программ оптимизировать программы, написанные на Алголе несколько труднее, чем программы на Фортране. [37]
В статье Вегнера [1971] в этом сборнике дается полезный обзор; в статье Джонстона [1971] предлагается контурная модель для представления сред ссылок; эта модель особенно полезна для ясного понимания сред, основанных на статической блочной структуре; в статье Органика и Клири [1971] описывается аппаратная реализация некоторых из рассмотренных понятий. Бойль и Гро [1970] рассматривают среды ссылок, основанные на статической блочной структуре, в теоретическом плане. [38]
Для того чтобы выделить в среде ссылок ассоциации, которые создаются в результате последнего изменения среды ссылок, используют понятие локальной среды ссылок. Под локальной средой ссылок понимают ту часть среды ссылок, которая была создана в результате последнего вхождения в блок или в подпрограмму. Остальную часть среды ссылок называют нелокальной средой ссылок. В последнем примере перед первым оператором печати print ( х, у) локальная среда ссылок состоит из двух ассоциаций, связывающих идентификаторы х, z с целыми переменными; нелокальная среда ссылок состоит из двух ассоциаций, связывающих идентификатор у с целой переменной и идентификатор А с вещественным массивом. [39]
Это значение становится начальным значением соответствующего формального параметра, который при дальнейшем выполнении подпрограммы рассматривается как локальная простая переменная. Находится позиция памяти, связанная с именем переменной в среде ссылок в момент вызова. Передается указатель на эту позицию. Ссылка на формальный параметр в вызываемой подпрограмме обрабатывается как косвенная ссылка через этот указатель на позицию фактического параметра. Присваивание значения формальному параметру изменяет значение фактического параметра в вызывающей программе. [40]
Вызовы подпрограмм строго вложены друг в друга; подпрограмма, вызванная последней, будет завершена первой, поэтому для хранения системных данных, связанных с вызовами подпрограмм, можно применить обычный стек записей активации. Отдельный связанный стек, называемый А-списком, используется для организации среды ссылок. [41]
Статическая область и стек не требуют подробных комментариев. Активационные записи подпрограмм, находящиеся в стеке, содержат значения деактивированных формальных параметров, локальных переменных и идентификаторов имен подпрограмм, поскольку для представления текущей среды ссылок используется метод центральной таблицы среды ссылок. Таким образом, стек является скрытым и не участвует непосредственно в обработке ссылок. [42]
Как влияют на выбор среды ссылок рекурсивные подпрограммы. В любой момент выполнения у рекурсивной подпрограммы может быть много одновременно существующих активаций. Среды ссылок в различных активациях одной подпрограммы могут в общем случае отличаться друг от друга. Таким образом, перед нами стоит задача определения среды ссылок для каждой активации подпрограммы. [43]
В каждый момент выполнения программы имеется множество активных ассоциаций. Это множество называют средой ссылок в данной точке программы. Среда ссылок определяет для каждой встретившейся ссылки на идентификатор соответствующую ассоциацию. Кроме операций именования и разыменования на среду ссылок влияют операции активации и деактивации ассоциаций. Операция активации делает имеющуюся ассоциацию между идентификатором и объектом программы или данных пригодной для использования в ссылках. [44]
Для того чтобы выделить в среде ссылок ассоциации, которые создаются в результате последнего изменения среды ссылок, используют понятие локальной среды ссылок. Под локальной средой ссылок понимают ту часть среды ссылок, которая была создана в результате последнего вхождения в блок или в подпрограмму. Остальную часть среды ссылок называют нелокальной средой ссылок. В последнем примере перед первым оператором печати print ( х, у) локальная среда ссылок состоит из двух ассоциаций, связывающих идентификаторы х, z с целыми переменными; нелокальная среда ссылок состоит из двух ассоциаций, связывающих идентификатор у с целой переменной и идентификатор А с вещественным массивом. [45]