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

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

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

415

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

значения некоторого вы-

ражения, поставляемого фактическим параметром. А так как во втором опе-

раторе формальный параметр

является получателем значения, фактический

параметр, подставляемый по наименованию (параметр-имя),может быть толь-

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

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

треблять и выражение (в данном случае целого типа).

В результате выполнения процедуры переменная

получает значение 1.

Таким образом, операторы

R(23);

R(2 + 2);

некорректны, но не по причи-

не использования выражений, а из-за наличия в теле

присваивания

x := 1

Различные возможности вызова по имени проиллюстрированы на рис. 8.6.

Полезно подробнее сопоставить последний вызов процедуры

Q(M[a])

при

R(u); {

— нецелочисленная переменная или выражение}

некорректен из-за спецификатора

Integer

в заголовке проце-

дуры, и это, вообще говоря, отношения к механизму переда-

чи параметров не имеет, а означает просто несоответствие ти-

пов. Вместе с тем, допустимы

R( b ); { если значение

до этого оператора определено, то это зна-

чение присваивается

, а переменной

присваивается 1}

R( a ); { значение, получаемое переменной

, есть 1, оно вырабаты-

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

Эти вызовы имеют тот же эффект, что и соответствующие вы-

зовы процедуры

. Допустимы и следующие вызовы проце-

дуры, соответствующие

Q(M[2]);

Q(M[a])

, но с совсем иным

эффектом во втором случае:

R(M[2]); { значение

M[2]

станет значением переменной

, затем

M[2]

получит новое значение 1}

R(M[a]); { вызов всегда корректен, возможна ошибка при вычислении

значения

M[a]

, если неверно 0 6 a 6 3. Результат первого

оператора тела — изменение значения переменной

. Если

для нового значения

верно 0 6 a 6 3, то корректен опера-

тор

x:=1

. Его эффект — присваивание значения 1 переменной

M[a]

, где у

новое значение }

Рис. 8.6. Вызов по наименованию

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

R(M[a])

имитируется подмена параметра

на

M[a]

. Поэтому первый опера-

416

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

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

Q(M[a])

, присваивает значение 3 перемен-

ной

, но далее текстуальная замена

на

M[a]

в операторе

x:=1

приводит к

присваиванию значения 1 переменной

M[3]

(а не

M[1]

, как при

Q(M[a])

Из примеров видно, что достигается при подстановке параметра по на-

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

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

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

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

Приведенное выше определение передачи параметров не совсем коррект-

но: понимаемое буквально, оно противоречит отмеченному общему прин-

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

процедуры,а фактические к контексту ее вызова. Иллюстрацией служит при-

мер на рис. 8.7. При буквальном понимании определения, переменная

, по-

...

var a : Integer;

procedure P(name x : Integer);

begin

... x ... {

Текстуальная замена

на

приводит

}

end; { P } {

идентификатор

в контекст, в котором

}

procedure Q( ... ); {

он понимается как имя глобальной переменной a,

}

var a, b : Integer; {

в то время как в точке вызова

}

begin { a

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

}

... P ( a ); ...

... P ( b ); ...

end; { Q }

...

Рис. 8.7. Плохой вызов по наименованию

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

, оказывается

той переменной, которая описана в первой строке примера, а переменная

(второй вызов

) и вовсе недоступна. С любой разумной точки зрения это не-

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

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

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

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

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

417

стижения этого может быть переименование переменных, т. е. замена всех

вхождений конфликтных имен новыми уникальными именами (в полном со-

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

мах при оперировании со свободными и связанными переменными).

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

умного метода санков (thunk), предложенного Ингерманом еще для

Algol 60

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

няется специальными подпрограммами для каждого фактического параметра

(именно они и называются санками). При исполнении вызова обращение к

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

Фрагменты текста программы, соответствующие фактическим параме-

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

thunk_параметра

, которые за-

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

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

раметр a[i+j], то он превращается в процедуру с глобальными переменными

, вычисляющую ссылку на соответствующий элемент массива. Техни-

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

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

зависящими от многих частных решений используемого языка. Вы можете

сами предложить несколько его реализаций на разных уровнях (см. упр. 1 и

следующее).

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

Алгол 68

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

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

имена как процедурные параметры, т. е. такие, которые требуют использо-

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

чае, функции. Допускается это не только в

Алголе 68

, но уникально то, что

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

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

быть выведены из понятия <

тело процедуры

>. В результате на

Алголе 68

мо-

дификация описания

P(name int x);

потребовала бы только замены спецификатора

name

на

proc

; а в вызовы про-

цедуры

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

фрагмент

как изображения процедуры

, скажем, наше выражение превратилось бы

В первоначальной версии языка

Алгол 68

было предусмотрено приведение любого выра-

жения к типу <

процедура без параметров, вырабатывающая ТИП

> (запроцедуривание). В

418

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

ref int: (a[i+j])

. В других языках, например, в

Pascal

’е для моделирования

требуемого эффекта требуется для каждого подставляемого фрагмента спе-

циально описывать функцию с телом <

фрагмент

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

процедуры

могут быть присваивания значений параметрам-именам. По-

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

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

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

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

(в данном случае двух) программ, представляющих параметр в теле проце-

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

параметров по наименованию: даже в

Алголе 68

она не может быть явно вы-

ражена. Уже по этой причине неверно было бы говорить, что процедурные

параметры реализуют механизм передачи по наименованию. Суррогат такой

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

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

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

property

, появляется лишь

в последний момент, в зависимости от конкретного экземпляра объекта. Но,

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

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

со структурным программированием или же это скорее (пока еще не исполь-

зуемый) атрибут сентенциального программирования.

Механизм передачи параметров по имени может претендовать на реали-

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

фектом передачи параметра как переменной, а потому с теми же оговорками,

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

параметра. Однако здесь ситуация еще сложнее, поскольку нельзя гаранти-

ровать и то, что параметр-имя сохранится в течение выполнения тела проце-

дуры.

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

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

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

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

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

Тем не менее механизм передачи по имени — единственный адекватный

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

свойствами, массу вредных побочных эффектов, исчезло.

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

419

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

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

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

изменится.

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

мирования достаточно часто. Даже использование параметров-переменных

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

лок — можно не заботиться о различии употребления формального параме-

тра в двух синтаксических позициях: в качестве источника и получателя зна-

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

нуждается в корректировке:

begin

a := взять_значение x;

взять_адрес x := 1;

end;

Словосочетания “взять_значение”и “взять_адрес” использованы для ука-

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

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

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

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

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

ми понятия передачи параметров как переменных и по ссылке. Понятно, что

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

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

Именно передача параметра по ссылке в

С/С++

реализуется с помощью

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

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

них” механизмах. В самом деле, заголовок функции

void S ( int *x )

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

щее на целочисленное значение. В частности, выражение

&Variable

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

Variable

. А это именно то, что нужно

для передачи параметра по ссылке.

Передача параметра по необходимости — это скорее подход, чем кон-

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

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

420

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

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

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

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

мой стратегии ленивых вычислений (lazy evaluations). Суть стратегии в том,

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

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

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

буются для дальнейшего продвижения процесса вычислений. В результате

можно (чуть-чуть нестрого) утверждать, что при стратегии ленивых вычи-

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

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

намного эффективнее самих откладываемых вычислений.

У параметризации по необходимости три цели:

• обеспечение вычислений с некорректно заданными параметрами в тех

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

вычислений;

• обеспечение того, что мы используем наиболее ‘свежее’ значение па-

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

вычислений.

• повышение эффективности вычислений.

Первая цель кажется несколько искусственной, но на самом деле ее важность

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

, где фактически ре-

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

A&&B

то вычисление

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

и получе-

но значение

true

. Из-за этого, в частности, корректен следующий оператор

(li x — интергральный логарифм x, который определен лишь при x > 0):

if (x>0&& li(x)>y) x+=epsilon;

(8.2)

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

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

Вычисление логических операций в

поучительно сопоставить с их вы-

числением в

Pascal

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

ность вычисления операндов (как для любых выражений — см. § 5.2), а во-

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

тинность или ложность выражения выясняется до того, как все составляю-

щие выражения вычислены (есть прагматически устанавливаемый режим, в

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

421

котором запрещается подобная оптимизация). В результате транслятору раз-

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

ющие их истинность или ложность, с тем, чтобы выбрать наиболее эффек-

тивный путь вычислений. Как следствие, пример, подобный (8.2) может ока-

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

Pascal

. Прагматическая полез-

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

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

Pascal

принята стратегия

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

том

С/С++

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

по необходимости — распределенные вычисления. Пусть программа работа-

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

рывно модифицируются другой программой. Предположим, что наша про-

грамма не изменяет данные, но принимает решение на основе их анализа.

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

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

ровать ту информацию, которая соответствует реальному состоянию дел. И

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

сети, естественно передавать по необходимости, а не по значению.

Тот же пример иллюстрирует и третью цель параметризации по необходи-

мости. Для установления связи и последующей работы с удаленными данны-

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

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

туация сложится так, что без удаленных данных можно будет обойтись. Еще

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

стрируют логические операции: &&, || и др. (смотри анализ первой цели).

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

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

и концепция имеет право на существование.

Рассмотрим, как соотносится механизм подстановки параметра по необ-

ходимости с другими механизмами параметризации.

Передача по необходимости моделирует входной параметр в том случае,

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

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

метр. Не следует в связи с этим исключать предельной возможности, когда

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

вызова (т. е. как параметр-значение).

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

422

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

лее сложная. Стратегия ленивых вычислений предписывает откладывание

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

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

выполнения процедуры (в частности, при последовательных вычислениях

она с гарантией возникает после завершения). Как следствие, последний мо-

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

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

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

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

димости дана на рис. 8.8.

Гарантия

неизменности

Гарантия

неизменности

Вызов

процедуры

Использование

in-параметра

Вычисление

out-параметра

Использование

out-параметра

Возврат из

процедуры

Перенос назначения

необходимости

Рис. 8.8. Перенос назначения необходимости на более ранние сроки

Механизм передачи параметра по наименованию содержит некоторые чер-

ты подстановки по необходимости. В самом деле, санк выполняется тогда и

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

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

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

щениях к соответствующему формальному параметру.

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

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

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

value N : by need

при первом обращении к

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

следующих обращениях — к эффекту работы с обычной локальной перемен-

ной (санк становится ненужным). При первом обращении к

, определяемо-

му как параметр-переменная

var N : by need

аналогично в стек загружается ссылка на

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

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

423

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

Константные параметры. Осознание того,что некоторые передаваемые

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

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

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

раметра, или, короче, о константном параметре. Это понимается как огра-

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

процедуры.

Object Pascal

константный параметр синтаксически оформляется сле-

дующим образом:

procedure P ( const <описание формального параметра> );

В руководстве по языку

Object Pascal

сказано, что константный параметр

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

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

процедуры или функции. Как и любой другой константе, константному па-

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

левой части оператора присваивания).

С++

оформление константного параметра практически такое же:

void P ( const <описание формального параметра> );

Для неуказательных типов это означает в точности же эффект,что и для

Object

Pascal

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

мяти в стеке с ограничением возможности присваивания значений точно так

же, как и для любого локального константного описания.

Ситуация меняется,если речь идет об указателях. Из требования руковод-

ства по

Object Pascal

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

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

описанием. Коль скоро она получает значение фактического параметра-ука-

зателя, это значение не может быть изменено. В

С++

данная конструкция

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

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

нии формального параметра спецификатор

const

защищает от изменения эту

память, а не значение самого указателя.

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

Приведенное разъяснение явно показывает, что для обоих языков кон-

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

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

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

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

424

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

емого значения. Напротив, для

Object Pascal

тот факт, что константные па-

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

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

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

семантики. Это снимает противоречие между желанием передавать входные

параметры-массивы по значению и стремлением к эффективности, которое

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

ся параметрами-переменными. А константный указательный параметр языка

С++

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

вами, структурами и другими составными типами.

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

всего лишь иное прагматическое оформление входных параметров.

TURBOPascal

версии 7.0 и

ObjectPascalDelphi

предлагают еще один спо-

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

логичных механизму передачи параметров по именам. Речь идет о так назы-

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

мощью спецификации var, const или out имени формального параметра, за

которой не указывается тип параметра:

procedure Change_any( var x );

procedure TakeAnything(const C);

procedure GiveSomething(out Res);

Вместо

или

Res

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

ная любого типа, вместо

— произвольное выражение.

На самом деле нетипизированные параметры являются естественным обоб-

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

возможности языка, расширяющей

Pascal

, — на область параметризации.

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

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

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

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

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

ных, которая затушевывается синтаксически.

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

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

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

параметр (или нетипизированный указатель), была как-то определена. Это