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

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

3.1.

Предложения

общего

вида

171

как

множества переменных памяти. Родственное понятие про-

граммной

переменной

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

хода

будет

играть ключевую роль в этой главе. Естественное

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

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

граммы к понятию

процедуры.

Машинам

фоннеймановского типа свойственны линейный по-

рядок

на всём множестве переменных памяти (линейная память)

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

хода

вычислений, кото-

рая

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

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

прин-

ципом.

«La

plus

belle

ruse

Dlable

est de

nous

persuader

qu'il

n'existe

pas.»

Бодлер

3.1. Предложения общего вида

В разделе 2.5.1 формулы, которым предшествуют подчинён-

ные

им подпрограммы, были названы предложениями. Теперь

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

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

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

2.2.2.4.

3.1.1.

Описания

промежуточных

результатов

Для трёх сторон а, Ь, с треугольника наряду с неравенства-

ми

а ^ 0, b ^ 0, с ^ 0 должно выполняться условие (неравен-

ство треугольника)

Ь + с^а Л с + a^fb Л а + b^c.

Проверка

выполнения этого условия

требует

трёх сложений (и

трёх сравнений). Если же преобразовать его к виду

(а + Ь +

с)/2>а

Л (а + Ь + с)/2>Ь Л (а + b + с)/2>с,

то можно обойтись двумя сложениями и одним делением по-

полам,

ибо достаточно

один

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

чающееся подвыражение (а + b -\- с)

12.

В формулах, которые

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

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

' „Самая коварная уловка дьявола состоит в том, чтобы убедить нас,

будто

его не существует". — Прим.

перев.

Фактически неравенства aJSsO, 6^0 и с^О вытекают из неравен-

ства треугольника — Прим.

перев.

172

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

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

ния

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

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

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

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

fac

then\else'

if /~7fi

Рис.

84. Формуляр с сетевой структурой для функции fac.

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

ние,

как правило, имеет место для параметров подпрограмм:

посмотрите, например, на приведённые в 2.3.2 формуляры для

функции

fac и

других

функций и сравните их с рис. 84. В на-

шем примере желаемого эффекта можно достичь, если ввести

подпрограмму

funct p s

(real

с,

bool:

function

{a,

b, c, s: real):

Boolean;

begin

p•xfs'e.a)

and (s>b) and (s>c)

end

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

ным

{а + Ь + с)/2: '

funct

istnangks(tea\

a,b,с)

bool:

function

istriangle(a,

b, c,:

real):

Boolean;

begin

istriangk

(a,

b, c, {a + b+c)/2)

end

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

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

один

раз) до исполнения (строгой!) подпрограммы.

Ниже

istriangle

— от triangle (треугольник). — Прим.

перев.

3.1. Предложения общего вида

173

На

рис. 85 слева изображен формуляр, соответствующий

исходной формуле, а справа — его вариант с вспомогательной

подпрограммой р.

а Ь

а Ь с

Рис.

85. Формуляр для формулы с общими подвыражениями и выделение

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

Используя подчинение подпрограмм и удаляя неизменные

параметры, подпрограмму

istriangle

можно записать короче:

funct

