Смекни!
smekni.com

Распределение памяти (стр. 3 из 5)

выделения памяти в этой области. В рассматриваемых языках нет

явного оператора для освобождения памяти, так что, когда память

исчерпана, система обращается к программе "сбора мусора".

Заметим, что для того, чтобы иметь возможность обнаружить мусор,

нужно знать, где расположены все указатели, включая те, которые

являются компонентами структурных величин.

Структуры 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 ). Когда происходит вызов санка,

он вычисляет значение фактического параметра ( если этот параметр

не переменная ) и передает адрес этого значения. В теле процедуры

при каждой ссылке на формальный параметр происходит вызов санка,

после чего для обращения к нужному значению используется

переданный санком адрес.

Различие между вызовом по ссылке и вызовом по имени

заключается в следующем: адрес фактического параметра,

вызываемого по ссылке, вычисляется только один раз, перед

фактическим входом в процедуру, в то время как для вызова по

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

обращение к формальному параметру.

Имя массива в качестве фактического параметра

В этом случае и фактический, и формальный параметр должны

быть массивами. Процедуре передается адрес первого элемента

массива ( для языков, которые не требуют информационных

векторов ) или адрес информационного вектора, и этот адрес

используется процедурой для ссылки на элементы массива.

Имя процедуры в качестве фактического параметра