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

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

3.4. Операторы перехода

221

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

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

щему некоторой непосредственно рекурсивной подпрограмме.

Если

графически изобразить процесс движения (называемый

также

исполнением),

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

мных формуляров возникнет „схема движения" —

блок-схема

mvar

nvar

Переменные:

var int

Беов

Вывод

Рис.

116. Блок-схема, полученная из программного формуляра на рис. 95.

программы.

На рис. 116 дан пример такой блок-схемы, получен-

ной

из программного формуляра на рис. 95, соответствующего

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

gcdl,

„обрамлением" (заключением в рамочки)

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

(передачи)

управления.

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

из

стандарта DIN

66001

(рис. 117).

Более компактной является

другая

форма блок-схем, полу-

чающаяся возведением графической „надстройки" над програм-

мным

текстом. Так, в соответствии со сказанным в 3.4.2 подпро-

222

Гл. 3.

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

Символи-

ческое

изображе-

ние

Объяснение

ттг

Операция

общего вида, в

особенности если

она не

подпадает

ни

под

один

из

следующих

четырёх типов.

Разветвление.

Такие точки

блок-схеме,

которых

на

осно-

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

из не-

скольких возможных продолжений.

Вызов

подпрограммы;

обычно

эта

подпрограмма описывает-

ся

другой

блок-схеме.

Модификация

программы, т. е.,

например, места расположе

ния

запрограммированных переключателей, изменение

индексных регистров

или

модификация самого программного

текста

(не

рекомендуется!).

Ручная

операция,

связанная, вообще говоря,

ожиданием.

Ввод,

вывод.

Линия (дуга) передачи управления,

предпочтительные

на-

правления—

сверху

вниз

слева направо; возможны

—

при

отклонении

от

предпочтительных направлений

даже

необходимы

—

стрелки, направленные

следующему

симво-

лическому изображению.

Схождение,

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

блок-схеме.

Точка перехода,

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

для „связывания"

двух

концов разорванной

на

блок-схеме

линии.

Пограничные точки, т. е.

начало

конец исполнения,

также

программные прерывания.

Синхронизация

при параллельном выполнении,

особенно

следующих

трёх

случаях:

Расщепление

в режиме параллельного выполнения.

„Сращивание"

ветвей в режиме параллельного выполнения.

Синхронизационное

сечение.

Примечание,

может быть присоединено

любому

другому

символу.

Рис.

117.

Символы

для

блок-схем (стандарт DIN

66001).

3.4.

Операторы

перехода

•fund

gcdl s([nt

OT,nco/77?-OAn?Oco)int:

223

Varint

4]mvarl,

ч/nvar/,

V/resuli/;

Bao8l—.

(mvar,

nvar):

(m,n)

gcdl:

\result:=mvar

else

(mvar,

nvar):

(nvar,

mod

(mvaf,

nvar))

goto

gcd

Рис.

118.

Блок-схема,

полученная

возведением

графической

„надстройки"

над

программным

текстом.

грамма

gcdl

(см.

3.3.2.1)

допускает формулировку

funct

gcdl з

(int

т,

п со

nS 0 со) int:

var int

mvar,

nvar,

result;

(mvar,

nvar):=t(m,

n);

gcdl:

nvar

then,

result

:==

mvar

else

(mpar,

nvar):=(nrar,

mod

(invar,

nvar))',

goto

gcdl fi;

которая

даёт блок-схему, изображенную на рис. 118.

3.4.3.2

Повторительной

системе подпрограмм отвечает набор из соот-

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

мой

благодаря связующим переходам. Рис. 119 демонстрирует

это

для рассмотренного в

2.4.1.4

и 3.4.1 примера системы подпро-

грамм

(ispos,

isneg).

Чтобы не превращать блок-схему в „лабиринт", управляю-

щие

дуги

можно разрывать, отмечая соответствующие

„вися-

224

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

щие"

концы с помощью

точек

перехода

(см. рис. 117). На

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

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

ход. Переходы сами по себе—вещь вполне естественная, если

они

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

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

Я-

т т т

£7

„ f7 £7

т 6 ^/

tsneg

Cspps

£7 ^7 ^-Z ^7 ^-7

if *"£/ ft

•fund ispos в (string m) boot

£7 £7 £7

first"_" r«sf rest

QCJO £7

m 6 \c/

P°

s lsne

£7 & £7C7 C?

\c/

false ^ then..,,-el5e

Cl£7 , ^ £7 ft

vf £7 ft

var string

\nvar,-rest(pvar)\,

Ypvar

=rest(pvar)\;

\ result =true |;

else grtoenrfl fi,

| remit =fa.lie|

d Д f

else goto end Д fi

goto mn^ gotompj ft, gotomp,^

end О

ВывоЗ

-/result/

goto

Рис.

119 Вычислительные формуляры для системы подпро1раммы

(ispos,

isneg)

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

3.4.1.

Иначе

обстоит дело с „дикими" переходами, которые вводят по

