Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

8.4. ВЫЗОВ ПРОЦЕДУРЫ

395

KPROG, KQ, KQ2,

которая опять совпадает со статической цепочкой тела процедуры

. Вызов

в строке 18 правомерен, он приводит к динамической цепочке

KPROG, KQ, KQ2, KQ1,

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

KPROG, KQ, KQ1

(локальные данные из

KQ2

не доступны!). В

вызывается процедура

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

цепочка подпрограмм примет вид

KPROG, KQ, KQ2, KQ1, KP.

Статическая цепочка, регламентирующая доступ к данным в теле процедуры

, строка 4, есть

KPROG,

Статическая и динамическая цепочки при исполнении строки 25, не содер-

жащей вызова подпрограмм, состоят из контекста основной программы.

Когда исполняется вызов процедуры

в строке 26, статическая и дина-

мическая цепочки принимают вид

KPROG, KP.

При возврате из процедуры из них удаляется имя

, а при выходе из всей

программы обе цепочки ликвидируются.

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

к данным оказываются фрагментами динамических цепочек. Очевидно, что

это свойство выполняется для любых вызовов процедур.

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

вычислений

Algol 60

; в

Pascal

, как и во многих других развитых языках про-

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

зову имеет косвенное отношение), она воспроизведена без изменений.

Как уже отмечалось, потребность в статических цепочках возникает, ко-

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

имен, которые приведены выше на примере

Pascal

. Реализация такой воз-

можности требует, чтобы в процессе выполнения программы в памяти со-

хранялись обе цепочки: одна для адресации данных, связанной с динамиче-

ской вложенностью, а другая — со статической вложенностью. Это обстоя-

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

а потому зачастую они жертвуют возможностью статической локализации

имен (обычно путем запрета вложенных описаний процедур, реже — изме-

нением правил локализации) в пользу повышения эффективности рабочих

программ. Характерным примером такого рода является язык

С/С++

396

ГЛАВА 8. ПОДПРОГРАММЫ

8.4.3. Понятие экземпляра процедуры

При обсуждении процедур важно иметь ввиду следующие моменты. Во-

первых, каждое обращение к алгоритму процедуры — это запуск вычисле-

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

процесс.В частности,рекурсивное обращение к алгоритму порождает новый

экземпляр работающего в данный момент или приостановленного процес-

са. Как следствие, порождается новый комплект локальных данных процес-

са еще до окончания текущего процесса. Во-вторых, завершение вычислений

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

в которой вычисления были приостановлены для обращения к процедуре —

это свойство обращения к любому вспомогательному алгоритму.

Таким образом, имеет смысл говорить об экземплярах процедур и функ-

ций,существующих одновременно

.Эти экземпляры обладают следующими

свойствами.

a) экземпляр характеризуется своим комплектом локальных данных и точ-

кой возврата;

b) порождение экземпляра — это создание его комплекта локальных дан-

ных, запоминание точки возврата и передача управления на начало про-

граммы алгоритма;

c) завершение экземпляра — это уничтожение его комплекта локальных дан-

ных и передача управления в точку возврата, а для функций, вдобавок, пе-

редача результата вычислений в вызвавшее выражение для продолжения

его вычисления;

d) из всех экземпляров рекурсивной процедуры или функции выделяется ак-

тивный экземпляр, который непосредственно выполняется в данный мо-

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

они ожидают продолжения своего выполнения после завершения актив-

ного экземпляра;

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

ности соответствует тому, что здесь названо экземпляром. Термин восходит к операцион-

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

активизации операторов ее тела, но при этом не прекращаются, а лишь приостанавливают-

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

вычислительных процессов.

8.4. ВЫЗОВ ПРОЦЕДУРЫ

397

e) порождение и завершение экземпляров строго соответствует стековой дис-

циплине: “первым порожден — последним завершен”.

Возможности, соответствующие механизму рекурсивного вызова, у нашего

абстрактного вычислителя имеются: это запоминание всего локального кон-

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

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

Возможность одновременного существования нескольких экземпляров од-

ной и той же процедуры или функции в динамике выполнения программы,

при условии выполнения только что перечисленных требований, можно рас-

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

ции.

При определении абстрактных вычислений было бы неправильно тракто-

вать вызов процедуры как преобразование дерева абстрактного синтаксиса:

замена конструкции вызова процедуры деревом, представляющим ее тело.

Причина не в том, что при этом необходимо оперировать потенциально бес-

конечными графами (например, при раскрытии рекурсивных вызовов): это

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

сия всегда конечна. Серьезным доводом против трактовки вызова как заме-

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

следствие, невозможность оперирования с экземплярами. А оперирование с