istriangle=(real

bool:

rfunct/?=(real.?)

bool:

p((a+b+c)/2)

function

istriangle

(a,

b. с:

real):

Boolean

function

p (s:

real):

Boolean

;

bpgin

(s&a) and {s^b) and (v&f)

end;

begin

triangle

•<=

p ((a

b+c)/2)

end

3.1.1.1.

Упрощённая

нотация

Другой способ действий, более предпочтительный с точки

зрения

простоты нотации (хотя для машины обработки форму-

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

ввести s как обозначение промежуточного результата. При этом

нужно

будет

также указать тот тип, к которому относится s.

алголе-68

для этого имеется следующая нотация ' (где снова

В стандартном

алголе-68

вместо символа = нужно писать

знак

равен-

ства. Мы используем здесь =, чтобы исключить возможность путаницы с

универсальной операцией проверки равенства.

174

Гл. 3.

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

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

языки

используются скобки-уголки, а точку с запятой

следует

считать

как

„внутри" или „в"):

Ггеа1

s = (а + Ь + с)/2;

s>aAs>&

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

будем

называть

описанием

промежуточного

(вспомогательного)

результата

или

описанием

объекта.

На

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

структурой для исходной формулы (с внесённым в него обозна-

Ъ с а Ь с и Ъ с

а Ь с

общее

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

описание

промежуточного

результата

перехоЭ

сети

РИС.

86.

Структурирование

формуляра

посредством

описания

промежуточ-

ного

результата

(описания

объекта).

чением s для общего подвыражения) к формуляру с развет-

влённым

потоком данных. В результате мы получаем уже не

дерево, а всего лишь

сеть,

т. е. ацикличный ориентированный

граф.

Полученная

описанным образом „формула" также

будет

счи-

таться предложением; тем самым она

будет

формулой в неко-

тором более общем смысле. Благодаря этому оказывается воз-

можным записать наше условие (неравенство треугольника)

для

невырожденного

треугольника как обобщённую формулу

а>0Л6>0Лс>0Л

[real

s = (a + b +

c)/2;

s>aAs>bAs>c].

Итак,

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

funct

istriangle&=

(real

a,b,c)

bool:

[real

s^(a-\- b + c)/2; s^a A s^b Л s^cj

Условие а>0Л6>0Лс>0 является следствием условия

freal s Ез (а + 6 + с) /2;

s>a/\s>bAs>c]

(см. подстрочное примеча-

ние

в начале раздела 3.1.1). — Прим перев.

3.1. Предложения общего вида 175

funct

istrianglel

= (real

a,b,c)

bool:

а>0ЛЬ>0Лс>0Л

freal s si

-f- 6 + c)/2; s>aAs>6As>cJ.

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

формуле Герона с помощью подпрограммы

funct

herons

(real

a,b,c со

istriangle(a,b,c)

со)

real:

s - (a + b + c)/2;

sqrt(s

X(s - a)X(s - b)X(s - c))\.

Описания

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

степенно.

Так, формула

