Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Реализация
подпрограмм
В этой главе...
Джон Кемени (John Kemeny)
Джон Кемени и его коллега
Томас Курц (Thomas Kurtz)
в начале 1960-х годов разрабо-
тали в Дартмуте компиляторы
для нескольких диалектов языков
ALGOL и FORTRAN. В 1963 году
Кемени приступил к созданию
языка BASIC и закончил его
1964 году.
393
Реализация подпрограмм
Ц
ель этой главы — исследовать методы реализации подпрограмм. В ней читатель
получит некоторое представление о том, каким образом "работают" языки про-
граммирования, а также почему язык ALGOL 60 в начале 1960-х годов представлял со-
бой вызов ничего не подозревавшим создателям компиляторов. Мы начнем с простей-
шей разновидности подпрограмм — подпрограмм в языке FORTRAN 77, а затем перей-
дем к более сложным подпрограммам в таких языках со статическим обзором данных,
как Pascal и Ada. Возрастающие трудности, связанные с реализацией подпрограмм в этих
языках, вызваны необходимостью поддержки рекурсии и механизмов доступа к нело-
кальным переменным.
Детально обсуждаются и сравниваются между собой два метода доступа к нелокаль-
ным переменным в языках со статическим обзором данных — статические цепочки и
дисплеи. Кратко описаны способы реализации блоков. Рассмотрены виды доступа к не-
локальным переменным в языках с динамическим обзором данных. В заключение опи-
сывается метод реализации параметров, представляющих собой имена подпрограмм.
9.1. Общая семантика вызовов и возвратов
Вызов подпрограммы и операции возврата управления, взятые вместе, называются
связыванием подпрограмм (subprogram linkage). Любой метод реализации подпро-
грамм должен основываться на семантике связывания подпрограмм.
Вызов подпрограммы в обычном языке программирования связан с большим количе-
ством действий. Так, он содержит механизм передачи параметров. Если локальные пе-
ременные не являются статическими, вызов приводит к выделению памяти для локаль-
ных переменных, объявленных в вызываемой подпрограмме, и связывает их с этими
ячейками памяти. Он должен сохранять текущее состояние выполняемого модуля, вы-
звавшего подпрограмму; передавать управление коду подпрограммы и гарантировать,
что оно будет возвращено в нужное место после выполнения подпрограммы. В заключе-
ние вызов должен обеспечить доступ к нелокальным переменным, видимым в вызывае-
мой подпрограмме.
Возврат управления из подпрограммы также достаточно сложен. Если параметры
подпрограммы передаются в режиме вывода и по копии, при возврате управления внача-
ле следует присвоить фактическим параметрам локальные значения соответствующих
формальных параметров. Затем должна быть освобождена память, использованная для
хранения локальных переменных, и восстановлено текущее положение выбывающего
программного модуля. Для возврата механизма доступа к нелокальным переменным в
состояние, в котором он пребывал до вызова подпрограммы, также требуется выполнить
несколько действий. В заключение управление должно быть возвращено вызывающему
программному модулю.
9.2. Реализация подпрограмм на языке FORTRAN 77
Мы начнем с относительно простого примера— подпрограмм в языке FORTRAN 77.
Все обращения к нелокальным переменным в языке FORTRAN 77 осуществляются через
блоки COMMON. Поскольку блоки COMMON не относятся к механизму связывания под-
программ, они здесь не обсуждаются -Другим упрощающим дело обстоятельством явля-
ется тот факт, что в языке FORTRAN 77 подпрограммы не могут быть рекурсивными.
394 Глава 9. Реализация подпрограмм
Более того, во многих реализациях переменные, объявленные в подпрограммах, разме-
щаются статически.
Семантика вызова подпрограмм в языке FORTRAN 77 требует выполнения следую-
щих действий.
При возврате из подпрограмм в языке FORTRAN 77 выполняются следующие действия.
Действия, связанные с вызовом и возвратом, требуют выделения памяти для следую-
щих данных.
Информация о состоянии вызывающего модуля.
Параметры.
Адрес возврата.
Возвращаемое значение функции.
Эти данные вместе с локальными переменными и кодом подпрограммы формируют пол-
ную совокупность информации, необходимой подпрограмме для своего выполнения и
возврата управления вызывающему модулю.
Подпрограмма на языке FORTRAN 77 состоит из двух отдельных частей: собственно
кода подпрограммы, являющегося неизменным, а также локальных переменных и дан-
ных, перечисленных выше, которые могут изменяться при выполнении подпрограммы.
Обе эти части имеют фиксированные размеры.
Значение функции
Локальные переменные
Формат, или структура, части подпрограммы, не являющейся кодом, называется за-
писью активации (activation record), или активационной записью, поскольку данные,
которые она описывает, относятся только к активации подпрограммы. Форма записи ак-
тивации является статичной. Экземпляр записи активации
(activation record instance) — это конкретный образец записи ак-
тивации, или набор данных в форме активационной записи.
Параметры
Адрес возврата
Поскольку язык FORTRAN 77 не поддерживает рекурсии, в
каждый момент времени может существовать только одна ак-
тивная версия данной подпрограммы и только один экземпляр
записи активации подпрограммы. Возможная структура записей
активации в языке FORTRAN 77 показана на рис. 9.1. Здесь и в
оставшейся части главы мы пропускаем сохраненное текущее Рис 9.1. Запись актива-
состояние вызывающего модуля, поскольку это не относится к щи в языке FORTRAN 77
предмету нашего обсуждения.
9.2. Реализация подпрограмм на языке FORTRAN 77 395
Поскольку экземпляр записи активации подпрограммы в языке FORTRAN 77 имеет
фиксированный размер, его можно размещать в памяти статически. Фактически, его
можно присоединить к коду подпрограммы.
На рис. 9.2 показана программа на языке FORTRAN 77, состоящая из COMMON-блока,
главного модуля и трех подпрограмм: А, В и С. Хотя на рисунке показано, что все сегмен-
ты кода хранятся отдельно от всех экземпляров записей активации, в некоторых случаях
экземпляры записей активации присоединяются к соответствующему сегменту кода.
Данные '
Код
|
main/ |
|
А1 |
|
> |
|
ъ< |
|
с J |
|
MA JN < |
|
А |
|
■ |
|
' |
Общая память
Локальные переменные
Локальные переменные
Параметры
Адрес возврата
Локальные переменные
Параметры
Адрес возврата
Локальные переменные
Параметры
Адрес возврата
Рис. 9.2. Код и запись активации
программы в языке FORTRAN 77
Компилятор не создает полную программу на языке FORTRAN 77, показанную на
рис. 9.2. Действительно, поскольку существует независимая компиляция, четыре про-
граммных модуля — MAIN, А, В и С — могут быть скомпилированы в разное время. По-
сле компиляции каждого модуля его машинный код вместе со списком ссылок на внеш-
ние подпрограммы и нелокальными переменными записывается в файл. Выполняемая
программа, показанная на рис. 9.2, объединяется в одно целое редактором связей
(linker), являющимся частью операционной системы. (Иногда редакторы связей называ-
ются загрузчиками.) При вызове редактора связей для главной программы его первой
задачей является поиск файлов, содержащих оттранслированные подпрограммы вместе с
их экземплярами записей активации, и загрузка их в память. Он должен также опреде-
396 Глава 9. Реализация подпрограмм
лить размер всех COMMON-блоков и разместить их в памяти. Затем редактор связей при-
сваивает входные адреса вызываемых подпрограмм целевым адресам соответствующих
вызовов, находящихся в главном модуле. То же самое он делает со всеми вызовами,
встречающимися в загружаемых подпрограммах, и всеми вызовами стандартных под-
программ языка FORTRAN. В примере, показанном выше, редактор связей вызывался
для модуля MAIN. Редактор связей должен был найти машинный код программ А, В и С
вместе с их экземплярами активационных записей и загрузить в память вместе с кодом
модуля MAIN. Затем он должен был вставить все целевые адреса для вызовов подпро-
грамм А, В и С, а также вызовов всех библиотечных подпрограмм в подпрограммах А, В,
С и MAIN. Кроме того, все ссылки на переменные в COMMON-блоках должны были быть
заменены соответствующими адресами. Во многих случаях ссылки на нелокальные пе-
ременные обрабатывают с помощью относительной адресации в блоке, избегая необхо-
димости вставки адресов.
В языке FORTRAN 90 подпрограммы могут быть вложенными (с помощью статиче-
ского обзора) и рекурсивными. Это приводит к тому, что их реализация становится по-
хожей на язык ALGOL. Методы реализации этих языков подробно обсуждаются в сле-
дующем разделе.
9.3. Реализация подпрограмм на языках, подобных
языку ALGOL
Рассмотрим реализацию связывания подпрограмм в языках со статическим обзором
данных, подобных языку ALGOL, — Pascal, Ada, FORTRAN 90 и Delphi, основное вни-
мание уделяя операциям вызова и возврата управления во все более усложняющихся си-
туациях. Детально описываются два связанных между собой, но разных подхода к реали-
зации доступа к нелокальным переменным, называемых статическими цепочками
(static chains) и индикаторами (dispays).
Несмотря на то что в языках С, C++ и Java не допускаются вложенные подпрограм-
мы, их реализация похожа на реализацию других языков со статическим обзором дан-
ных. Отличие заключается в поддержке ссылок на нелокальные переменные, которая
может быть намного проще, если запрещаются вложенные программы.
9.3.1. Более сложные записи активации
Связывание подпрограмм в языках, подобных языку ALGOL, осуществляется более
сложным образом, чем связывание подпрограмм в языке FORTRAN 77. Это происходит
по следующим причинам.
Обычно параметры могут передаваться двумя разными способами. Например, во
многих языках они передаются по значению или по ссылке.
Переменные, объявленные в подпрограммах, часто являются динамическими.
Рекурсия добавляет возможность одновременно выполнять несколько активаций
подпрограммы. Это означает, что одновременно может существовать несколько
экземпляров подпрограммы, выполняющихся частично, активирующихся с помо-
щью одного внешнего вызова подпрограммы и нескольких рекурсивных вызовов.
Следовательно, для рекурсии требуется несколько экземпляров записей актива-
ции, по одной на каждую активацию подпрограммы, которые могут существовать
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 397
одновременно. Для каждой активации нужна своя собственная копия формального
параметра и динамически размещаемые локальные переменные вместе с адресами
возврата.
■ В языках, подобных языку ALGOL, для доступа к нелокальным переменным ис-
пользуется статический обзор данных. Поддержка такого доступа к нелокальным
переменным должна быть частью механизма связывания подпрограмм.
Формат записи активации для данной подпрограммы в языках со статическим обзо-
ром данных во время компиляции уже известен. В процедурах языка Pascal размер запи-
сей активации также известен, поскольку все локальные данные процедуры имеют фик-
сированный размер. Это условие не выполняется в некоторых других языках, в которых
размер локального массива может зависеть от значения фактического параметра. В этих
случаях формат записи активации является статическим, а ее размер — динамическим. В
языках, подобных языку ALGOL, экземпляры записей активации должны создаваться
динамически. Типичная запись активации для языка, подобного языку ALGOL, приведе-
на на рис. 9.3.
Локальные переменные
Параметры
Динамическая связь
Статическая связь
Адрес возврата
t
Вершина
стека
Рис. 9.3. Типичная запись активации
в языке, подобном языку ALGOL
Поскольку адрес возврата, статическая связь, динамическая связь и параметры поме-
щаются в запись активации вызывающим модулем, они должны быть первыми элемен-
тами записи активации. В этой главе мы предполагаем, что стек растет вверх. Следова-
тельно, адрес возврата окажется на дне записи активации.
Адрес возврата часто содержит указатель на сегмент кода вызывающего модуля и отно-
сительный адрес команды, следующей за вызовом в этом сегменте кода. Статическая
связь (static link), которую иногда называют указателем статического обзора, указывает на
дно экземпляра записи активации статического предка. Она используется для доступа к не-
локальным переменным. Статические связи детально обсуждаются в разделе 9.3.4. Дина-
мическая связь (dynamic link)— это указатель на вершину экземпляра записи активации
вызывающего модуля. В языках со статическим обзором данных эта связь используется
при разрушении текущего экземпляра записи активации после выполнения процедуры. Ди-
намическая связь нужна, поскольку в некоторых случаях в стеке находятся переменные,
помещенные туда подпрограммой после записи активации. Например, там могут находить-
ся временные переменные, необходимые для машинного кода подпрограммы. Таким обра-
зом, даже зная размер записи активации, его нельзя просто вычесть из указателя на верши-
ну стека для того, чтобы удалить запись. Фактические параметры в записи активации явля-
ются значениями, или адресами, задаваемыми вызывающим модулем.
398
Глава 9. Реализация подпрограмм
Локальные скалярные переменные связываются с ячейками памяти в экземпляре за-
писи активации. Локальные переменные, представляющие собой структуры, иногда раз-
мещаются в произвольном месте, а в запись активации заносятся только их дескрипторы
и указатели на места их хранения. Локальные переменные размещаются в памяти и мо-
гут инициализироваться вызываемой подпрограммой, поэтому они заносятся в запись
активации последними.
Рассмотрим следующую скелетную процедуру на языке Pascal:
procedure sub(var total : real; part : integer);
var list : array [1..5] of integer;
sum : real;
begin
end;
Запись активации подпрограммы sub показана на рис. 9.4.
Локальная переменная
Локальная переменная
Локальная переменная
Локальная переменная
Локальная переменная
sum
list [5]
list [4]
list [3]
list [2]
list [1]
Локальная переменная
part
Параметр
to! ,il
Параметр
Динамическая связь
Статическая связь
Адрес возврата
Рис. 9.4. Запись активации процедуры sub
При активации процедуры динамически создается экземпляр записи активации этой
процедуры. Как указывалось ранее, формат этой записи во время компиляции является
фиксированным, хотя размер записи в других языках, отличающихся от языка Pascal,
может зависеть от вызова. Поскольку семантика вызова и возврата указывает, что под-
программа, вызванная последней, завершается первой, вполне резонно поместить созда-
ваемые экземпляры записей активации в стек. Этот стек является частью системы под-
держки выполнения программ и поэтому называется стеком выполняемой программы
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 399
(run-time stack), хотя мы будем называть его просто стеком. Каждая активация процеду-
ры, независимо от того, является ли эта процедура рекурсивной или нет, создает новый
экземпляр записи активации в стеке. Это обеспечивает требуемое разделение копий па-
раметров, локальных переменных и адресов возврата.
Напомним, что, как указывалось в главе 8, подпрограмма является активной, начи-
ная с момента ее вызова и заканчивая моментом ее завершения. Когда подпрограмма
становится неактивной, ее локальные области видимости перестают существовать и ее
среда ссылок больше не имеет смысла. Таким образом, в этот момент ее экземпляр запи-
си активации разрушается.
9.3.2. Пример без рекурсии и нелокальных ссылок
Вследствие сложности реализации связывания подпрограмм мы рассмотрим их в не-
сколько этапов. Во-первых, изучим пример программы, в которой нет обращений к не-
локальным переменным и рекурсивных вызовов. В этом примере не используется стати-
ческая связь. Затем мы обсудим, как реализовать рекурсию и доступ к нелокальным пе-
ременным.
Рассмотрим следующий скелетный пример программы:
program MAIN_1;
var P : real;
procedure A(X : integer);
var Y : boolean;
procedure C(Q : boolean);
begin { С }
. . . < 3
end; { С }
begin { A }
< 2
C(Y);
end; { A }
procedure B(R : real);
var S, T : integer;
begin { В }
< 1
A(S);
end; {B}
begin { MAIN_1 }
B(P);
end. { MAIN_1 }
Последовательность вызовов процедур в этой программе такова:
MAIN_1 вызывает В
В вызывает А
А вызывает С
Содержимое стека в точках, отмеченных цифрами 1, 2 и 3, показано на рис. 9.5.
400 Глава 9. Реализация подпрограмм
В точке 1 в стеке содержатся только экземпляры записей активации программы
MAIN_1 и процедуры В. Когда процедура В вызывает процедуру А, в стек заносится эк-
земпляр записи активации процедуры А. Когда процедура А вызывает процедуру С, в
стек заносится экземпляр активации процедуры С. Когда выполнение процедуры С за-
вершается, экземпляр ее записи активации удаляется из стека, а динамическая связь ис-
пользуется для переопределения указателя на вершину стека. Аналогичный процесс про-
исходит, когда завершается выполнение процедур А и В. После возврата управления из
процедуры В в программу MAIN_1 стек содержит только экземпляр записи активации
программы MAIN_1. Заметим, что некоторые системы реализации языков программиро-
вания в действительности не хранят в стеке экземпляр записи активации главной про-
граммы, как это показано на рисунке. Однако описанная ситуация возможна, и это уп-
рощает как саму реализацию, так и ее обсуждение. В данном примере и во всех осталь-
ных примерах этой главы мы предполагаем, что стек увеличивается в порядке
возрастания адресов.
ЭЗА
С
вершин
а стека
ЭЗА
Л
Локальная переменная
Локальная переменная
Параметр
ЭЗА
В
Динамическая связь
Статическая связь
Возврат (в MAIN)
ЭЗА г
MAIN \
Локальная переменная
ЭЗА
ЭЗА
MAIN \
ЭЗА
А
вершин
а стека
ЭЗА
В
ЭЗА
MAIN
|
Локальная переменная |
Y |
||
|
Параметр |
X |
||
|
-< |
Динамическая связь». |
||
|
Статическая связь |
|||
|
Возврат(в В) |
|||
|
Локальная переменная |
1 |
||
|
Локальная переменная |
S |
||
|
Параметр |
R |
||
|
Динамическая связь». |
|||
|
Статическая связь |
|||
|
Возврат (в MAIN) |
|||
|
< |
Локальная переменная |
Р |
|
веошин |
||
|
Параметр |
q а стека |
|
|
Динамическая связь»_ |
||
|
Статическая связь |
||
|
Возврат(в А) |
||
|
Локальная переменная |
Y |
|
|
Параметр |
X |
|
|
Динамическая связь» |
—, |
|
|
' Статическая связь |
||
|
Возврат(в В) |
||
|
Локальная переменная |
1 |
|
|
Локальная переменная |
S |
|
|
Параметр |
R |
|
|
Динамическая связь». |
||
|
Статическая связь |
||
|
Возврате MAIN) |
||
|
Локальная переменная |
1 |
> |
ЭЗА- экземпляр записи активации
Рис. 9.5. Содержимое стека в трех точках программы
Совокупность динамических связей, содержащихся в стеке в данный момент време-
ни, называется динамической цепочкой (dynamic chain), или цепочкой вызовов (call
chain). В ней описана динамическая история того, каким образом выполнение програм-
мы достигло текущей точки, которая всегда находится в сегменте кода, экземпляр записи
активации которого расположен на вершине стека. Ссылки на локальные переменные
401
9.3. Реализация подпрограмм на языках, подобных языку ALGOL
могут быть представлены в коде с помощью смещения относительно начала записи ак-
тивации в соответствующей локальной области видимости. Такое смещение называется
локальным (local offset).
Локальное смещение переменной в записи активации можно определить во время ком-
пиляции, используя порядок, тип и размеры переменных, объявленных в процедуре, соот-
ветствующей данной записи активации. Предположим для простоты, что все переменные в
записи активации занимают по одной ячейке. Первую локальную переменную, объявлен-
ную в процедуре, можно разместить в ячейке, номер которой вычисляется следующим об-
разом: три плюс количество параметров, считая со дна стека (первые три ячейки предна-
значены для хранения адреса возврата, статической связи и динамической связи). Вторая
локальная переменная может быть размещена на одну ячейку ближе к вершине стека и так
далее. Например, рассмотрим предыдущую скелетную программу. В процедуре А локаль-
ное смещение переменной Y равно 4. Аналогично, в процедуре В локальное смещение пе-
ременной S равно 4, а переменная Т имеет локальное смещение, равное 5.
9.3.3. Рекурсия
Рассмотрим следующий пример программы на языке С, в которой для вычисления
факториала используется рекурсия:
int factorial(int n) {
< 1
if (n <= 1)
return 1 ;
else return (n * factorial(n - 1));
< 2
}
void main() {
int value;
value = factorial(30;
< 1
}
Формат записи активации функции factorial показан Значение функции
Параметр
на рис. 9.6. Заметим, что запись имеет дополнительное поле
для возвращаемого значения функции.
Динамическая связь
Статическая связь
Адрес возврата
На рис. 9.7 показано содержимое стека, соответствующее
трем разным ситуациям, когда выполнение программы дости-
гает точки 1 в функции factorial. В каждом случае пока-
зана дополнительная активация функции с неопределенным
возвращаемым значением. Первый экземпляр активационной
записи функции содержит адрес возврата в вызывающую
функцию main. Остальные содержат адрес возврата в саму Рис. 9.6. Запись актива-
функцию, соответствующий рекурсивным вызовам. ции функции factorial
402
Глава 9. Реализация подпрограмм
вершина
стека
вершина
{
{
Первый ЭЗА
factorial
ЭЗА
main
Второй ЭЗА
factorial
ПервыйЭЗА f
factorial
ЭЗА
main
|
Значение функции |
? |
|
|
Параметр |
3 |
п |
|
Динамическая связь |
||
|
Статическая связь |
||
|
Возврат (в main ) |
||
|
Локальная переменная |
7 |
cli |
первый вызов
вершина
Значение функции
Параметр
Динамическая связь
Статическая связь
Возврат (в factorial)
Значение функции
Параметр
Динамическая связь
Статическая связь
Возврат(в mam )
стека
Локальная переменная ?
с,|'ата1ёа
Третий ЭЗА ,
factorial
Второй ЭЗА
factorial
Первый ЭЗА ;
factorial
ЭЗА
main
ш V
|
F |
|||
|
Значение функции |
? |
||
|
Параметр |
1 |
п |
|
|
Динамическая связь |
|||
|
Статическая связь |
|||
|
Возврат (в factorial) |
|||
|
Значение функции |
? |
||
|
Параметр |
2 |
п |
|
|
Динамическая связь |
|||
|
Статическая связь |
|||
|
Возврат (в factorial) |
|||
|
Значение функции |
? |
||
|
Параметр |
3 |
п |
|
|
Динамическая связь |
|||
|
Статическая связь |
|||
|
Возврат (в main) |
|||
|
Локальная переменная |
? |
fl |
k+ |
третий вызов
второй вызов
ЭЗА - передать значение первого адрес
Рис. 9.7. Содержимое стека в точке 1 функции factorial
403
9.3. Реализация подпрограмм на языках, подобных языку ALGOL
вершина
Третий ЭЗА
factorial
Второй ЭЗА
factorial
Первый ЭЗА
factorial
ЭЗА
та
ЗА С
in V.
|
Значение функции |
1 |
||
|
Параметр |
1 |
п |
|
|
Динамическая связь |
|||
|
Статическая связь |
|||
|
Возврат (в factorial) |
|||
|
Значение функции |
? |
||
|
Параметр |
2 |
п |
|
|
Динамическая связь |
|||
|
Статическая связь |
|||
|
Возврат (в factorial) |
|||
|
Значение функции |
? |
||
|
Параметр |
3 |
п |
|
|
Динамическая связь |
|||
|
Статическая связь |
|||
|
Возврат (в main) |
|||
|
Локальная переменная |
? |
и |
14 |
вершина
ПервыйЭЗА
factorial
ЭЗА
П'Л
ЗА Г
iii \
|
Значение функции |
6 |
||
|
Параметр |
3 |
п |
|
|
Динамическая связь |
•- |
• |
|
|
Статическая связь |
|||
|
Возврат (в main) |
|||
|
Локальная переменная |
? |
и |
В точке 2 функции
factorial
третий вызов выполнен
В точке 2 функции
:-i i о :л!
первый вызов выполнен
вершина
стека
Значение функции
Параметр
Динамическая связь
Второй ЭЗА
factorial
Статическая связь
Возврат (в factorial)
Значение функции
Параметр
Динамическая связь
Первый ЭЗА
factorial
Статическая связь
Возврат (в main)
Локальная переменная ■>
Локальная переменная
{
ЭЗА
main
ЭЗА С
■nain \
вершина
_ стека
В точке 2 функции
factorial
второй вызов выполнен
В точке 3 функции
main
окончательные результаты
ЭЗА - экземпляр записи активации
Рис. 9.8. Содержимое стека во время выполнения функций main и factorial
404 Глава 9. Реализация подпрограмм
На рис. 9.8 показано содержимое стека, соответствующее трем разным ситуациям,
когда выполнение программы достигает точки 2 в функции factorial. Точка 2 соот-
ветствует случаю, когда оператор return уже выполнен, а запись активации из стека
еще не удалена. Напомним, что код функции умножает текущее значение параметра п на
значение, возвращаемое при рекурсивном вызове функции. При первом вызове функция
factorial возвращает значение 1. В этом случае копия параметра п в экземпляре за-
писи активации имеет значение 1. Результат, равный 1, передается второй активации
функции factorial для умножения на значение ее параметра п, равное 2. Значение 2
возвращается первой активации функции factorial для умножения на значение ее па-
раметра п, равное 3, что дает в результате значение б, которое затем возвращается в
первый вызов функции factorial в функции main.
9.3.4. Механизмы реализации нелокальных ссылок
Существуют два основных способа доступа к нелокальным переменным в языках со
статическим обзором данных: статические цепочки и индикаторы. Оба эти способа де-
тально изучаются в следующих разделах.
Ссылка на нелокальную переменную требует выполнения двухэтапного процесса. Все
нелокальные переменные содержатся в существующих экземплярах записей активации и,
следовательно, находятся где-то в стеке. Для доступа к нелокальной переменной сначала
нужно найти в стеке экземпляр записи активации, в котором содержится эта переменная.
Затем следует использовать ее локальное смещение в экземпляре записи активации.
Поиск нужного экземпляра записи активации представляет собой более интересную и
трудную проблему. Во-первых, заметим, что в данной подпрограмме видимыми и дос-
тупными являются только те переменные, которые объявлены в области видимости ста-
тических предков. Во-вторых, если обращения к переменным статических предков нахо-
дятся во вложенной процедуре, существование экземпляров записей активации всех этих
предков гарантируется правилами семантики языков со статическим обзором данных:
процедуру можно вызвать, только если активны все программные модули, являющиеся
ее статическими предками. Если конкретный статический предок не активен, его локаль-
ные переменные не связаны с ячейками памяти, следовательно, открывать доступ к ним
не имеет смысла.
Заметим, что, хотя в стеке должен существовать экземпляр активационной записи
предка, эта запись не обязана соседствовать с экземпляром записи активации его потом-
ка. Эта ситуация проиллюстрирована примером в разделе 9.3.4.1.
Семантика ссылок на нелокальные переменные означает, что при поиске переменной
во вложенных областях видимости следует сначала найти ближайшее вложенное объяв-
ление. Таким образом, для обеспечения доступа к нелокальным ссылкам мы должны
иметь возможность находить в стеке все экземпляры активационных записей, соответст-
вующих статическим предкам. Это наблюдение приводит к двум методам, описанным в
следующих разделах.
Мы откладываем рассмотрение вопросов, связанных с блоками, до раздела 9.4, а в
оставшейся, части раздела 9.3 все области видимости определяются подпрограммами.
Поскольку в языках С и C++ вложенные функции не допускаются (блоками создаются
только статические области видимости), все изложенное в данном разделе к этим языкам
не относится.
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 405
9.3.4.7. Статические цепочки
Статическая цепочка — это цепочка статических связей, соединяющих некоторые
экземпляры активационных записей в стеке.
Во время выполнения процедуры Р статическая связь ее экземпляра активационной
записи указывает на экземпляр активационной записи программного модуля, являюще-
гося статическим предком процедуры Р. Статическая связь экземпляра записи активации
предка, в свою очередь, указывает на экземпляр записи активации программного модуля,
являющегося его статическим предком, если он существует. Таким образом, все статиче-
ские предки выполняемой подпрограммы связываются в статическую цепочку в порядке
ослабления родственных связей (первым является непосредственный предок, за ним —
его предок и так далее). Эту цепочку можно использовать для доступа к нелокальным
переменным в языках со статическим обзором данных.
Поиск нужного экземпляра записи активации, соответствующего нелокальной пере-
менной, с помощью статических связей становится направленным. Чтобы найти экземп-
ляр активационной записи, содержащий нелокальную переменную, следует в статиче-
ской цепочке обнаружить экземпляр записи активации статического предка, содержащий
эту переменную. Однако это можно сделать намного проще. Поскольку вложенные об-
ласти видимости во время компиляции известны, компилятор может определить не толь-
ко ссылку на нелокальную переменную, но и длину статической цепочки, которую нужно
отмерить, чтобы достичь экземпляр записи активации, содержащий искомый нелокаль-
ный объект.
Будем называть статической глубиной (static depth) целое число, связанное со ста-
тической областью видимости переменной и указывающее, насколько глубоко вложена
эта область в самую внешнюю область видимости. У главной программы в языке Pascal
статическая глубина равна 0. Если процедура А определяется только внутри главной про-
граммы, то ее статическая глубина равна 1. Если процедура А содержит определение
вложенной процедуры В, то статическая глубина процедуры В равна 2.
Длина статической цепочки, которую нужно пройти, чтобы добраться до нужного эк-
земпляра активационной записи, содержащей нелокальную ссылку на переменную X, в
точности равна разности между статической глубиной процедуры, содержащей ссылку
на переменную X, и статической глубиной процедуры, содержащей объявление перемен-
ной X. Эта разность называется глубиной вложения ссылки (nesting depth), или смеще-
нием по цепочке (chain offset). Фактическую ссылку можно представить в виде пары
(смещение по цепочке, локальное смещение), состоящей из целых чисел, где смещение
по цепочке является количеством связей, которые отделяют нужный экземпляр актива-
ционной записи от ссылки на переменную (локальное смещение описано в разделе 9.3.2).
В качестве примера рассмотрим следующую скелетную программу:
program A;
procedure В ;
procedure С;
end; { С }
end; { В }
end; [ А }
I
406 Глава 9. Реализация подпрограмм
Статические глубины процедур А, В и С равны 0, 1 и 2, соответственно. Если бы проце-
дура С ссылалась на переменную, объявленную в процедуре А, то смещение по цепочке у
этой ссылки равнялось бы 2 (статическая глубина процедуры С минус статическая глу-
бина процедуры А). Если бы процедура С ссылалась на переменную, объявленную в про-
цедуре В, то смещение по цепочке у этой ссылки равнялось бы 1. Обращения к локаль-
ным переменным обрабатываются с помощью того же самого механизма, при этом сме-
щение по цепочке равно 0.
Для того чтобы проиллюстрировать полный процесс нелокального доступа, рассмот-
рим следующую скелетную программу на языке Pascal:
program MAIN_2;
var X : integer;
procedure BIGSUB;
var А, В, С : integer;
procedure SUB1;
var A, D: integer;
begin { SUB1 }
A := В + С; < 1
end; { SUB1 }
procedure SUB2(X : integer);
var В, Е : integer;
procedure SUB3;
var С, Е : integer;
begin { SUB3 }
S0B1;
E := В + A; < 2
end; { SUB3 }
begin { SUB2 }
SUB3;
A := D + E; < 3
end; { SUB2 }
begin {BIGSUB}
SUB2(7);
end; { BIGSUB}
begin { MAIN_2 }
BIGSUB;
end; { MAIN_2 }
Последовательность вызовов процедур такова:
MAIN_2 вызывает BIGSUB.
BIGSUB вызывает SUB2.
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 407
SUB2 вызывает SUB3.
SUB3 вызывает SUB1.
Состояние стека во время выполнения программы при достижении точки 1 показано на
рис. 9.9.
ЭЗА
SUB1
ЭЗА
SUB3
ЭЗА
SUB2
ЭЗА
BIGSUB
ЭЗА
MAIN 2
|
вершина |
||||
|
< < - |
Локальная переменная |
* стека |
||
|
Локальная переменная |
D |
|||
|
Динамическая связь |
•- |
-А |
||
|
Статическая связь |
•- |
|||
|
Возврат (в SUB3 |
||||
|
Локальная переменная |
||||
|
Локальная переменная |
Е |
|||
|
Динамическая связь |
С |
|||
|
Статическая связь' |
• |
|||
|
ч 1 |
||||
|
Возврат (в SUB2 |
||||
|
Локальная переменная |
||||
|
Локальная переменная |
Е i i |
|||
|
Параметр |
7 |
В ' | |
||
|
Динамическая связь |
X |
|||
|
Статическая связь |
• ■ |
■ |
— 1 1 |
|
|
Возврат(в 1 |
3) |
— ' у 1 |
||
|
Локальная переменная |
•4 «-. С | | |
|||
|
Локальная переменная |
В ' 1 |
|||
|
Локальная переменная |
А ! | |
|||
|
Динамическая связь |
•- |
> |
||
|
Статическая связь |
•- |
\ ' 1 |
||
|
Возврат (в MAIN_; |
) |
1 ' 1 |
||
|
{ |
Локальная переменная |
X |
1 1 |
ЭЗА — экземпляр записи активации
Рис. 9.9. Содержимое стека при дос-
тижении точки I в программе MA1NJ2
В точке 1 внутри процедуры SUB1 происходит обращение к локальной переменной А, а
не к нелокальной переменной А из процедуры BIGSUB. Пара (смещение по цепочке, ло-
кальное смещение), соответствующая этой ссылке на переменную А, равна (0, 3). Ссылка
на переменную В относится к нелокальной переменной В из процедуры BIGSUB. Эту ссыл-
ку можно представить в виде пары (1,4), Локальное смещение равно 4, поскольку смеще-
408 Глава 9. Реализация подпрограмм
ние, равное 3, соответствует первой локальной переменной (процедура BIGSUB не имеет
параметров). Отметим, что если бы для простого поиска экземпляра записи активации, со-
ответствующего объявлению переменной В, использовалась динамическая связь, то мы
нашли бы переменную В, объявленную в процедуре SUB2, что было бы ошибкой. Если бы
пара (1,4) использовалась для поиска по динамической цепочке, то была бы найдена пере-
менная Е из процедуры SUB3. Статическая связь, однако, указывает на запись активации
процедуры BIGSUB, соответствующую правильному экземпляру переменной В. Перемен-
ная В в процедуре SUB2 не принадлежит среде ссылок в этой точке и (вполне законно) не
доступна. Обращение к переменной С в точке 1 относится к переменной С, определенной в
процедуре BIGSUB, которой соответствует пара (1, 5).
После того как процедура SUB1 завершит свою работу, экземпляр ее активационной
записи будет удален из стека, а управление будет возвращено в процедуру SUB3. Обра-
щение к переменной Е в точке 2 относится к переменной, объявленной в процедуре
SUB2, поскольку эта процедура является ближайшим статическим предком, содержащим
объявление этой переменной. Ей соответствует пара (1,4). Локальное смещение равно 4,
потому что переменная В является первой переменной, объявленной в процедуре SUB1,
а процедура SUB2 имеет один параметр. Обращение к переменной А относится к пере-
менной А, объявленной в процедуре BIGSUB, поскольку ни процедура SUB3, ни ее ста-
тический предок SUB2 не имеют объявлений переменной с именем А. Этой ссылке соот-
ветствует пара (2, 3).
" После того как процедура SUB3 закончит свою работу, экземпляр ее активационной
записи будет удален из стека, и в нем останутся только экземпляры записей активации
программы MAIN_2, а также процедур BIGSUB и SUB2. В точке 3 внутри процедуры
SUB2 обращение к переменной А относится к переменной А из процедуры BIGSUB,
единственной из активных подпрограмм, имеющей объявление этой переменной. Этот
доступ осуществляется с помощью пары (1,3). В этой точке переменная D является не-
видимой, таким образом, обращение к ней было бы семантической ошибкой. Эта ошибка
может быть обнаружена, когда компилятор попробует вычислить пару (смещение по це-
почке, локальное смещение). Обращение к переменной Е относится к локальной пере-
менной Е из процедуры SUB2, которая является доступной с помощью пары (0, 5).
Итак, обращения к переменной А в точках 1, 2 и 3 можно представить следующими
парами целых чисел:
(О, 3) (локальная)
(2, 3) (на два уровня ниже)
(1,3) (на один уровень ниже)
В этом месте вполне резонно спросить, как поддерживается статическая цепочка во
время выполнения программы. Если такая поддержка является слишком сложной, то
факт, что такой доступ прост и эффективен, становится неважным. В этом разделе мы не
рассматриваем параметры, передаваемые по имени, и параметры, являющиеся именами
подпрограмм.
Статическая цепочка должна модифицироваться при каждом вызове подпрограммы и
возвращении из нее. Часть, связанная с возвращением из подпрограммы, является триви-
альной: когда подпрограмма завершает свою работу, ее активационная запись удаляется
из стека. После этого на вершине стека окажется экземпляр записи активации модуля,
вызвавшего только что завершившуюся подпрограмму. Поскольку статическая цепочка,
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 409
начинающаяся этим экземпляром активационной записи, никогда не изменялась, она ра-
ботает правильно, так же, как она работала до вызова другой подпрограммы. Следова-
тельно, никакие другие действия не нужны.
Действия, которые необходимо выполнить при вызове подпрограммы, намного
сложнее. Несмотря на то что соответствующая область видимости предка легко опреде-
ляется во время компиляции, во время вызова должны быть найдены самые последние
по времени создания экземпляры активационных записей, находящиеся в области види-
мости предка. Для этого проводится поиск экземпляра активационной записи по дина-
мической цепочке, пока не будет найден первый экземпляр в области видимости предка.
Однако этого можно избежать, если обрабатывать объявления процедур и ссылки на них
точно так же, как и для переменных. Когда компилятор встречает вызов процедуры, по-
мимо всего прочего, он определяет, в какой именно процедуре была объявлена данная
процедура. Такая процедура должна быть статическим предком вызываемой процедуры.
Затем компилятор вычисляет глубину вложения, или количество вложенных областей
видимости между вызывающим модулем и процедурой, в которой объявлена вызываемая
процедура. Эта информация записывается в память и становится доступной для вызова
данной процедуры при выполнении программы. В момент вызова определяется статиче-
ская связь, содержащаяся в экземпляре активационной записи вызываемой процедуры.
Для этого следует переместиться вниз по статической цепочке вызывающего модуля на
количество звеньев, равное глубине вложения, вычисляемой во время компиляции.
Снова рассмотрим программу MAIN_2 и состояние стека, показанное на рис. 9.9. Обра-
батывая вызов процедуры SUB1 из процедуры SUB3, компилятор определяет, что глубина
вложения процедуры SUB3 (вызывающего модуля) на два уровня меньше, чем глубина
вложения процедуры, в которой объявлена вызываемая процедура SUB1, т.е. BIGSUB. При
вызове процедуры SUB1 из процедуры SUB3 эта информация используется для установле-
ния статической связи в экземпляре активационной записи процедуры SUB1. Этой статиче-
ской связи присваивается указатель на экземпляр активационной записи, на которую ука-
зывает вторая статическая связь в статической цепочке, считая от экземпляра активацион-
ной записи вызывающего модуля. В этом случае вызывающим модулем является
процедура SUB3, статическая связь которой указывает на экземпляр активационной записи
ее предка (т.е. SUB2). Статическая связь экземпляра активационной записи процедуры
SUB2 указывает на экземпляр записи активации процедуры BIGSUB. Таким образом, ста-
тической связи нового экземпляра активационной записи процедуры SUB1 присваивается
указатель на экземпляр активационной записи процедуры BIGSUB.
Этот метод работает при связывании любых процедур, кроме случая, когда в качестве
параметров в процедуру передаются имена подпрограмм. Эта ситуация рассматривается
в разделе 9.6.
Один недостаток использования статической цепочки для доступа к нелокальным пе-
ременным заключается в том, что ссылки на переменные, находящиеся вне области ви-
димости статического предка, выполняются неэффективно. При этом статическая цепоч-
ка прослеживается звено за звеном, по одному звену на каждую вложенную область ви-
димости, начиная со ссылки на переменную и заканчивая ее объявлением. Другой
недостаток состоит в том, что программисту, разрабатывающему программу, продолжи-
тельность выполнения которой очень важна, трудно оценить затраты времени на обра-
ботку нелокальных ссылок, поскольку эти затраты зависят от глубины вложения между
ссылкой и областью видимости объявления переменной. Еще более усложняет эту про-
410 Глава 9. Реализация подпрограмм
блему тот факт, что при последующих модификациях кода глубины вложений могут из-
мениться, приведя таким образом к изменению времени обработки некоторых ссылок
как в этом, так и, возможно, в других сегментах кода.
9.3.4.2. Индикаторы
Единственной широко распространенной альтернативой статической цепочке являет-
ся индикатор. При этом подходе статические связи объединяются в одном массиве, на-
зываемом индикатором, вместо того, чтобы храниться в своих активационных записях.
Содержание индикатора в любой конкретный момент времени представляет собой спи-
сок адресов доступных экземпляров активационных записей в стеке — по одному на ка-
ждую активную область видимости — в том порядке, в котором они вложены друг в друга.
Каждый доступ к нелокальным переменным с помощью индикатора состоит из двух
этапов, независимо от количества вложенных областей видимости, разделяющих ссылку
и объявление переменной, к которой требуется получить доступ. Во-первых, с помощью
статически вычисляемого значения, называемого смещением индикатора (display
offset) и тесно связанного со смещением в цепочке, обнаруживается связь с нужной акти-
вационной записью, которая хранится в индикаторе. Во-вторых, локальное смещение
внутри экземпляра активационной записи вычисляется и используется точно так же, как
и при применении статической цепочки. Нелокальная ссылка представляется упорядо-
ченной парой целых чисел (смещение индикатора, локальное смещение). Нелокальную
переменную можно удобно и быстро адресовать, дважды выполнив косвенную адреса-
цию, основанную на смещениях.
При каждом вызове подпрограммы и возврате из нее необходимо изменять содержи-
мое индикатора, чтобы отражать новое состояние областей видимости. Теперь мы иссле-
дуем действия, которые следует выполнять для поддержания работы индикатора. Пред-
положим, что параметры не могут быть именами подпрограмм и передаваться по имени.
Эти более сложные случаи рассматриваются в разделе 9.6.
Смещение индикатора зависит только от статической глубины процедуры, в которой
появляется обращение к нелокальной переменной. Если статическая глубина процедуры
Р равна 2, то связь с экземпляром записи активации процедуры Р всегда будет появлять-
ся в индикаторе во второй позиции. Индексы индикатора отсчитываются от нуля, причем
нулевая позиция используется для доступа к переменным, объявленным во внешней об-
ласти видимости (главном модуле).
Указатель на позицию к в индикаторе адресует экземпляр активационной записи про-
цедуры, имеющей статическую глубину, равную к. При вызове процедуры Р, имеющей
статическую глубину, равную к, индикатор следует модифицировать, выполнив следую-
щие действия.
При завершении работы подпрограммы указатель, сохраненный в экземпляре записи
активации завершенной подпрограммы, следует вернуть в индикатор. Затем экземпляр
записи активации подпрограммы удаляется из стека точно так же, как это происходило
при работе со статической цепочкой.
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 411
Для того чтобы убедиться, что описанные выше действия всегда выполняются кор-
ректно, рассмотрим три возможные ситуации, возникающие при вызове процедуры Р из
процедуры Q. Обозначим через Psd статическую глубину процедуры Р, а через Qsd —
статическую глубину процедуры Q. Рассмотрим три случая.
Воспользуемся следующей программой, представляющей собой скелетную версию
программы из предыдущего примера программы MAIN_2.
program MAIN_3;
procedure BIGSUB;
procedure SUBl;
end { SUBl }
procedure SUB2;
procedure SUB3;
end { SUB3 }
end { SUB2 }
end { BIGSUB }
end. { MAIN_3 }
Первый случай может возникнуть, если процедура SUB2 вызывается процедурой
SUB1, поскольку они обе имеют статическую глубину, равную 2. Состояние стека и ин-
дикатор непосредственно перед вызовом и сразу после него показаны на рис. 9.10.
Стек
Индикатор
Стек
Индикатор
a) main_3 вызывает bigsub; bigsub вызывает SUB2 б) SUB2 вызывает SUBl
ЭЗА — экземпляр записи активации
Рис. 9.10. Изменение индикаторов, соответствующих вызывающей и вы-
зываемой подпрограммам одинаковой статической глубины
412
Глава 9. Реализация подпрограмм
Для вызова, как всегда, необходимо, чтобы новый экземпляр активационной записи
был помещен в стек. Новая среда ссылок содержит только подпрограммы SUB1,
BIGSUB и MAIN_3. Поскольку значения статической глубины подпрограмм SUB1 и
SUB2 равны между собой, их индикаторные связи должны занимать в индикаторе одина-
ковые места. Это означает, что их смещения в индикаторе должны быть равными. По-
скольку индикаторные связи всегда хранятся в новом экземпляре активационной записи,
никаких проблем не возникает. Следовательно, элемент индикатора, соответствующий
подпрограмме SUB2, должен быть удален, и на его место должен быть записан новый
элемент индикатора, соответствующий подпрограмме SUB1. В данном случае он являет-
ся вторым элементом индикатора в соответствии со статической глубиной подпрограм-
мы SUB1. После того как подпрограмма SUB1 завершит свою работу и вернет управле-
ние подпрограмме SUB2, элемент индикатора, соответствующий подпрограмме SUB2,
должен быть восстановлен на прежнем месте. Непосредственно перед удалением экзем-
пляра активационной записи процедуры SUB1 из стека сохраненный экземпляр индика-
тора перемещается из экземпляра обратно в индикатор.
Второй случай может возникнуть, если подпрограмма SUB2 вызывает подпрограмму
SUB3. Статическая глубина подпрограммы SUB2 равна 2, а подпрограммы SUB3 — 3.
Состояние стека и дисплея непосредственно перед вызовом и сразу после него показаны
на рис. 9.П.
V
|
ЭЗА SUB2 |
|
|
ЭЗА BIGSUB |
|
|
ЭЗА MAIN_3 |
-4 |
ЭЗА
SUB3
ЭЗА
SUB2
ЭЗА
BIGSUB
ЭЗА
MAIN_3
Стек Индикатор Стек Индикатор
a)MAiN_3 вызываетbigsub; BigsubвызываетSUB2 6)sub2 вызываетзивз
ЭЗА — экземпляр записи активации
Рис. 9.11. Изменение индикатора в ситуации, когда статическая глубина вы-
зывающей подпрограммы меньше статической глубины вызываемой подпро-
граммы (Qsd < Psd)
В данном случае в стеке, как обычно, создается новая запись активации, однако среда
ссылок просто увеличивается на одну новую область видимости, соответствующую вы-
зываемой подпрограмме. Таким образом, в индикатор можно просто добавить новый
указатель. В этом конкретном примере нет необходимости сохранять в экземпляре акти-
вационной записи существующий указатель, записанный в индикаторе на месте, предна-
значенном для нового указателя. Однако в общем случае это неверно. В других ситуаци-
ях это делать необходимо. Намного проще каждый раз сохранять существующий указа-
тель, чем определять при каждом вызове подпрограммы, следует ли это делать. В качес-
9.3. Реализация подпрограмм на языках, подобных языку ALGOL 413
тве примера ситуации, в которой указатель необходимо сохранять, рассмотрим следую-
щую подпрограмму SUB4:
program MAIN 4;
procedure BIGSUB;
procedure SUB1;
procedure SUB4;
end; { SUB4 .}
end; { SUB1 }
procedure SUB2;
procedure SUB3;
end; { SUB3 }
end; { SUB2 }
. . .
end; { BIGSUB }
end. { MAIN_4 }
Предположим, что в ходе выполнения программы ее подпрограммы вызываются сле-
дующим образом:
MAIN_4 вызывает BIGSUB
BIGSUB вызывает SUB2
SUB2 вызывает SUB3
SUB3 вызывает SUB4
Состояние стека и индикатора, полученное в результате этих вызовов, показано на рис. 9.12.
Допустим теперь, что подпрограмма SUB1 вызывает подпрограмму SUB4. Это при-
мер ситуации, при которой статическая глубина вызывающей подпрограммы меньше,
чем вызываемой. В этом случае указатель, соответствующий подпрограмме SUB3, зани-
мает в индикаторе место, на котором должен был бы находиться указатель, соответст-
вующий подпрограмме SUB4. Обе эти подпрограммы имеют статическую глубину, рав-
ную 3. Следовательно, существующий в индикаторе указатель следует сохранить перед
тем, как на его место будет помещен новый указатель. Правильное состояние стека и ин-
дикатора при выполнении подпрограммы SUB4 показано на рис. 9.13.
Третий случай (Qsd > Psd) возникает, когда подпрограмма SUB3 вызывает подпро-
грамму SUB1. Статическая глубина процедуры SUB3 равна 3, а процедуры SUB1 — 2.
Состояния стека и индикатора непосредственно перед вызовом и сразу после него пока-
заны на рис. 9.14.
В данном случае оказывается, что два элемента индикатора, соответствующие подпро-
граммам SUB2 и SUB3, должны быть временно удалены, поскольку они не принадлежат
среде ссылок подпрограммы SUB1. Однако в действительности должен быть удален
только один из этих указателей, соответствующий подпрограмме SUB2. Указатель, соот-
ветствующий подпрограмме SUB3, может оставаться в индикаторе. Ссылки на переменные
в подпрограмме SUB1 не будут использовать индикаторный указатель, соответствующий
подпрограмме SUB3, поскольку переменные подпрограммы SUB3 не видны в подпрограм-
ме SUB1. Таким образом, можно совершенно спокойно оставить этот указатель в индика-
торе. Компилятор не будет генерировать код, имеющий доступ к элементам индикатора,
находящимся выше элементов, соответствующих текущей активной подпрограмме.
414 Глава 9. Реализация подпрограмм
Стек
Индикатор
Стек
Индикатор
ЭЗА — экземпляр записи активации
Рис. 9.12. Состояние стека и ин-
дикатора перед тем, как подпро-
грамма SUB1 вызовет подпро-
грамму SUB4 в программе
MAIN_4; пунктирные линии ука-
зывают на неактивные указатели
ЭЗА — экземпляр записи активации
Рис. 9.13. Состояние стека и ин-
дикатора после того, как подпро-
грамма SUB1 вызовет подпро-
грамму SUB4 в программе
MAIN__4 (Qsd< Psd)
Стек
Индикатор
Стек
Индикатор
б)зивз вызывает SUBl
a)MAiN_4 вызываетbigsub; bigsub вызываетSUB2;
SUB2 вызывает SUB3
ЭЗА —экземпляр записи активации
Рис. 9.14. Изменение индикатора в ситуации, при которой вызывающая
подпрограмма имеет большую статическую глубину, чем вызываемая под-
программа (Qsd > Psd)
415
9.3. Реализация подпрограмм на языках, подобных языку ALGOL
Индикатор можно хранить в памяти в виде статического массива. Компилятор может
определять максимальный размер индикатора, равный максимальной статической глуби-
не подпрограмм в программе. Хранить индикатор в памяти вполне разумно, поскольку
машина обеспечивает косвенную адресацию через машинные ячейки. В таком случае об-
ращения к нелокальным переменным занимают на один машинный цикл больше, чем
обращения к локальным переменным, которые могут использовать прямую адресацию.
В качестве альтернативы можно поместить индикатор в регистрах, предполагая, что в
машине имеется достаточное количество резервных регистров. В этом случае обращения
не требуют дополнительного машинного цикла.
Сравним использование статических цепочек и индикаторов. В той реализации, кото-
рую мы описали выше, может оказаться, что обращения к локальным переменным при.
использовании индикатора будут выполняться медленнее, чем при использовании стати-
ческих цепочек, если индикатор не хранится в регистрах. Это объясняется тем, что все
обращения к локальным переменным должны выполняться через элементы индикатора, а
при этом возникает дополнительный уровень косвенной адресации. Однако этого можно
избежать, так что доступ к локальным переменным при использовании обоих методов
будет одинаковым.
Обращения к нелокальным переменным, отдаленным только на один статический
уровень, при обоих методах занимают одинаковое время. Однако, если они находятся на
более отдаленных статических уровнях, применение индикаторов позволяет ускорить
этот процесс, поскольку в этом случае нет необходимости отслеживать статическую це-
почку. Время доступа к нелокальной переменной с использованием индикатора одинако-
во для всех нелокальных переменных. Если время выполнения программы очень важно,
используйте индикаторы, а не статические цепочки.
Если вызываемую и вызывающую процедуры разделяет лишь несколько статических
уровней, то вызов подпрограммы с помощью статических цепочек выполняется быстрее.
В противном случае дополнительное время уходит на отслеживание статической цепочки
от вызывающей подпрограммы к экземпляру активационной записи подпрограммы, в ко-
торой объявлена вызываемая подпрограмма. Время возврата из подпрограммы одинаково
для обоих методов, однако при использовании статических цепочек этот процесс всегда
выполняется немного быстрее, поскольку, когда подпрограмма завершает свою работу, не-
обходимо затратить время на восстановление предыдущего состояния индикатора.
Использование индикаторов имеет преимущество, если в программе есть много об-
ращений к отдаленным нелокальным переменным. Статические цепочки лучше исполь-
зовать, когда таких обращений немного, что является более распространенной ситуаци-
ей. Эксперименты показывают, что на практике количество уровней вложения подпро-
грамм не превышает трех.
9.4. Блоки
Напомним, что, как указывалось в главе 4, в нескольких языках программирования, в
частности, в языках Ada, С, C++ и Java, пользователь может сам определять локальные
области видимости переменных, называемые блоками. В качестве примера рассмотрим
следующий фрагмент программы на языке C++:
{ int temp;
temp = list[upper];
416
Глава 9. Реализация подпрограмм
0
list[upper] = list[lower];
list[lower] = temp;
}
Блок в программе на языке C++ определяется как фрагмент кода, начинающийся с
одного или нескольких определений данных и заключенный в фигурные скобки. Время
жизни переменной temp в приведенном выше блоке начинается, когда управление вы-
полнением программы входит в блок, и заканчивается, когда управление покидает блок.
Преимущество использования такой локальной переменной заключается в том, что ее
область видимости никогда не перекроется с областью видимости любой другой пере-
менной, имеющей то же самое имя и объявленной где-либо в другом месте программы.
Блоки можно реализовать с помощью описанного нами процесса выполнения под-
программ на языке Pascal. Блоки рассматриваются как подпрограммы, которые не имеют
параметров и всегда вызываются в одном и том же месте программы. Реализация блоков
этим способом с применением индикаторов имеет один недостаток. Максимальная глу-
бина вложения возрастает, и, следовательно, увеличивается размер индикатора. Если ин-
дикатор хранится в регистрах, его размер должен быть ограничен. Таким образом, при-
менение индикаторов при обработке блоков может привести к тому, что индикаторы
придется размещать в памяти, а не в регистрах, а это значительно замедлит доступ к не-
локальным переменным.
Однако блоки можно реализовать другим, относительно более простым способом.
Можно статически определить максимальный объем памяти, необходимой при выполне-
нии программы для хранения переменных, объявленных в блоке, поскольку вход в блок
и выход из него осуществляется в строгом соответствии с текстом программы. Этот объ-
ем памяти выделяется в экземпляре активационной записи сразу за локальными пере-
менными. Смещение всех переменных, объявленных в блоке, вычисляется статически,
так что эти переменные адресуются точно так же, как и локальные переменные.
В качестве примера рассмотрим следующую скелетную программу:
main_5() {
int x, у, z;
while (...){
int a, b, c;
while (..,){
int d, e;
}
}
while (...){
int f, g;
}
}
Схема распределения статической памяти для этой программы показана на рис. 9.15. За-
метим, что переменные f ид занимают ту же ячейку памяти, что и переменные а и Ь,
поскольку переменные а и b выталкиваются из стека при выходе из блока, где они были
объявлены (до того, как в их ячейках будут расположены переменные f и д).
417
9.4.Блоки
|
е |
|
|
d |
|
|
Переменные„ |
с |
|
Ьид |
|
|
аи f |
|
|
z |
|
|
Локальные - |
У |
|
переменные |
X |
|
Экземпляр записи МАШ_5 |
Рис. 9.15. Хранение переменных, объ-
явленных в блоке, в случае, когда бло-
ки не рассматриваются как процеду-
ры без параметров
9.5. Реализация методов динамического
обзора данных
Существуют, по крайней мере, два вида доступа к нелокальным переменным в языках
с динамическим обзором данных: глубокий доступ и теневой доступ. Отметим, что ни
глубокий, ни теневой доступ не связаны с понятиями глубокого и теневого связывания.
Основное отличие между связыванием и доступом здесь состоит в том, что глубокое и
теневое связывания приводят к разным с точки зрения семантики результатам, а глубо-
кий и теневой доступ — нет.
418
Глава 9. Реализация подпрограмм
9.5.1. Глубокий доступ
Когда программа на некотором языке с динамическим обзором данных обращается к
нелокальной переменной, можно выполнить поиск объявления этой переменной в других
подпрограммах, активных в данный момент, начиная с подпрограммы, вызванной рань-
ше всех. Эта концепция чем-то напоминает доступ к нелокальным переменным в языках
со статическим обзором данных, за исключением того, что отслеживается динамическая,
а не статическая цепочка. Динамическая цепочка связывает в одно целое экземпляры за-
писей активации всех подпрограмм в порядке, обратном порядку их активации. Следова-
тельно, динамическая цепочка — это именно то, что нужно для доступа к нелокальным
переменным в языках с динамическим обзором данных. Этот метод называется глубо-
ким доступом (deep access), потому что он может потребовать глубокого поиска в стеке.
Рассмотрим следующий пример программы:
procedure С;
integer x, z;
begin
х : u + v;
end;
procedure В;
integer w, x;
begin
end;
procedure A;
integer v, w;
begin
end;
procedure MAIN_6;
integer v, u;
begin
end;
Эта программа внешне похожа на программу, написанную на языке ALGOL, однако
здесь не подразумевается никакой конкретный язык программирования. Предположим,
что в ходе выполнения программы возникла следующая последовательность вызовов
подпрограмм:
MAIN_6 вызывает А
А вызывает А
А вызывает В
В вызывает С
На рис. 9.16 показано состояние стека в ходе выполнения процедуры С после этой
последовательности вызовов. Отметим, что в экземпляре активационной записи нет ста-
тических связей, которые в языках с динамическим обзором данных не нужны.
9.5. Реализация методов динамического обзора данных 419
ЭЗА
С
ЭЗА
В
ЭЗА
А
ЭЗА
А
ЭЗА
MAIN_6
|
* - < |
Локальная переменная |
z |
|
|
Локальная переменная |
X |
||
|
Динамическая связь |
|||
|
Возврат (в В) |
|||
|
Локальная переменная |
X |
||
|
Локальная переменная |
w |
||
|
Динамическая связь |
• |
||
|
Возврат (в А) |
|||
|
Локальная церемонная |
W |
||
|
Локальная переменная |
V |
||
|
Динамическая связь |
1 |
||
|
Возврат (в А) |
.] |
||
|
Локальная переменная |
W |
||
|
Локальная переменная |
V |
||
|
Динамическая связь |
|||
|
Возврат (в MA!N_6) |
|||
|
Локальная переменная |
U |
||
|
Локальная переменная |
V |
ЭЗА — экземпляр записи активации
Рис. 9.16. Состояние стека программы
на языке с динамическим обзором данных
Рассмотрим обращения к переменным х, и и v в процедуре С. Сначала обнаружива-
ется ссылка на переменную х в экземпляре записи активации процедуры С. Поиск ссыл-
ки на переменную и производится во всех экземплярах активационных записей в стеке,
поскольку единственная переменная с этим именем существует только в программе
MAIN6. Для этого приходится отслеживать четыре динамические связи и проверять де-
сять имен переменных. Ссылка на переменную v обнаруживается в самом последнем по
времени создания экземпляре активационной записи процедуры А (ближайший экземп-
ляр в динамической цепочке).
Между методом глубокого доступа к нелокальной переменной в языках с динамиче-
ским обзором данных и методом статических цепочек в языках со статическим обзором
данных существуют два важных различия. Во-первых, в языках с динамическим обзором
данных нельзя во время компиляции определить длину цепочки, по которой производит-
ся поиск. Нужно осуществлять поиск во всех экземплярах активационных записей в це-
почке, пока не обнаружится первый экземпляр, содержащий ссылку на искомую пере-
менную. Это — одна из причин, по которым программы на языках с динамическим об-
зором данных выполняются медленнее, чем программы на языках со статическим
обзором данных. Во-вторых, активационные записи должны хранить имена переменных
420 Глава 9. Реализация подпрограмм
для того, чтобы их можно было найти, в то время как в реализациях языков со статиче-
ским обзором данных требуется хранить только их значения. (Имена при статическом
обзоре не нужны, поскольку все переменные представляются в виде пар (смещение в це-
почке, локальное смещение).)
9.5.2. Теневой доступ
Теневой доступ (shallow access) — это метод, альтернативный с точки зрения реали-
зации, но не семантики. Как указывалось выше, глубокий и теневой доступ имеют иден-
тичную семантику. При теневом доступе переменные, объявленные в подпрограммах, не
хранятся в их активационных записях. Поскольку при динамическом обзоре в каждый
момент времени существует, по крайней мере, одна видимая копия переменной с указан-
ным именем, можно использовать совершенно другой подход. Один из вариантов тене-
вого доступа — отдельный стек для каждого имени переменной во всей программе. Ка-
ждый раз новая переменная с конкретным именем создается с помощью объявления в
начале активации подпрограммы, и для этой переменной в соответствующем стеке выде-
ляется ячейка памяти. Каждая ссылка на это имя означает ссылку на переменную, нахо-
дящуюся на вершине стека, связанного с этим именем, поскольку вершина создается по-
следней. По завершении работы подпрограммы время жизни ее локальных переменных
заканчивается, а стеки, соответствующие их именам, выталкиваются. Этот метод способ-
ствует очень быстрому доступу к переменным, однако поддержка стеков при входе в
подпрограммы и выходе из них требует затрат.
На рис. 9.17 показаны стеки, соответствующие переменным из ранее приведенного
примера программы в ситуации, аналогичной показанной на рис. 9.16.
Кроме того, при теневом доступе можно использовать центральную таблицу, в которой
для каждого имени переменной, появляющейся в программе, предусмотрена отдельная
ячейка. Вместе с каждым элементом этой таблицы хранится бит, называемый активным,
который указывает, связано ли данное имя с какой-то переменной в настоящий момент. Та-
ким образом, любой доступ к любой переменной может быть осуществлен с помощью
смещения в центральной таблице. Это смещение является статическим, так что доступ
должен быть быстрым. Реализации языка SNOBOL используют именно этот подход.
|
А |
В |
|||
|
А |
С |
А |
||
|
MAIN_6 |
MAIN_6 |
В |
С |
Л |
u v х г w
(В ячейках отека указаны имена программных модулей,
содержащих объявление переменной)
Рис. 9.17. Один из.методов использова-
ния теневого доступа при реализации
динамического обзора данных
Центральная таблица поддерживается довольно просто. При вызове подпрограммы
требуется, чтобы все ее локальные переменные были логически размещены в централь-
ной таблице. Если позиция новой переменной в центральной таблице уже является ак-
9.5. Реализация методов динамического обзора данных 421
тивной, т.е. если в этой позиции уже содержится некая переменная, время жизни которой
еще не закончилось (что указывается активным битом), то значение старой переменной
на время жизни новой следует сохранить в какой-нибудь ячейке памяти. Одновременно с
началом жизни какой-либо переменной должен быть установлен активный бит в ее пози-
ции в центральной таблице.
Разработано несколько вариантов центральной таблицы и способов, с помощью кото-
рых переменные, временно замещаемые другими переменными, хранятся в памяти. Один
из вариантов — "скрытый" стек, в который записываются все объекты, подлежащие хра-
нению. Поскольку подпрограммы выполняют вызовы и возвращают управление, и, сле-
довательно, времена жизни их локальных переменных вкладываются друг в друга, этот
метод работает хорошо.
Второй вариант, возможно, наиболее ясен и прост для реализации. Используется цен-
тральная таблица с отдельными ячейками, в которых хранятся только текущие имена
всех переменных. Замененные переменные хранятся в записях активации тех подпро-
грамм, в которых они создавались. При этом используются стеки, однако один из них
всегда уже существует, так что дополнительные затраты минимальны.
Выбор между теневым и глубоким доступом к нелокальным переменным зависит от
относительной частоты вызовов подпрограмм и обращений к нелокальным переменным.
Метод глубокого доступа обеспечивает быструю связь между подпрограммами, однако
при его использовании обращения к нелокальным переменным, особенно к отдаленным
(в смысле статической цепочки), требуют дополнительного времени. Метод теневого
доступа ускоряет обращение к нелокальным переменным, особенно к отдаленным, одна-
ко требует дополнительного времени на связь между подпрограммами.
9.6. Реализация параметров, являющихся именами
подпрограмм
Параметры, представляющие собой имена подпрограмм, детально обсуждались в гла-
ве 8. Напомним, что языки со статическим обзором данных для связывания среды ссы-
лок с активацией подпрограммы, которая передается как параметр, используют метод,
называемый глубоким связыванием. Теперь мы исследуем, как именно можно реализо-
вать глубокое связывание с помощью статической цепочки и индикаторов.
9.6.1. Статические цепочки
Предположим, что при реализации языка используется метод статических цепочек.
Подпрограмма, которая передает имя некоей подпрограммы как параметр, должна иметь
в качестве своего статического предка модуль, в котором была объявлена передаваемая
подпрограмма. Если это не так, то имя передаваемой подпрограммы будет невидимым, и
компилятор обнаружит синтаксическую ошибку. Таким образом, при синтаксически
правильных вызовах компилятор может просто передать связь статическому предку пе-
редаваемой подпрограммы вместе с ее именем. Затем при инициализации экземпляра ак-
тивационной записи передаваемой подпрограммы эта связь заносится в его поле стати-
ческих связей вместо связи, вычисляемой обычным путем. Завершение работы переда-
ваемой подпрограммы не требует никаких особых действий.
422
Глава 9. Реализация подпрограмм
9.6.2. Индикаторы
Предположим, что при реализации языка используются индикаторы. Подчеркнем еще
раз, что поддержка индикаторов, описанная в разделе 9.3.4.2, корректна, только если
имена подпрограмм не передавались как параметры и не применялась передача парамет-
ров по имени. Использование индикаторов для вызовов подпрограмм в других ситуациях
сводилось к замене отдельного индикаторного указателя. Когда при вызове подпрограм-
мы ей в качестве параметра передается имя некоей подпрограммы, в индикатор должны
быть помещены указатели на все статические предки этой подпрограммы. При этом в
памяти должно сохраняться большое количество старых индикаторных указателей. По-
скольку статическая среда активации подпрограммы, передаваемой как параметр, может
иметь мало общего со статической средой вызываемой подпрограммы, во многих случа-
ях в индикаторе приходится заменять несколько указателей. В некоторых реализациях
при каждом вызове подпрограммы, передаваемой как параметр, в памяти сохраняется
весь существующий индикатор, причем часто он записывается в экземпляр активацион-
ной записи выполняемой подпрограммы. Когда подпрограмма, передаваемая как пара-
метр, завершает свою работу, полностью сохраненный индикатор заменяет собой инди-
катор, использованный для ее выполнения.
9.6.3. Ошибочное повторное обращение к среде ссылок
Перейдем к обсуждению проблемы, описанной в главе 6: какая среда ссылок является
правильной при выполнении подпрограммы, передаваемой как параметр. Рассмотрим
следующую скелетную программу, представляющую собой вариант программы, описан-
ной в работе Ghezzi and Jazayeri (1987):
program MAIN_7;
procedure SUB1;
begin { SUB1 }
end; { SUB1 }
procedure SUB2(procedure SUBX);
var SUM : real;
procedure SUB3;
begin { SUB3 }
SUM := 0.0;
end; { SUB3 }
begin { SUB2 }
SUBX;
SUB2 (SUB3);
end; { SUB2 }
begin { MAIN_7 }
SUB2(SUB1);
end. { MAIN 7 }
9.6. Реализация параметров, являющихся именами подпрограмм 423
Подпрограмма MAIN_7 вызывает процедуру SUB2, передавая процедуру SUB1 как па-
раметр. Затем процедура SUB2 вызывает переданную процедуру SUB1. После возвраще-
ния из процедуры SUB1 процедура SUB2 вызывает сама себя, передавая свою собствен-
ную процедуру SUB3 как параметр. Теперь в стеке существует два экземпляра записи ак-
тивации процедуры SUB2, причем верхний экземпляр используется для рекурсивного
вызова. Затем верхняя активация процедуры SUB2 вызывает процедуру SUB3. В тот мо-
мент, когда процедура SUB3 обращается к переменной SUM, существуют две версии этой
переменной, по одной на каждую активацию процедуры SUB2, в которой она объявлена.
Поскольку среда ссылок процедуры SUB3 совпадает со средой ссылок вызывающей
процедуры SUB2, которая передает процедуру SUB3 как параметр, она относится к пер-
вой активации процедуры SUB2, а не к последней по времени. В действительности, это
совсем не очевидно для случайного читателя программы.
Ясно, что этот пример является надуманным. Однако аналогичные ситуации могут
возникнуть и в более реалистичных программах. Проблема заключается в том, что, хотя
интуитивно ясно, что среда ссылок должна относиться к самой последней по времени ак-
тивации, это не всегда так.
На рис. 9.18 показано состояние стека во время выполнения процедуры SUB3 из пре-
дыдущего примера программы.
А
ЭЗА
SUB3
ЭЗА
SUB2
(вызванной из
SUB2)
ЭЗА
•SUB2
(вызванной из <
MAIN_7)
ЭЗА
MAIN
|
Динамическая связь |
•- |
||
|
— |
|||
|
Статическая связь |
*■ |
--, |
|
|
Возврат(в |
|||
|
Локальная переменная |
SOT |
! |
|
|
Параметр |
SUB3 |
SUBX [ |
|
|
Динамическая связь |
•- |
N |
|
|
Статическая связь |
•- |
||
|
Возврат (в SUB2) |
|||
|
Локальная переменная |
SOT |
1 1 |
|
|
Параметр |
SUB1 |
SUBX ] i |
|
|
Динамическая связь |
|||
|
Статическая связь |
• |
||
|
Возврат (в main_7) |
|||
|
-* - |
--<-' |
ЭЗА - экземпляр записи активации
Рис. 9.18. Состояние стека для примера програм-
мы MAIN_ 7 с параметром, являющимся подпро-
граммой (процедура SUB1 была вызвана, но уже
завершила свою работу)
424 Глава 9. Реализация подпрограмм
Семантика связей между подпрограммами при своей реализации требует выполне-
ния многих действий. В языке FORTRAN 77 эти действия относительно просты по сле-
дующим причинам: отсутствуют нелокальные ссылки, кроме ссылок через блоки
COMMON; локальные переменные обычно являются статическими, а рекурсия не поддер-
живается. В языках, подобных языку ALGOL, связь между подпрограммами намного
сложнее. Это является следствием требований поддержки доступа к нелокальным пере-
менным с помощью статического обзора, наличия автоматических локальных перемен-
ных и рекурсии.
Подпрограммы в языках, подобных языку ALGOL, состоят из двух частей: собст-
венно кода, являющегося статическим, и активационной записи, являющейся динамиче-
ской и хранящейся в стеке. Экземпляры активационных записей, кроме всего прочего,
содержат формальные параметры и локальные переменные.
Статические цепочки и индикаторы представляют собой два основных метода реа-
лизации доступа к нелокальным переменным в языках со статическим обзором данных.
В обоих методах пути доступа к переменным во всех статических предках можно уста-
новить статически.
Доступ к нелокальным переменным в языках с динамическим обзором данных мож-
но реализовать с помощью динамических цепочек или метода центральной таблицы пе-
ременных. Динамические цепочки обеспечивают медленный доступ к нелокальным пе-
ременным, но позволяют быстро выполнять вызовы подпрограмм и возвраты из них.
Метод центральной таблицы обеспечивает быстрый доступ к нелокальным переменным,
но при этом вызовы подпрограмм и возврат из них происходят медленнее.
Реализация методов статического и динамического обзора описана в книгах Pratt (1984)
и Ghezzi and Jazayeri (1987), однако более детально она рассмотрена в книгах, посвя-
щенных разработке компиляторов, например, Fischer and LeBlanc (1988).
Подпрограммы, передаваемые как параметры, приносят определенную пользу, од-
нако иногда в них трудно разобраться. Их запутанность объясняется неопределенностью
среды ссылок, доступной во время выполнения таких подпрограмм. Подпрограммы, пе-
редаваемые как параметры, можно реалиювывать с помощью как статических цепочек,
так и индикаторов.
Вопросы 425
426
Глава 9. Реализация подпрограмм
3. Покажите состояние стека со всеми экземплярами активационных записей, вклю-
чая статические и динамические связи, когда выполнение следующей скелетной
программы достигает точки 1 (при условии, что уровень подпрограммы BIGSUB
равен 1).
procedure BIGSUB;
procedure А;
procedure В;
begin { В }
. . . < 1
end; { В }
procedure С ;
begin { С }
В;
end; { С }
begin { А } i
С,"
end; { A }
begin { BIGSUB }
• • j
А;
end; { BIGSIB }
procedure BIGSUB;
procedure С; forward;
procedure A(flag: boolean);
procedure B;
A(false)
end; { В }
begin { A }
if flag
then В
else С
end; { A }
procedure C;
procedure D;
Упражнения 427
... < 1
end; { D }
D
end; { С }
A (true);
end; { BIGSUB} ■
Последовательность вызовов, которые следует выполнить в этой подпрограмме,
для того чтобы достичь оператора D, такова:
BIGSUB вызывает А
А вызывает В
В вызывает А
А вызывает С
С вызывает В
428 Глава 9. Реализация подпрограмм