экземплярами процедур, в том числе и не ограничивающее себя рамками сте-

ка, — исключительно важный момент

Однако,как всегда,нецелесообразность некоторого решения в общем слу-

чае не означает его нецелесообразности в частных. Например, в языке

C/C++

имеются встраиваемые процедуры (

inline

-процедуры), семантика вызова ко-

торых — именно прямая текстовая подстановка

тела процедуры вместо

конструкции вызова.

Осознав, что абстрактный вычислитель должен порождать именно экзем-

пляры процедур,необходимо далее ответить на вопрос,как запоминать экзем-

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

Надо заметить, что в языке

Algol 60

было принято именно подстановочное определение

семантики вызова. Неудобства, связанные с таким определением, выявились в работах по

реализации

Algol 60

, и стимулировали осознание концепции контекста.

Как всегда, такое определение некорректно, и некорректность явно оговорена в семан-

тике, в частности, языка

C++

: правила локализации имен для встраиваемой и обычной про-

цедур одни и те же, и в этом главное отличие встраиваемых процедур от препроцессорных

определений.

398

ГЛАВА 8. ПОДПРОГРАММЫ

завершается текущий активный экземпляр? Для этого есть две возможности.

• Присоединить локальный контекст порождаемого экземпляра к локаль-

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

ально создается для отработки конструкции вызова процедуры. Это чи-

сто теоретический путь реализации,который,тем не менее,может быть

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

вызов обрабатывается на своем процессоре.

• Организация специальной памяти для хранения локальных контекстов

процедур, к которой имеет доступ абстрактный вычислитель. Это —

прагматический вариант реализации. Если не фиксировать дисципли-

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

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

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

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

обрабатывающий вызов процедуры, переходит к интерпретации дерева те-

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

завершении экземпляра стек восстанавливается, а управление возвращается

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

динамической, и статической цепочки процедур.

В практике программирования понятие экземпляра подпрограммы не огра-

ничивается применением лишь в области рекурсивных алгоритмов. В част-

ности,одновременное существование нескольких экземпляров подпрограмм,

не подчиняющееся стековой дисциплине, является мощным средством про-

граммного моделирования. Здесь нет принципиальной разницы, выполняют-

ся ли эти подпрограммы последовательно,приостанавливаясь или продолжа-

ясь по какой-либо из внешних причин, или параллельно, когда на причины

приостановки, продолжения и завершения накладываются правила одновре-

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

держивается определенная дисциплина активизации и взаимодействия про-

цессов,и стековая дисциплина —это существенный,но лишь один из многих

пример реально используемых дисциплин.

Выше (см. § 7.3.4) при обсуждении циклической обработки было опре-

делено понятие сопрограммного механизма взаимодействия процессов, при

котором несколько программных объектов поочередно передают друг другу

управление и поставляют данные для обработки. Эта важная с практической

8.4. ВЫЗОВ ПРОЦЕДУРЫ

399

точки зрения дисциплина может рассматриваться как вариант, альтернатив-

ный по отношению к стековой организации взаимодействий. Тем не менее,

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

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

Типичный пример — синтаксическое управление трансляцией. Здесь вы-

делен главный процесс — синтаксический анализатор. Когда ему это нужно,

он запрашивает лексический анализатор путем обыкновенного вызова про-

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

редную лексему. Генератор лексемы останавливает себя сам, когда лексема

сформирована. Это реализуется как обычный возврат из процедуры. Понят-

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

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

В то же время,генератор лексемы работает в собственном контексте,основ-

ными данными которого являются поток (файл) входных символов и указа-

тель очередного символа этого потока. Можно естественно определить со-

стояние такого контекста (совокупность значений его переменных), которое

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

все основания рассматривать, пусть даже умозрительно, особую программ-

ную единицу, объединяющую процедуру генерации лексемы и указанный

контекст. Именно к ней обращается синтаксический анализатор за очередной

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

ничто иное, как реализация требуемого действия. И именно эта программ-

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

Аналогично можно выделить и другие сопрограммы транслятора: процесс

работы с таблицей имен, анализатор контекстных зависимостей, генератор

объектного кода и др. (конкретный набор сопрограмм зависит от архитекту-

ры транслятора).

При явном описании таких сопрограмм появляются определенные пре-

имущества:

• автономная и во многом независимая их разработка (зависимости сво-

дятся к определению протокола в качестве соглашения о взаимодей-

ствиях),

• осуществимость различных стратегий реализации каждой из сопро-

грамм,

• упрощение задачи распараллеливания.

400

ГЛАВА 8. ПОДПРОГРАММЫ