причине

недостаточного понимания структуры алгоритма. Дейк-

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

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

ваемого „дальнодействия" '. Некоторые чересчур рьяные сто-

Слегка утрируя, Дейкстра пишет: ". the quality of programmers is a

decreasing function of the density of go to's in the programs they produce...

..the

go to statement should be abolished from all 'higher

level'

piogramming

languages (i.e. everything except, perhaps, plain machine code)" [„.квалифи-

кация

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

go to в создаваемых им программах оператор go to следовало бы

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

всюду, кроме, разве, простого машинного кода) (англ). — Перев.

3 4 Операторы перехода

225

ронники

не только вывели отсюда, что в „хорошо структуриро-

ванных

программах" лучше всего вообще не использовать пере-

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

диаграммы Насси — Шнейдермана,

будет

„хорошо структуриро-

ванной".

Без

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

ные

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

funct

Isposneg

(siring

boot

boot:

ВооЗ

var string Щ

mvar

I, var

boot

Щ war I ;

(muar,

vvar)-=

(m, v)

else

skip

ft;

mar I— ВывоЭ

Ihen

else

(muar,

war):

=(rest(muar),

war)

(mvar,

war);=(resl(mvar),

war)

Рис.

120. Блок-схема для

isposneg.

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

могут

быть вло-

жены

друг

друга

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

1ельно

друг

за другом, см 3 3.2 3. Часто, однако, требование из-

бегать переходов приводит к дублированию программного тек-

ста. Иногда (но далеко не всегда) это может даже оказаться по-

лезным

для

понимания,

см. в связи с этим подпрограмму

isprim

из

3.4.2.3.

Для системы подпрограмм

(ispos,

isneg)

сведение к одному-

единственному оператору цикла

требует

слияния

обеих под-

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

Такую подпрограмму

isposneg,

определяемую следующим об-

разом:

funct

isposneg

(string

bool

bool:

if v

then

ispos{tn)

else

isneg(rn)

fi,

Л. Бауэр, Г. Гооз

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

А1

s:=

false

while

true

AZ A3

while

B1ABZ

Рис.

121. Блок-схемы с переходами и дистанционными переключателями.

3.5. Процедуры

227

можно записать

как

повторительную:

funct

isposneg

(string

bool

boo!:

then

\1Jirst(m)

"~"

then

isposneg(rest(m),

"ID)

else

isposneg(rest(m),

else

v fi .

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

жена

на рис. 120 в

виде блок-схемы, допускающей дальнейшие

упрощения.

3.4.3.3

В общем

случае

было доказано

(Бём,

Джакопини

(1966 г.),

Ашкрофт, Манна

(1971 г.)), что за

счёт введения дополнитель-

ных логических переменных

от

переходов

блок-схемах

про-

грамм всегда можно избавиться

в том

смысле,

что

можно обой-

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

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

для записи программ только диаграммы'Насси

—

Шнейдермана.

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

„дистанционными

переключателями"

и как

таковые приводят

по

меньшей мере

столь

же

скверному „дальнодействию",

что и

переходы.

Довольно сомнительно, чтобы

блок-схеме

(Ь) на рис. 121,

содержащей лишь одну петлю

представимой

виде диаграм-

мы Насси

—

Шнейдермана, достигалась большая ясность,

чем

блок-схеме

(а).

Пожалуй, здесь лучше было

бы

подчинить

повторение оператора

А4

условию

В1 Л В2,

после чего

ещё раз

смотреть, выполнено

ли

условие

В1 (для

выбора

между

А2 и

A3),

как это

реализовано

блок-схеме

(с).

3.5. Процедуры

(Вспомогательные) подпрограммы предназначены

для

сокра-

щения

записи часто встречающихся формул

алгоритмов,

тек-

стуально совпадающих

или

имеющих одну

и ту же

структуру.

После

того

как в

этой главе были введены операторы,

у нас по-

явились

еще и

операторы

одинаковой структурой; например,

мы

уже

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

resi(v).

Возникает потребность параметризовать также

операторы

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

для

них

сокращённые обозначения. Однако прежде нужно

раз-

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

качестве параметров.

Из-за

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

грамм

— их

чисто функциональный характер.

таком

случае

мы говорим

„процедурах".

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

3.5.1.

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

Рассмотрим три просто устроенных оператора

m :=

rcst(tn),

(*,//):=

(1,0),

(a,b):=(b,a).

Здесь m, х, у и a, b должны быть переменными, поскольку им

что-то присваивается. Так как переменной m присваивается ре-

зультат

применения операции

rest,

m может быть переменной

для объектов вида

string

(соотв. типа

string);

можно коротко

сказать, что пг имеет вид var

string.

Точно также х и у должны

быть переменными для объектов, имеющих изображения 0 и 1,

т. е. для объектов целого или вещественного сорта. Лишь в спе-

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

(a, b) := (b,a) совершенно не важно, какого сорта те объекты,

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

Итак,

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

ратора, представляют собой, вообще говоря, переменные вполне

определённого сорта. Один из основных принципов

алгола-68

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

ров-переменных.

Операторы, содержащие присваивания переменным, которые

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

для них, имеют

побочные

эффекты;

упомянутые переменные яв-

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

эффектов

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

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

была бы безрезультатной.

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

замещаются

при

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

вызванная

про-

цедура

использует

переменные

из

окружения

вызова,

она

носит

паразитический

характер

по

отношению

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

менным.

Параметры-переменные обладают чертами, с которыми мы

ещё не сталкивались при рассмотрении обычных параметров.

Обычные параметры заменяются при вызове фактическими зна-

чениями,

так что вызовы вроде

gcd(l8,l8)

или

gcd(a,a)

вполне корректны.

Однако разные обозначения для переменных, например х и

у в (х, у) := (1, 0) или аи b в (о, b) := (b,a), означают, что

речь идёт о существенно различных объектах. Отсюда

вытекает следующий

3.5. Процедуры

229

Запрет

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

для

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

Ника-

кие

два

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

разными

обозначениями

не

должны

при

вызове

замещаться

одной и

той

же

переменной.

Бессмысленным

будет,

разумеется,

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

с (не-

тривиальной) формулой

позиции параметра-переменной.

3.5.2.

Описания

процедур

Параметризованный

оператор называется

процедурой. В от-

личие

от

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

не

вырабатывает никакого

результата,

т. е. не

может встречаться непосредственно

выра-

жениях.

соответствии

этим

описании

не

нужно указывать

сорт результата. Чтобы процедура давала некоторый эффект,

она,

как

правило, должна содержать

по

крайней мере один

па-

раметр-переменную, хотя наряду

этим

могут

присутствовать

все обсуждавшиеся

до сих пор

параметры

— как

обыкновенные,

так

параметры-подпрограммы. Параметры процедуры

могут

быть перечислены

явном виде

или

опущены.

Это

относится

и к

параметрам-переменным. Телом описания процедуры является

оператор,

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

как

программный форму-

ляр

(см.

3.3.1).

Способ записи

описаний процедур

похож

на

запись

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

от-

сутствия сорта результата, состоит

в том, что

вместо

funct или

function

пишут соответственно

ргос или procedure.

Примеры

(а)

Оператор взаимной замены

ргос

exch

s (var int

V):

procedure

exch

(var a,b :

integer)',

var h : integer;

begin h

a ;

a:=6;

6:= Л

end

(b) „Укорачивание"

переменной-цепочки:

pro

pop=(var

string m

со-

со):

:=rest(m)

procedure

pop

(var

m'.

string

begin

in:—

rest(m)

{not

isemptyQn)});

end

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

var в

заголовке пишут

ref [от

reference (буквально: упоминание, отсылка).—Перев.]

Ниже

exch

— от

exchange (обмен, замена).

—

Прим.

перев.

оригинале ,Рорреп'

—

немецкий неологизм, произведённый

от

англий-

ского

„pop"

(хлопать, выбивать)

означающий „выталкивание"; отсюда

используемое ниже обозначение

pop. —

Прим.

перев.

изо

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

Здесь предохранитель означает не ограничение на

обозначение-

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

ременная

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

значением

непустую цепочку.

(с) Система процедур с иерархической структурой: рис. 122 '.

В вызове exch(u,v), фигурирующем в ord, процедура

exch

ис-

proc

0ri==(

int

u,v):

if u<v then

exch(ti,v)

else

skip

procedure

ord

(var

Integer);

begin

if и <v then

exch

(u, v)

else skip

end

proc

exch

э (var int a, b):

Tint

= а:

Й:=6;

procedure

exch

(var a, b:

integer);

var h :

integer;

begin

h:=a\

end

Рис.

122.

пользует параметры и, v процедуры ord;

skip

(соотв. skip) — это>

(пустая) процедура без параметров.

Вложение описаний процедур

друг

в друга, как и подчинение

подпрограмм

друг

другу,'—важное средство структурирования.

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

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

программ. (В противоположность этому в алголе-68 вложен-

ными

могут быть даже блоки.)

Описания

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

proc

pot=(var

reat

avar,

var

int

near)',

procedure

^o/fvar avar: rcaT; var

noar'.lnteger)

begin

if nvar>0

then

begin

(avar,

pror)

((t]r(avaf),

nvar—\)x

pot

(avar,

nvai)

end

else

skip

end

if H''ar>0

then

(avar, nvar)

:=i(avar\2,nvar-V);

pot

(avar,

nvar)

else

skip

Отметим, что оператор

poi(u,v)

означает в точности то же самое, что и (u,v) := (potz(u,v),Q)

(см.

3.3.3.1),

поскольку

pot(avar,

nvar) является просто (рекур-

Обозначение ord для первой из

двух

процедур на этом рисунке — от

order (порядок). — Прим.

перев.