Бауэр Ф.Л., Гооз Г. Информатика. Том 1

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

3.5. Процедуры 231

сивно

сформулированным) сокращением для того оператора

«икла, что стоит в теле подпрограммы

potz.

В подпрограмме

gcdl

из

3.3.2.1

повторяемый оператор можно

привести к виду

mvar

tnod(mvar

,nvar);

{mvar

,nvar)

:==

(nvar ,mvar),

•и,

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

зовами

mo(mvar,nvar); exch(mvar,nvar),

где процедура

exch

была описана выше, а то описывается так:

ргос

то = (var int

uvar,

war):

uvar

war

then

uvar

uvar—war;

(uvar,

war)

else

skip fi

procedure

mo (var

uvar,

war:

integer);

begin

uvar

S war

then

begin

uvar

'.=

uvar—war'.

end

else

skip

end

(uvar,

war)

3.5.3.

Вызовы

процедур

Как

видно уже из приведённых выше примеров, вызовы про-

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

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

При

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

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

мул, а фактические значения параметра-переменной — это про-

сто заменяющие его описанные переменные.

3.5.3.1

Разумеется, в качестве фактических значений можно исполь-

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

держит соответствующий вызов. При этом речь может идти о

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

менной.

Первый случай имеет место в приведённом на рис. 123

примере вызова процедуры ord в ещё одном варианте подпро-

граммы gcd (см.

3.3.5.1),

со вторым мы сталкиваемся при вы-

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

exch

в теле процедуры ord, а также при рекур-

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

речь идёт о простой замене параметров-переменных неизмен-

ными

или в свою очередь заменёнными обозначениями, т. е.

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

вестись работа.

Вызов

процедуры

— это

тоже

оператор.

В нерекурсивном

случае он равносилен программному формуляру, получающе-

232

Гл. 3. Машинно-ориентированные алгоритмические языки

funct gcd=(\ni n, int m

сол>0лт>0 со) int:

f(var

int

mvar,

nvar)

:= (m, n) ;

while

mvar

nvar

do ord

(mvar,

nvar)',

mvar:—

mvar—nvar

od ;

mvar

function

gcd(n,

integer

{(n

> 0) л

(m>0))):

Integer

var

mvar,

nvar:

integer;

begin

(mvar,

nvar)

:= (m, n);

while

mvar

nvar

begin

ord(mvar,

nvar)

;

mvar

—nvar

end;

end

Рис.

12.5.

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

параметров фактическими значениями и переменными. Вложен-

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

туру.

3.5.3.2

Рекурсивные же процедуры, как и в случае машины обра-

ботки формуляров,

ведут

прежде всего к появлению различных

воплощений

программных формуляров, причём в каждом из

воплощений

реализуется своя собственная замена параметров

фактическими

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

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

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

площений;

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

вается в этом случае блок-схемой программы.

При

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

влений

для параметров-переменных. Его смысл в полной мере

проявляется в связи с групповыми присваиваниями. Например»

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

procedure

tip (var x,y : recd)\

begin

(*,*/):= (1,0)

end

proc

(var

real

x,y):

вызов hp(a, а), конечно же, запрещён '.

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

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

Запрет отождествлений целесообразно сохранять

даже

в таких спе-

циальных

случаях

(вроде оператора взаимного обмена (а, Ь) := (й, а)),

когда нарушение этого запрета не

ведёт

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

3.5. Процедуры 233

сительно отождествлений

отсутствует'.

Однако и здесь прене-

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

осложнениям.

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

приходится прибегать к её линеаризациям, например к

ргос

hpl ==(var

real

x, у):

procedure

hpl (var x, у: real);

begin

x := 1; г/:=0 end

или

же

ргос

/jp2 = (var

real

x, у):

Гг/:=О; х := 1J

procedure

hp2 (var x,y: real):

begin

у := 0; x := 1 end

Обе процедуры hpl и hp2 являются корректными линеаризация-

ми

(идеальной) процедуры hp и эквивалентны между собой при

соблюдении запрета отождествлений; тем не менее вызовы

hpl

{а,

а) и hp2(a,a)

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

ноа:=0

иа:=1.

3.5.4.

Транзитные

параметры

параметры-результаты

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

ческой переменной, вообще говоря, изменяется. Такие

тран-

зитные

параметры-переменные

(параметры

доступа)

представ-

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

рах exch, pop и ord, а также в pot.