§ 8.5. ПАРАМЕТРИЗАЦИЯ

Параметризация —важнейший способ связи экземпляра программы с ди-

намическим контекстом. Данное понятие заслуживает серьезного анализа.

8.5.1. Назначение параметризации

Мы уже определяли параметризацию с точки зрения контекстов (см.§8.3),

определим ее с точки зрения действий.

Определение 8.5.1. Параметризация — средства языка программирования,

которые позволяют явно сопоставлять некоторым именам из локального кон-

текста процедуры (формальным параметрам) данные из динамического кон-

текста вызова, называемые фактическими параметрами. Формальные пара-

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

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

зывается передачей параметров.

Конец определения 8.5.1.

С конкретно-синтаксической точки зрения параметры делятся на позицион-

ные и ключевые.

При позиционной форме совокупности формальных и фактических па-

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

задается путем взаимно однозначного соответствия между списками: каждо-

му формальному параметру соответствует фактический, имеющий тот же

порядковый номер, что и формальный параметр. При ключевой форме ка-

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

Фактический параметр, помеченный ключом, считается соответствующим

формальному параметру с данным ключом (часто для пометки используется

синтаксис, подобный оператору присваивания: <ключ>“=”<фактический па-

раметр>). Использование ключевой формы позволяет задавать фактические

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

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

мальных параметров, а только для некоторых. Тем самым вызов процедуры

с не полностью заданными параметрами превращается в заготовку для вы-

зова процедуры с меньшим числом параметров, что соответствует матема-

тическому понятию частичной функции и стилю функционального програ-

мирования. К сожалению, в существующих языках программирования это

средство развито слабо. Ключевая форма удобна, когда для формальных па-

раметров определено некоторое стандартное задание, и тогда урпоминание

некоторых параметров можно опускать при вызове подпрограммы для ис-

8.5. ПАРАМЕТРИЗАЦИЯ

401

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

раметры в общераспространенных системах программирования.

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

вой формы параметризации для параметров-признаков: вместо фактического

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

нается ключ, а отсутствие признака отмечается отсутствием ключа. Встреча-

ются другие разновидности ключевой формы параметризации. Такие формы

обыкновенно применяются в командных строках.

Позиционная форма более традиционна,в частности,она принята в

С/С++

Pascal

и в большинстве других популярных языков. Она больше приспосо-

блена для контроля количества передаваемых параметров и согласования ти-

пов фактических параметров с типами формальных параметров (см. ниже).

Пример 8.5.2. Вызов с позиционными параметрами:

f(a+b,c[i],&d);

Вызов с ключевыми параметрами:

\includegraphics[scale=1.50, rotate=90]{ris2-1.eps}

Две формы такого же вызова, когда значения, предполагаемые по умолча-

нию, опускаются, и когда они задаются явно:

\includegraphics{ris2-1.eps}

\includegraphics[scale=1.00, rotate=0]{ris2-1.eps}

Ключевой параметр-признак:

copy /b ﬁle1.dvi ﬁle2.dvi

Конец примера 8.5.2.

Уменьшение привязанности процедур и функций к контексту — лишь одна

из задач, решаемых с помощью параметризации. Другая, не менее важная за-

дача, — это повышение гибкости программирования. Благодаря параметри-

зации можно объединять в процедуре не только совпадающие, повторяющи-

еся в основной программе вычисления, но и похожие вычисления, отличаю-

щиеся своими параметрами — программными объектами, которые конкре-

тизируют выполнение вычислений процедуры при ее вызове. При составле-

нии текста процедуры такие объекты должны быть тем или иным способом

обозначены; о таких обозначениях известно, что они употребляются в про-

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

В большинстве языков программирования способ обозначения параме-

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

мальных параметров: эти имена описываются в заголовках процедур. Как

402

ГЛАВА 8. ПОДПРОГРАММЫ

альтернатива идентификаторам, в некоторых языках используются порядко-

вые номера параметров (специально оформленные синтаксически, напри-

мер, выражения вида

в системе T

X). Этот путь в общем случае неудобен

из-за снижения уровня абстракций по сравнению с именами-идентификато-

рами, но целессообразен, когда мы задаем процедуру, которая может вызы-

ваться с очень большим нефиксированным числом параметров.

Имена формальных параметров пополняют локальный контекст проце-

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

именем, совпадающим с именем формального параметра, вызывает ошибку:

повторное описание имени.

В отличие от формальных, фактические параметры полностью относят-

ся к контексту вызова процедуры — они строятся с помощью средств этого

контекста как языковые конструкции, способные замещать формальные па-

раметры.

По своему назначению параметры подразделяются на три вида:

