выделения памяти в этой области. В рассматриваемых языках нет
явного оператора для освобождения памяти, так что, когда память
исчерпана, система обращается к программе "сбора мусора".
Заметим, что для того, чтобы иметь возможность обнаружить мусор,
нужно знать, где расположены все указатели, включая те, которые
являются компонентами структурных величин.
Структуры PL/1
Более сложную конструкцию имеют структуры, в которых
компоненты могут сами иметь подкомпоненты. Пример таких
структур - структуры языка PL/1. Такая структура есть дерево,
узлы которого связаны с именами компонент, а концевые узлы
имеют значения данных.
Если бы возможность иметь подкомпоненты была бы
единственным различием между записями по Хоору и структурами
PL/1 не было бы существенной разницы во время выполнения
программы; можно было бы разместить все компоненты и
подкомпоненты так, чтобы каждая имела фиксированное смещение
относительно начала структуры и это смещение было бы известно во
время компиляции. Однако в языке PL/1 существует еще два
расширения. С целью экономии памяти атрибут CELL для компоненты
требует, чтобы все ее подкомпоненты непременно занимали одно и
тоже место в памяти. В любое заданное время только одна из
нескольких переменных может иметь значение. Присваивание значения
подкомпоненте приводит к тому, что подкомпонента, к которой
обращались ранее утрачивает свое значение.
Подобная возможность вызовет осложнения во время компиляции,
но в действительности не очень изменяет код готовой программы,
если только объектная программа не должна проверять при каждом
обращении к подкомпоненте, что значение подкомпоненты
действительно существует.
Для другого расширения требуются более сложные
административные функции во время выполнения программы. В PL/1
корневой узел структурного дерева или любая из подкомпонент могут
быть снабжены размерностями.
Так как выражения, которые определяют границы изменения
индексов, должны быть вычислены при выполнении программы, для
них, как и в случае массивов, следует употреблятъ опители, или
информационные векторы. Т.е. нам необходимы информационные
векторы для всех компонент имеющих размерность большую единицы.
Структуры данных по Стендишу
Следующий шаг в развитии - структуры данных, которые не
могут быть реализованы эффективно, но которые богаче и мощнее.
Структуры данных предложенные Стендишом изменяются во время
работы программы. Динамически могут изменяться не только
размерности компонент, но и число компопонент и их типы.
Обычно во время компиляции ничего не известно, а все делается
во время выполнения программы на основе описателей, которые
сами строятся в это же время.
Во время выполнения программы необходимо хранить описатель
для каждой структурной величины. Действительно, этот описатель
аналогичен набору элементов таблицы символов, используемому
компилятором при компиляции, скажем, структур PL/1. Такие
описания структур лучше всего реализуются в виде дерева, где
для каждого узла должно быть по крайней мере известно:
1) концевой ли это узел или нет;
2) если узел концевой, то каков его тип;
3) если узел концевой, то указатель на значение, если
таковое существует;
4) если узел не концевой, то указатели на узлы для
подкомпонент;
5) размерности подкомпонент.
Всякий раз при обращении к значению компоненты должен быть
проинтерпретирован описатель. Начиная с корневого узла, находится
путь к узлу, к которому обращаются, проверяется тип этого узла и,
наконец, используется или изменяется его значение.
6. Соответствие фактических и формальных параметров
Рассмотрим различные типы формальных параметров и их
соответствие фактическим параметрам и покажем, как каждый из них
может быть реализован. Под формальным параметром мы понимаем
идентификатор в процедуре, который заменяется другим
идентификатором или выражением при вызове процедуры.
При обращении к процедуре, скажем, устанавливается некоторым
образом связь между формальными параметрами и фактическими
параметрами.
Когда в каком-нибудь языке происходит обращение к процедуре,
ей передается список адресов аргументов. Процедура переписывает
эти адреса в свою собственную область данных и использует их для
установления соответствия фактических и формальных параметров.
Кроме фактических параметров, часто имеется несколько неявных
параметров, о которых программист не знает. Один из них это,
конечно, адрес возврата. Следовательно, вызываемой процедуре
передается список такого вида:
неявный параметр 1
.
.
.
неявныи параметр m
адрес фактического параметра 1
.
.
.
адрес фактического параметра n
Что представляют собой адреса в списке? Это зависит от языка
и от типа параметра. Нише перечислены типы параметров, которые
мы будем рассматривать:
1) вызов по ссылке;
2) вызов по значению;
3) вызов по результату;
4) фиктивные аргументы;
5) вызов по имени;
6) имена массивов в качестве фактических параметров;
7) имена процедур в качестве фактических параметров.
Вызов по ссылке ( by reference )
Этот тип параметра самый простой для реализации.
Фактический параметр обрабатывается во время выполнения
программы перед вызовом; если он не является переменной или
константой, он вычисляется и запоминается во временной ячейке.
Затем вычисляется адрес ( переменной, константы или временной
ячейки ), и этот адрес передается вызываемой процедуре.
Вызываемая процедура использует его для ссылки на ячейку (ячейки),
содержащую значение.
Вызов по значению ( by value )
При этом типе соответствия формального и фактического
параметров вызываемая процедура имеет ячейку, выделенную в ее
области данных для значения формального параметра этого типа. Как
и при вызове по ссылке, адрес фактического параметра вычисляется
перед вызовом и передается вызываемой процедуре в списке
параметров. Однако перед фактическим началом выполнения процедура
выбирает значение по адресу и заносит его в свою собственную
ячейку. Эта ячейка затем используется как ячейка для величины
точно так же, как любая переменная, локализованная в процедуре.
Таким образом, нет никакого способа изменить в процедуре значение
фактического параметра.
Вызов по результату ( by result )
В языке АЛГОЛ W для любого формального параметра Х,
объявленного параметром RESULT, справедливо следующее:
1. Для параметра Х отводится ячейка в области данных
процедуры. Эта ячейка используется в процедуре как локализованная
ячейка для переменной Х.
2. Как и в случае параметра VALUE, при рызоре при вызове
процедуры вычисляется и передается адрес фактического параметра.
3. Когда выполнение процедуры заканчивается, полученное
значение Х запоминается по адресу, описанному в п.2.
Другими словами, параметр RESULT есть переменная,
локализованная в процедуре, значение которой при выходе
запоминается в соответствующем фактическом параметре (который
должен быть конечно, переменной ). Понятие RESULT было
предназначено для того, чтобы дополнить в АЛГОЛе вызов по имени
( который описан ниже ), так как последний весьма неэффективен и
обладает большими возможностями, чем это необходимо в
большинстве случаев.
Фиктивные аргументы
В развитых языках следующие фактические параметры
обрабатываются по-разному:
1) константы;
2) выражения, которые не являются переменными;
З) переменные, чьи характеристики отличаются от характеристик
указанных для соответствующих формальных параметров.
Для такого фактического параметра в вызывающей процедуре
заводится временная переменная. Фактический параметр вычисляется
и запоминается во временной переменпой, и адрес этой переменной
передается в списке параметров. Такая переменная называется
фиктивным аргументом.
Вызов по имени
Согласно сообщению о языке АЛГОЛ, использование вызова
параметра по имени означает буквальную замену имени формального
параметра фактическим параметром.
Получить эффективную реализацию с помощью такой текстовой
замены, конечно, нельзя, и мы должны разработать соответствующий
эквивалентный способ.
Обычный способ реализации вызова параметров по имени
состоит в том, чтобы иметь отдельную программу или процедуру в
объектном коде для каждого такого параметра. Для такой программы
был введен термин "санк" ( thunk ). Когда происходит вызов санка,
он вычисляет значение фактического параметра ( если этот параметр
не переменная ) и передает адрес этого значения. В теле процедуры
при каждой ссылке на формальный параметр происходит вызов санка,
после чего для обращения к нужному значению используется
переданный санком адрес.
Различие между вызовом по ссылке и вызовом по имени
заключается в следующем: адрес фактического параметра,
вызываемого по ссылке, вычисляется только один раз, перед
фактическим входом в процедуру, в то время как для вызова по
имени адрес вычисляется всякий раз, когда в теле процедуры есть
обращение к формальному параметру.
Имя массива в качестве фактического параметра
В этом случае и фактический, и формальный параметр должны
быть массивами. Процедуре передается адрес первого элемента
массива ( для языков, которые не требуют информационных
векторов ) или адрес информационного вектора, и этот адрес
используется процедурой для ссылки на элементы массива.
Имя процедуры в качестве фактического параметра