Однако может случиться и так, что имеющееся в месте вы-

зова значение переменной, являющейся значением параметра,

не

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

случае говорят о

результатном

параметре

или о

параметре-ре-

зультате.

В примере процедуры hp мы обнаруживаем самые на-

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

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

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

результатов. Для подпрограмм алгол-68 и паскаль такой воз-

можности не допускают (без явного введения составных объ-

ектов).

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

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

Пример.

Из тела подпрограммы

modi

(см.

3.3.2.2)

полу-

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

В сообщении об алголе-68 важность запрета отождествлений была

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

ний.

Руководство по паскалю гласит: "...schould be distinct

variables."

[„...должны

быть

различными

переменными."

(англ). —

Перев.]

234

Гл. 3. Машинно-ориентированные алгоритмические языки

которую можно достроить до процедуры, находящей одновре-

менно

и частное:

proc

moddivl

(var int

int

со

т&0лл>0

со):

0 ; r

'.=

while

r>n

q:-=:q

l',

r.=*r-n

odJ

procedure

moddivl

(vaf

q: integer;

n '. integer

((mS0)and(«>0)));

begin

q:—0',r:=m

while

r^n

begin

?1=5+

;

end

В этой процедуре m, n — обыкновенные параметры, а добавлен-

ные

параметры-переменные г, q — параметры-результаты. Для

г, q характерно, что они не обязаны иметь каких-либо значений

при

входе

в процедуру, а коли

даже

они имеют какие-то значе-

ния,

то эти значения несущественны. (Именно по этой причине

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

менные

и без их инициализации.) Если теперь, скажем, обыкно-

венный

параметр т во

всех

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

moddivl

пред-

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

mvar»

которая

после этих вызовов больше не используется, то пере-

менную

mvar

можно отождествить с одним из параметров-ре-

зультатов, лучше с г, и получить

proc

; (var int A, q, int n

Л п > Oco):

[q:=0;

r:=r,

while

r^n

do q:= q + 1;

/•:=/•

— n odJ

procedure

moddiv2

(var r, q:

integer,

n'.integer

{(r^O)

and

(n>0)})i

begin

= 0; r := r,

while

r > n

begin

q := q + 1;

:==

r — n

end

Отождествление

mvar

с г

даёт

вырожденное присваивание

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

цедуры.

Хотя ни в алгольном, ни в паскалевском варианте никаких

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

однако природа их весьма различна: если q — это по-прежнему

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

входе

в процедуру

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

зывает остаток. Таким образом, параметр-переменная г изме-

няется

процедурой, т. е. г — транзитный параметр.

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

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

ными)

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

ляются вначале делимое и делитель, а в конце остаток и част-

3.5. Процедуры

235

ное,

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

тельное обозначение:

proc

moddfyjsfyar

int r,q

согйОлj>0

со);

Tint n = q , с/.= 0;

while

гй/t

dor:=r~/i;2:=?+l

procedure

modd!v3

(var r q :

\nleqer

((/SO) and fa;>О}));

var и :

integer

begin

/1=9;

j:=0;

while

rin do

beginr;»r~/i;

3 := g +1 end

end

Разумеется, подпрограммы с простым результатом также

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

результатов. По этой причине в некоторых (устаревших) языках

программирования подпрограммы

отсутствуют

вовсе — в них

предусмотрены только процедуры.

Транзитный

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

обыкновенный

и один параметр-результат. Это продемонстри-

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

параметром для „счёта", выполняемого „в некоторой заданной

переменной":'

proc

increm^

(var int x):

procedure

increm

(var x :

integer);

:= x + 1J

begin

x := x -f- 1 end

Выходное значение параметра-переменной „портится" вызовом

процедуры

increm.

Чтобы избежать этого, нужно „расщепить"

транзитный

параметр:

proc

incr

н=

(int n, var int x):

procedure

incr

(n :

integer;

var x :

integer);

begin

x:=n-\- 1 end

Теперь эффект вызова

increm(a)

достигается специальным вы-

зовом

incr

(а, а). Отметим, что в последнем вызове нет никакого

«арушения запрета отождествлений!

3.5.5.

Входные

параметры

Конечно,

случае

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

всегда можно было бы вводить параметры-переменные. Напри-

мер,

исходя из процедуры

moddivl,

получим

proc

mod-lw4