1. входные, in-параметры, которые поставляют значения для выполнения

процедуры;

2. выходные, out-параметры, которые принимают значения, вырабатыва-

емые в ходе выполнения процедуры, для внешнего использования;

3. совмещенные, входные и одновременно выходные, или inout-параме-

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

два предыдущих назначения.

Фактический in-параметр — это выражение того типа, которого требует со-

ответствующий формальный параметр. Небольшая оговорка здесь требуется

по поводу передачи подпрограмме в качестве параметров для внутреннего

использования процедур и функций, которые при обсуждении параметриза-

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

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

будут принимать в качестве значений алгоритмы процедур или функций. Ни

в одном развитом языке эта концепция не доведена до логической завершен-

ности. Ее непоследовательно реализованные фрагменты имеются во многих

языках (

Алгол-68

, несколько более ограниченно —

Ada

Turbo-Pascal

Фактические out-параметры — это переменные, т. к. только они в состоя-

нии принимать значения. Если рассматривать операнды выражений как еще

одну возможность принимать значения, то подпрограмму-функцию можно

8.5. ПАРАМЕТРИЗАЦИЯ

403

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

ленным out-параметром, который предписано использовать в синтаксиче-

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

зов функции.

Inout-параметры являются совмещением двух других видов параметров,

а потому их фактические параметры могут быть только переменными. Отли-

чие таких параметров от out-параметров лишь в том, что эти переменные

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

выражения in-параметров).

Перечисленные виды параметров характеризуют параметризацию с точ-

ки зрения использования процедур. Такое рассмотрение достаточно для кор-

ректного употребления процедур:три вида параметров исчерпывают все слу-

чаи взаимодействия процедур с окружением, необходимые на практике. Это

обстоятельство, по-видимому, является главной причиной того, что в совре-

менных языках программирования (например, в

Ada

) виды параметров ука-

зываются явно при описании процедур. Такой подход к параметризации со-

гласуется с интуитивным пониманием назначения параметризации и ее воз-

можностей.

Что же касается языка

С/С++

, то для его параметризации выбрана кон-

цепция, максимально приближенная к тому, как реализуется передача пара-

метров на машинном уровне. В частности, в нем представлен лишь один ме-

ханизм параметризации, через который все указанные виды параметров мо-

делируются. Если это и недостаток, то маленький, поскольку к такому моде-

лированию быстро привыкают и даже не замечают его при практической ра-

боте. Есть еще одно свойство языка

С/С++

, облегчающее неаккуратное про-

граммирование: возможность описывать функцию с одним числом параме-

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

вида параметров, а со средствами оперирования с ними.

Алголе 68

, как и в

С/С++

задается единый механизм параметризации,

но там он предлагается для экономии мышления, а не с точки зрения эффек-

тивной реализуемости. И хотя оказывается, что эти позиции не противоречат

друг другу (что наталкивает на мысль о согласовании принципа экономии

мышления с принципом экономии вычислений), все же явное определение

назначения параметров представляется более логичным.

Каждый фактический параметр должен быть таким, как того требует ал-

горитм процедуры. Эта характеристика параметризации называется согла-

сованностью типов фактических параметров с типами формальных параме-

тров. Правила согласования для разных языков различны в зависимости от

404

ГЛАВА 8. ПОДПРОГРАММЫ

целей, которые ставятся при разработке языка. Основная проблема здесь со-

стоит в противоречии между стремлением к повышению универсальности

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

параметров разных типов) и контролем корректности вызова.

Для пояснения этого тезиса используется следующая иллюстрация.Впол-

не осмысленна такая процедура (записывается в нотации, напоминающей

Паскаль, но это совершенно другой язык):

procedure Copy ( in X, out Y );

begin

Y := X

end;

Она копирует входное значение в выходное. С точки зрения такой се-

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

Copy

(в данном

примере используются имена, типы которых указаны как окончания иденти-

фикаторов):

Copy ( a_int, b_int );

Copy ( ’=’, c_char );

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

уже

Copy ( a_ﬂoat, b_int );

Copy ( 40, c_char );

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

которых естественно обозначить в данном языке int:=ﬂoat и char:=int.

А что будет, если в теле процедуры встречается, например, операция де-

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

Может быть, корректными фактическими параметрами, т. е. согласованны-

ми по типам с формальными параметрами, считать такие, набор операций

которых включает в себя всю совокупность используемых в теле процеду-

ры операций с соответствующим формальным параметром? Но тогда нужно

осознавать, что логическим следствием будет расширение этой совокупно-

сти вглубь вызовов процедур: если формальный параметр используется (в

теле процедуры) в качестве фактического параметра другой процедуры, то