[real

sls=aOXx

+ al;

freal

s2e=sl X x + a2\

[real s3 = s2 X x + a3; S3XJC + a4JJJ

даёт

тот же

результат,

что и формула четырёхчленной схемы

Горнера (см.

2.2.2.4),

а ход вычислений у этих

двух

формул

совпадает. Как и в

случае

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

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

края

скобках и писать короче

[real

sl™aOX*

+ al".

real s2==sl X x + a2\

real s3 = s2 X x + a3; s3 X x + a4J.

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

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

быть попарно различными. Они снова оказываются связанными:

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

лучится эквивалентный алгоритм. Областью связывания обозна-

чения

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

чале которого находится соответствующее описание. Это в точ-

ности

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

граммы (как, например, р в

istriangle),

которую можно было бы

ввести взамен'. Промежуточные результаты называются ло-

кальными

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

Область действия всякого обозначения совпадает с областью

связывания

этого обозначения, уменьшенной, если надо, на

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

вложенном уровне и „экранирующего" используемое на внеш-

нем

уровне. Примером может служить предложение

[real ha= [real

h^aXa;

ft X AJ; h X AJ,

Эту взаимосвязь обнаружил Ландин (1966 г.).

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

представляющее собой запись упрощённого вычисления выра-

жения

((а X а) X (а X а)) X ((а X а) X (а X а)).

Польза

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

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

одинаковых подвыражений, очевидна'. Часто удаётся, как

выше,

подходящим образом преобразовать формулу. Например,

для вычисления логарифмической производной р'(х)/р(х) по-

линома

р(х) можно получить „двухрядную

схему

Горнера"; для

нашего примера это

будет

[real si

a*aOX*

+ al;

reaW2

= aO X х + si;

real s2 = sl X * + a2; real /3 s= t2 X x + s2;

real s3 = s2 X x + a3; real

/4s/3X^

+ s3;

/4/(s3 X ^ + a4)J.

3.1.1.2.

Обозначения промежуточных

результатов

в рекурсивных подпрограммах

Обозначения

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

могут

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

более простой линейной рекурсии. Проиллюстрируем это на

примере ханойских

башен.

Это название древней восточной

игры используют также как название определённого класса

проблем с той же структурой.

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

щего диаметра. И пусть диски в соответствии с их размерами

сложены в форме башни, так что диск наибольшего диаметра

лежит в самом низу. Тогда задача состоит в том, чтобы пере-

ложить башню с данного места (место 1) на

другое

(место 2).

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

нашем

распоряжении ещё одно место (место 3), куда можно скла-

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

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

одной из башен. В любой момент времени на каждом из трёх

мест диск большего диаметра должен лежать ниже диска мень-

шего диаметра.

Задача кажется весьма трудной, однако рекурсивное реше-

ние

очевидно. Обозначим самый нижний диск нашей башни

буквой L Переместим остальную часть башни, нижний диск

которой обозначим предшественником буквы i, с исходного

места 1 на свободное место 3; далее переместим обозначенный

буквой i диск на место 2 и затем перемещённую ранее часть

При этом в

случае

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

можных

результатов

иногда

сужается.

3.1. Предложения общего вида 177

башни

переместим с места 3 на тот диск, что уже находится

на

месте 2.

Итак,

подпрограмма, результатом которой будет

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

дисков,

запишется следующим образом '•

funct

loh

s (char f) string:

if i>"A"

then

toh(jpred(i))

toh(pred(t))

0 Ы"А'

then

{/> fi

function

ioh(i:

char):

siring

begin

\fi>'A'

then

toh

&conc(ioh(pred(j)),

prefix{l,toh(pred(M)

i-'A'

then

to/i

•*

prefix

(i,

empty)

end

Вызов,

скажем, toh('D') приведёт сначала к

toh(C) +

('£>')

+ /оА('С),

затем к

tohi'B')

+ (С) +

/оА('В')

+ (D') +

/оА('В')

+ (С) +

и,

наконец, к

ЛЛЛЛ

Порождаемая

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

вида

^ + <О + А. (Она задаёт также построение циклического одно-

-i О -" О 1

Рис.

87. Построение одношагового двоичного кода.

шагового n-разрядного двоичного кода, содержащего 2" эле-

ментов,

см. рис. 87.)

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

приведенной

формулировки подпрограммы toh можно получить

Ниже toh — от английского названия ханойских башен:

towers

of Ha-

noi — Прим.

nepee.

Используемая ниже функция

pred

определяется так:

funct

pred

e (char n)char :

repr(abs n — 1)

function

pred(n

char)

char;

begin

pred

chr(ord(n)

— 1)

end

Палиндром — слово, читающееся одинаково слева направо и справа

налево. — Прим.

перев.

178

Гл. 3.

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

существенно более эффективную формулировку

net

loh

(char

if/>

then

0/='

then

'A"

string

h +

(/)+/>

'A!

<?>

string:

loh

(pred

(i))\

function /ой

(/!

char)

string;

begin

\U>'A'

then begin

siring

/c/i

(pred(i));

/o/i

conc(h,prejixll,h))

end

i =

'A'

then

(оЛ

prefix

(i,

empty)

end

которой каскадная рекурсия замещена линейной '.

Заметим,

что i-e воплощение toh^ функции toh содержит,,

конечно

же, свой собственный промежуточный результат /i<">>

При

работе с машиной обработки формуляров настоящие вы-

числения

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

будет

готов последний

формуляр и для значения функции to№

(при аргументе 'Л')

получится результат 'Л'; теперь продолжается выполнение „по-

висшей"

операции

string

h =з toh (pred(i)), т. е. вводится обо-

значение

ft'"-

для 'А' и вычисляется результат 'ABA' примене-

ния

функции

toh

к аргументу 'В'; затем вводится обозначе-

ние

г1

(п

г)

для 'ABA' и вычисляется результат

'АВАСАВА'

при-

менения

функции

toh

{

-"~

к аргументу 'С, и т. д.

Наконец,

отсюда уже нетрудно вывести соответствующий

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

(ниже

succ

— обращение функции

pred):

funct

loh и (char ()

string:

Ffunct

(oa(cher/,

string

Л)

strinq:

!fi<r

then

io(succ(l),h+<J)+h)

to С

A",

function

loh

(I;

char):

siring;

function

lo (i;

char;

Л: siring):

siring

begin

if i<t

then

-к

to(wcc(i),

concQi,

prefix{i,

Л)))

else

to«conc(h,preflx{f,h))

end;

begin

ioh<zto{'A', empty)

end

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

обозначений промежуточных результатов

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

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

Относительно паскалевской версии

см.

также

3.1.1.4.

S.I.

Предложения общего

вида

179

степени числа:

funct

pow8

ss (real a)

real:

[real Al = a t 2; real hi = Al f 2; A2 f 2J.

Отметим, что эта „детализованная" форма является сокра-

щенной

записью для системы

funct

powS

s= (real a) real : pl{a\ 2)

funct pi = (real Al) real:

p2(Al

f 2)

funct p2 ss (real A2) real: A2 f 2,

или,

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

funct

pow8

s= (real a) real:

ffunct p/ = (real h\) real:

ffunct pi = (real A2) real: hi \ 2;

/»2(A1

t 2) J;

pHa t 2) 1.

Подстановка даст, разумеется,

funct

pow8

= (real a) real: ((a \ 2) f 2) f 2.

3.1.1.3.

Линеаризация хода

вычислений

Для совместных формул (параллельно-последовательных)

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

Рис.

88.

Формуляры, получающиеся

результате декомпозиции

линеари-

зации.

ния

на предложения. Так, например, из формулы

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

разбиением на предложения можно получить формулу

Ггеа1

А1

(Ь

X 2 + а) X d;

real

Л2 = (а X 2 + 6) X с; Л1 + A2J,

которая

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

ние

„слева направо" (см. рис. 75) и уже не допускает вычисле-

ния

„изнутри наружу". Точка с запятой становится знаком,

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

На

рис. 88 изображены соответствующие записи вычисли-

тельных формуляров.

3.1.1.4.

Замечание относительно паскаля

Описания

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

ле-68

описаниями

тождества.

Строго говоря, в паскале они от-

сутствуют;

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

условных выражений. Однако некоторые версии паскаля, как,

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

тов, например:

function

istriangle(a,b,c

: real):

Boolean;

begin

s :

real

= (a + b + c)/2;

istriangle

-<=(s^a) and (5 ^ b) and (s ^ c)

end.

Мы

воспользовались этим в разделе

3.1.1.2

для описания

функции

toh.

3.1.2.

Групповые

описания

промежуточных

результатов

Подобно

тому как это делалось в 3.1.1, с помощью одной

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

вычисления

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

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

формулы

(a f 2 +

f 2) X

((a

Ь)/(а

Ь))

+ (a + b)X(a-b)

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

funct

p =

(real

a,b,s,d)

real:

(a f 2 + b f 2) X ln(s/d) + sX d

вызов

р(а,Ь,а-{-Ь,а

— b).

Более коротко это записывается так:

[(real s, real d) ^ (a + b,a - b); (a \ 2 + b\ 2) X ln(s/d) + 5 X d\,

или,

ещё короче,

f(real s,d) = (а + b,a- b); (a \ 2 + b f 2) X ln(s/d) + sXd\