s (var int

1»,

И,

г.

procedure

moddn.•/(var

m,n.f q

integef.

Hm^kO)

and (п>Щ;

Ниже

increm

— от increment (приращение). — Прим.

перев.

236

Гл. 3 Машинно-ориентированные алгоритмические

языки

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

moddivl

не требуется. В этом теле нег ни одного присваивания

параметрам-переменным т, п, т. е. их значения остаются неиз-

менными.

Такие параметры-переменные называются

входными

параметрами.

Например, параметр war процедуры то из 3.5.2

является входным.

Употребление входных параметров вместо обыкновенных

связано

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

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

формулу. Понятие входного параметра берёт начало от машин-

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

{'read-only'').

3.5.6.

Подавляемые

параметры

Параметры-переменные можно опускать („подавлять"), если

их замена не предусматривается.

Примером

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

щая

процедура

счёт,

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

для подсчёта того, сколько раз употребляется определённая

операция

в данном алгоритме:

procedure

счёт;

begin

х :=х -f- I end

proc счег =

Предупреждение о том, что х — это (глобальная) перемен-

ная,

а не обозначение обыкновенного объекта, снимается в ал-

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

iunct

potz

(rea\

intn

со п а 0 со)

real:

Гргос

ро в

: if nvar>

then

{avar,

nvai)

{avur

\2,

nvar-1):

else

skip

fi;

(var real

avar,

var int

nvar):=°(a,n);

po;

avar

function potz(a : teal; n :

integer

[n>0}):reaf'

var

avar:

real;

nvar:

integer;

procedure

po;

begin if nvar>0

then

begin

(avar,

nvar):=

(sqr{avar),

nvar—

1);

po end

else

skip

end;

begin

(avar,

nvar).= (a,n);

end

Рис.

124

po;

pon

avar

„Только

читать" {англ.). — Прим.

перев

3.5.

Процедуры

237

Для того чтобы отличить процедуры, в которых все пара-

метры опущены, от обыкновенных операторов, в

алголе-68

перед

ними

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

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

между

точками с запятой или скоб-

ками-уголками.

Опуская неизменные параметры

avar

nvar

рекурсивной

процедуры pot из

3.5.2,

мы получим рекурсивную процедуру ро

без параметров. Её можно использовать в подпрограмме

potz

формулировке, представленной на рис. 124. И в рекурсивной

процедуре то из 3.5.2 также можно опустить оба неизменных

параметра

uvar

и war.

Эффект

процедуры с опущенными параметрами-перемен-

ными

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

параметров-переменных

ведёт

к побочным эффектам, которые

легко упустить из

виду,

не стоит применять его бездумно. В ча-

стности, при

частичном,

подавлении параметров-переменных мо-

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

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

„удвоения"

с глобальным параметром-переменной п:

proc

r/des=(var

int и):

procedure

уде (var и :

integer);

begin

и :=и * 2;

«:=«+ 1

end

В последовательности вызовов

удв(а);

удв(Ь);

удв(а);

удв(п)

последний нарушает запрет отождествлений (и

даёт

п:=2Х

п + 1, что явно не совпадает с тем, что мы ожидаем).

3.5.7.

Процедуры

как

средство

структурирования

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

программного текста. Программистская методика, делающая

упор на работу с программными переменными (например, по

соображениям машинной аргументации), склонна к выдвижению

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

(Это,

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

стоянно

печатать результаты в

ходе

исполнения некоторой про-

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

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

тов.) Процедуры как средство организации иерархической

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

венным

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

238

Гл.

Машинно-ориентированные

алгоритмические

языки

примера рассмотрим операцию замены (*) в алгоритмах Мар-

кова

(см.

1.6.4.1).

Вспомогательной процедурой

будет

служить

поэлементно

сравнивающая „разборка" (слева)

двух

строк (це-

почек

символов) a, v: '

proc

subtr=

(var string

b):

while

(a+O л Ь+О) А

first

(a)

first

(b)

(a.

b):=*(rest(a),

rest(f>))

procedure

subtr(var

a,b

string);

begin

while

not

(isempty

(a)

isempty

(b))

first

(a)

first

(b)

(a, b) := (rest

(a),

rest

(b))

end

Нам

нужно заменить первое слева вхождение строки А в строку

В на строку С. После введения

двух

переменных a, b с их ини-

циализацией

значениями А и В соответственно и вызова

subtr(a,b)

ситуация такова. Если а= (), то А является нача-

лом В, т. е. В = A -f b, и А в В можно заменить на С. Далее,

если

а^=<),но

Ь=о.

т0

А длиннее В, и интересующая нас за-

мена вообще невозможна. В оставшемся случае нужно попро-

бовать предпринять замену А на С в строке

rest

(В), а перед

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

first

(В). Таким обра-

зом,

используя вспомогательную процедуру

subtr,

мы получаем

рекурсивную формулировку, приведённую на рис. 125. Можно

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

ные—

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

другую

для построения результата.

funct

enet:e&(string А, В, С)

string:

T(var

string

a,b):=-(A,B)\

subtr

(a.

b);

it « = О

then

C+b

elsf

b=O

then

else (first(B)) +

ersetze(A,

rest(B),C)f\

function

eisetze(A. В. С: string)'.

string

var

b :

string

;

begin

(a,b):=>(A,B),

subtr

(a,

b);

if isempty (a)

then

ersetze

« cone (C, b)

else if isempty (b)

then

ersetze

else

ersetze

prefix (first (B),

ersetze

(A,

rest(B),Q)

end

Рис.

125.

Ниже

subtr — от subtraction

(вычшание),

a ersetze (нем.) означает

„замени",

— Прим. перев.

3.5. Процедуры 239

3.5.8.

Рекурсивное

определение

повторения

3.5.8.1. Переход как гладкий вызов процедуры

без параметров

В подпрограмме

potz

из раздела 3.5.6 нам встретилась про-

цедура (без параметров) такого вида:

ос 52 =

: if >условие<

then

юператор<;

else

skip

fi;

procedure 3l\

begin

if >условие<

then

begin >oneparop<;

end

else

skip

end;

begin

end

Если

сравнить эту формулировку с соответствующей формули-

ровкой,

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

со следующей петлей (см.

3.4.2.2):

rep: if >условие<

then

юператор<;

goto rep

else

skip

begin

1: if >условие<

then

begin

>оператор<;

goto

1 end

else

skip

end

то становится понятно, что операторы перехода — это просто

вырожденные регулярные вызовы (рекурсивных) процедур

без параметров.

Таким

образом, кто хочет запретить операторы перехода,

должен запретить и рекурсивные процедуры.

3.5.8.2.

Рекурсивное определение условного повторения

После

сказанного выше

ясно,

что оператор цикла (см.

3.3.2)

while

>условие<

do >оператор< od

while

>условие<

do >оператор<

может быть определен как процедура (») из 3.5.8.1.

240

Гл. 3

Машинно-ориентированные

алгоритмические языки

При

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

ределение:

if >условие<

then

юператор<;

while

>условие<

do юператорс od

else

skip

if >условие<

then

begin

юператор<;

while

>условие<

do >оператор< end

else

skip

Таким

образом, тело процедуры pot из 3.5.2 и тело процедуры

без параметров ро из 3.5.6 запишутся совершенно оди-

наково

в форме с оператором цикла (см. также

potz

3.3.3.1):

while

nvar

> 0

(avar,

nvar) :=

(avar \

2,nvar

— 1) od

begin

while

nvar

> 0

{avar,

nvar) :=

(sqr(avar),nvar-

end

•1)

3.5.8.3.

Рекурсивное

определение

повторения

пересчётом

Повторение

часто связано со счётом, как это имеет место,

например,

potz,

где счёт ведётся в переменной

avar,

начиная с

а,

„вниз"

до 0. Для этой цели вводят, следуя

Гутисхаузеру

(1951 г.), специальное сокращение—

оператор

цикла,

работаю-

щий по

счётчику

(или с

пересчётом),

где счётчик — это параметр

цикла,

который пробегает целые значения от

начального

>starl<

до

конечного

>goal<' (включительно) с

шагом

>step<

(причем

for

счётчик

from

>start<

>step<

>goal

do >оператор< od

(алгол-68)

Повторяемый

оператор >оператор< может при этом содержать

переменную

счётчик.

Повторение

с пересчётом можно определить как применение

некоторой

рекурсивно определённой процедуры G. А именно, опе-

ратор цикла, работающий по счётчику:

for

счётчик

from

>start< by >step< to >goal< do >оператор< od

Цель (am.i).

—

Прим,••перса.

Шаг (англ.).—Прим.

перев.

Соответствующий русскоязычный вариант выглядит так-

для

счётчик

от )старт< через )шаг< до >фикиш< цк >оператор< кц.