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

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

2.1.

Основные

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

структуры

101

•операции

отрицания, конъюнкции и дизъюнкции переносятся

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

лительную

структуру

BIT.

В табл. 10 дан обзор операций, рассматриваемых в даль-

нейшем

как универсальные („булевы") операции логики вы-

сказываний.

2.1.3.7.

Переходы

между

сортами

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

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

ми

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

Это достигается отображением кольца целых чисел в изоморф-

ное

подкольцо вещественных чисел, которое (отображение)

остаётся необозначаемым. Такую вспомогательную опера-

цию,

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

зывают

неявным

обобщением'.

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

(real)int:,

соотв.

(real):integer,

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

(определения см. ниже в табл. И):

алголе-68

sign.

взятие знака,

entier.

взятие ближайшего снизу целого числа,

round,

округление,

паскале

trunc{.)

взятие ближайшего целого числа, заключённого

между

нулём и данным вещественным числом,

round{.)

округление, задаваемое формулой

trunc(x

+ 0.5) при *>0,

roundix)

= ,

' '

trunc(x

— 0.5) при

алголе-68

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

степень с целочисленным показателем

.f. с функциональным типом

(real,

int)real

О неявном обобщении (с функциональным типом

(char)string:)

идёт

речь (и

тогда,

когда в вычислительной

структуре

(V*, V) мы заменяем <.>

«а . (алгол-68); см. табл. 7.

Ещё одна (частично определённая) операция того же функционального

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

остаётся обычно необозначаемой,-

102 Гл. 2. Основные понятия программирования

Над

V (и

даже

над V") определено ' отображение в натураль-

ные

числа, называемое

перечислением,

нумерацией

или

счётом.

Оно

характеризуется тем, что не имеет „пробелов" и сохраняет

порядок

знаков (в

случае

V* — лексикографический порядок

слов),

а потому однозначно обратимо. Это отображение с типом

(char)int.,

соотв. (char):

integer,

обозначается в

алголе-68

через

abs, в паскале через ord(.).

Дальнейшие подробности об этих операциях, в частности

описание

обратных к ним операций

герг.,

соотв. chr(.), см. в

табл. 11

Другой важной операцией на V* со значениями в Z яв-

ляется операция

length(.)

нахождения длины слова (в

алголе-68

обозначаемая через upb.). Нет никакой необходимости вклю-

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

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

зовым операциям.

Это вер 10 и в отношении таких смешанных операций, как

«взятие t-го элемента слова а»

с функциональным типом

(string,

int)char:

(в

алголе-68

эта операция обозначается через

a[i])

или

«переход

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

а путём j-кратного применения операции

rest

(если i неотри-

цательно) или (—г)-кратного применения операции

lead

(если i неположительно)»

с функциональным типом

(string,

int)string:

(в

алголе-68

эта операция обозначается череза[(+ 1 :upba]

случае

положительных i и через а[\ :

(upbа)

+»'] в

случае

отрицательных)

или

«переход

от данного слова а к слову, совпадающему с а во

всех

элементах, за исключением t-ro, который равен х»

с функциональным типом

(string,

int,

char)

string:

(Грис ввёл для этой операции обозначение (a; i:x)).

Поскольку V является конечным или в крайнем

случае

счётным на-

бором знаков.

алголе-68

эта операция непосредственно имеется в распоряжении,

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

языка.

2.2.

Формулы 103

Вообще можно сказать,

что

выбор операций

в качестве при-

митивных

— это до

известной степени дело вкуса. Этот вопрос

надо

каждом отдельном

случае

решать, исходя

из

соображе-

ний

конкретной целесообразности,

также

и из

соображений

ма-

шинной

реализации

(см. гл. 4 и 6).

2.1.3.8*.

Составные объекты

Слова (последовательности знаков)

бинарные списки

яв-

ляются примерами

составных

объектов: они

составлены

из от-

дельных знаков.

таким

же

успехом можно рассматривать

по-

следовательности

или

бинарные списки, которые состоят

из

объектов

другого

сорта. Опережая общее изложение этого

во-

проса

в гл. 6, мы уже

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

будем

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

—

после-

довательности целых чисел, последовательности вещественных

чисел

последовательности значений истинности, соответст-

венно

битовые последовательности;

при

этом

табл.

надо

лишь

заменить

char на int, real, bool, bit.

Индикаторы этих

но-

вых множеств объектов образуются добавлением

sequ

перед

ин-

дикатором составных элементов:

sequ int, sequ real, sequ bool, sequ bit.

Таким

образом,

string

можно трактовать

как

сокращение

для

sequ char, a bits — как

сокращение

для sequ bit.

2.2.

Формулы

2.2.1.

Обозначения

параметров

„Der

Name

ist

durch

keine

Definition

wetter

zergliedern:

ist ein

Urzeichen."

Людвиг Витгенштейн

Алгоритмы

— это

описания общих методов; хотя фиксиро-

ванные

стандартные обозначения объектов

могут

в них

встре-

чаться,

их,

однако, недостаточно

для

такого описания: алго-

ритмы должны выполняться

над

меняющимися объектами

—

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

связи

этим требуются

обозначения

парамет-

ров. Такие обозначения можно выбирать произвольно

{свободно

выбираемые

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

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

(англ.:

identifier));

обычно

это

буква, комбинация букв

или

комбинация букв

цифр,

которая начинается буквой. (Чтобы обеспечить себе

пол-

* Изучение этого раздела можно отложить

до

3.3.3.2.

„Имя

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

это

первичный

знак."

{нем.)

—

Прим.

перев-

104 Гл. 2. Основные понятия программирования

ную свободу, стандартные обозначения (изображения) знаков и

последовательностей знаков заключают в кавычки.)

Примеры:

а, х,

mvar,

anton,

a\, хО.

Обозначения

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

обозначений

объектов, они по своей природе суть

имена,

кото-

рые можно присваивать объектам '. Изменяющаяся „загрузка"

имён

объектами

{интерпретация)

находит выражение также в

слове

переменная.

(Мы

будем

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

ния,

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

именами

алгола-68, с другой — с (программными) переменными

из

гл. 3).

"The

name

of the

song

called

'Haddocks

Eyes'"

"Oh,

that's

the

name

the

song,

is it?"

Alice

said,

trying

feel

interested.

"No,

you

don't

understand",

the

Knight

said,

looking

little

vexed.

"That's

what

the

name

called.

The

name

really

is 'The

Aged Aged

Man',"

"Then I

ought

have

said

'That's

what

the

song

called'?"

Alice

corrected

herself.

"No,

you

oughtn't:

that's

quite

another

thing!

The

song

called

'Ways and

Means': but

that's

only

what

it's

called,

you

know!"

"Well,

what

is the

song,

then?"

said

Alice,

who was by

this

time

completely

bewildered.

was

comming

that",

the

Knight

said.

"The

song

really

is 'A

sitting

On A

Gate':

and the

tune's

my own

invention."

Льюис Кэррол (Чарлз Лютвидж Доджсон

(1832—1898),

английский математик)

'Through the Looking-Glass', Ch. VIII.

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

изображениями и обозначениями. Формально изображение также является

обозначением некоторого значения. Разница состоит в том, что обозначение

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

уста-

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

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

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

или

pi, но иметь только одно изображение для него с помощью десятичных

чисел:

3.1415926...

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

жения.

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

эксплуатации зданий, устанавливающего внизу подъезда почтовые ящик»

для жильцов. Как физические экземпляры ящики

могут,

например, отли-

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

„изо-

бражение" ящика, т. е. обозначение, исчерпывающе характеризующее дан-

ный

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

жильцу, ни почтальону. Повесив их на стенке, сотрудник напишет краской

на

них номера квартир (обозначения-идентификаторы), которые и

будут

фактически

„работать" при доставке корреспонденции. — Прим. ред.

— Заглавие этой песни называется „Пуговки для сюртуков".

— Вы хотите сказать — песня так называется? — спросила Алиса, ста-

раясь показать, что песня её очень интересует.

— Нет, ты не понимаешь, — ответил нетерпеливо Рыцарь. — Это загла-

2.2. Формулы

105

2.2.2.

Формулы

формуляры

2.2.2.1. Построение формул

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

операции

^(композиция

операций), например:

gcd(gcd(G0,24),

15),

(

+1)Х(4-1),

first(rest(rerst("ABCD"))),

("H")

rest("MAUS");

них могут входить

обозначения параметров, скажем:

gcd(gcd(a,b),c),

(«+1)X(«-1),

first(rest(rest(a))),

(х)

rest

(а).

Само

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

операций

должны быть согласованы между собой:

вырабатывае-

мый

результат

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

раз

того сорта, который требуется на месте замены

формуле, куда

она

подставляется. Итак:

Формула

— это

либо

обозначение

параметра,

либо

стандартное

обозначение

для

фиксированного

объекта

(постоянная,

константа)

либо

символ

операции

формулами

качестве

операндов

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

этим

символом

операция

называется

доминирую-

щей

(или

определяющей)

операцией

формулы)

— это

есть

собственно

формула

(„настоящая"

формула).

При

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

скобки:

((а

Ь)

+ с) + d,

((t

Xu)Xv)Xw,

a + (b + (c +

d)),

tX(uX(vX

w)).

еие так называется.

песня называется „Древний старичок".

— Это

песни такое заглавие? — переспросила Алиса.

—

Да

нет! Заглавие совсем другое.

„С

горем пополам"!

Но это она

только так называется!

—

песня это какая? — спросила Алиса

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

—

как

раз

собирался тебе

об

этом сказать. „Сидящий

на

столбе"!

Вот какая это песня! Музыка собственного изобретения!"

(Перевод Н. Демуровой („Сквозь зеркало

что там увидела Алиса", Изд-во

литературы

на

иностранных языках, София, 1967).) ...„Алиса

Зазеркалья",

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

перев.

паскале

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

(с

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

для объектов, обладающих стан-

дартными обозначениями,

106

Группа

Гл. 2. Основные

понятия

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

Приоритеты в алголе-68

Одноместные

операции

Таблица If

Символ

операции

—

sign

entier

round

abs

герг

odd

Операнд

int

real

int

real

Int

real

char

bool

int

bool

bit

bits

Результат

int

real

Int

int

real

int

char

bool

bit

bits

Примечания

Перемена знака

(

—1 для

отрицательных

с = < 1 для

положительных

0 для а = 0

даёт

ближайшее снизу целое число

(entier

(—0.5) = —1)

округляет

до

ближайшего целого

числа

(round 0.5 не

определено!)

даёт

абсолютную величину

под-

ряд по

порядку

false |-> 0, true \-y 1

обращение операции

abs,

опреде-

лённой

на char (для

отрицатель-

ных

а не

определено)

Г true для

нечётных

\ false для

чётных

| отрицание

поэлементное отрицание

Двуместные

операции

Груп-

па

Символ

операции

Левый

операнд

Int

real

bits

Правый

операнд

int

Результат

int

real

bits

Примечание

c = a

для 6^0

c = a

сдвиг

а на b

позиций влево

при

Ь > 0, на —b

позиции

вправо

при b < 0 с

запол-

нением

2.2. Формулы 107

Таблица

(продолжение)

Груп-

па

Символ

операции

div

mod

—

Левый

операнд

int

real

int

real

int

real

string

int

real

char

string

int

real

char

string

bool

bit

bits

int

real

char

string

bool

bit

bits

bool

bit

bits

bool

bit

bits

Правый

операнд

int

real

int

real

int

real

string

int

real

char

string

int

real

char

string

bool

bit

bits

Int

real

char

string

bool

bit

bits

bool

bit

bits

bool

bit

bits

Результат

int

real

int

real

int

real

string

bool

boo!

bool

bit

bits

bool

bit

bits

Примечание

умножение

умножение,

де

ение

(деление

на 0

исключено)

результат

остаток

при це-

лочисленном делении

(деление

на 0

исключено)

вычитание

сложение

конкатенация

> в

обычном смысле

смысле лексикографиче-

ского порядка

над

алфави-

том объектов вида char

обычном смысле

смысле лексикографиче-

ского порядка

над

алфави-

том

об

ектов вида char

^ : с =

true, если

(д V 6) =

обычном смысле

\ конъюнкция

поэлементная

конъюнкция

дизъюнкция

поэлементная

дизъюнкция

108

Гл.

Основные понятия программирования

случае

ассоциативных операций

эти

скобки

могут

быть

опу-

щены:

+ b + c + d,

tXuXvXw.

Строго говоря, речь идёт

этом

случае

многоместных

опе-

рациях

.Х-Х-Х-,

которые

по

желанию можно

«читать»

слева направо либо справа

налево,

т. е.

представлять

тем или

иным образом

помощью

по-

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

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

нельзя:

—

(Ь

— с),

u/(v/w).

В арифметике издавна

для

борьбы

со

скобками применяют

неявное

правило

старшинства:

инфиксные символы

для

умноже-

Таблица

Приоритеты

паскале

Порядковый

номер

Операции

not

1 dlv mod and

— or

Ф < < > >

ния

деления „связывают" сильнее,

чем

инфиксные символы

для

сложения

вычитания.

Развивая

эту

идею, символы двуместных арифметических

операций,

операций сравнения

булевых

операций разбивают

на

несколько групп

по их

„рангу", скажем

алголе-68

— на де-

сять групп (табл.

11), в

паскале—на

три

группы (табл.

12).

Эти определения имеют много общего

— и там и тут (а —

Ь)

^х

можно сократить

до а — b ^ х, —

однако

целом

они

между

собой несравнимы;

других

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

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

на

этот

счёт

до сих пор нет, да,

пожалуй,

он и не

нужен.

Между префиксными символами

для

одноместных операций

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

почтения;

алголе-68

все

префиксные символы (группа

10 в

табл.

11)

имеют приоритет перед всеми инфиксными,

паскале

знак

отрицания

имеет приоритет перед знаком конъюнкции

Л, знак же—(обращение знака) приоритета перед

ним не

2.2. Формулы

109

имеет'. Несмотря

на

наличие правил старшинства, стоит

(и не

только новичкам!)

при

помощи „лишних" скобок чётко выра-

жать свои „намерения"; формулы

X 3)< (4 X 5) Л (2 X 2 =

5),

(-3) f 2 + (-4) f 2,

явно

легче

читаются,

чем

соответственно (алгол-68)

7ХЗ<4Х5Л2Х2

= 5, -3 f 2 +-4 f 2, ЗХ-1.

В паскале

же

писать, например,

* 3 < 4 * 5) and (2 X 2 = 5) или

(т

> 0) and

> 0)

просто требуется!

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

можно

не

только опускать скобки,

но и

добавлять сколько

угод-

но

„лишних" скобок,

как,

скажем,

формуле (ЗХ((—1)))

(в

алголе-68

паскале это,

во

всяком случае, допустимо).

Формулы, которые „ведут"

в В

и,

стало быть, результатом

имеют значения истинности

{булевы

формулы),

называются

высказываниями;

в них

используются

предикаты.

Высказываниями

(с

параметрами подходящего сорта)

яв-

ляются, например

^ Ь,

ЛЬ <: с

(часто сокращается

до a ^.b ^ с).

(Всегда истинные высказывания вроде

aVia

или 1 р V (р A д) V "I q

называются

тавтологиями.)

2.2.2.2.

Формуляры

Формулам соответствуют

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

есте-

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

для

проведения вычисле-

ний

(вычислительные)

формуляры

(„расчётные бланки"),

на ко-

торых

проводятся соответствующие

вычисления

(„обработка",

„отработка" формулы). Типичным примером

из

повседневной

жизни

служат

формуляры, которые применяются

учреждениях,

например

формуляр

для

расчёта подоходного налога

(рис. 45).

Более сложные примеры можно найти

инженерных науках.

На

рис.

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

Цузе пример

из

статики

строительных сооружений (рис.

46).

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

математическим обычаем писать—(—1)

[а не

—1,

—

Изд.

ред.],

понимая—.

как

сокращённую запись

для 0—..

113

Гл. 2. Основные понятия программирования

Остаток

.муж

600

480

жена

600

480

.муж

жена

Сулша доходов

а.

Итого

•муж

жена

стрвка

Рис.

45 Фрагмент формуляра для расчёта подоходного налога.

1. Доходы от занятий сельским хозяйством и лесным хозяйством

2. Доходы от занятий ремеслом

3. Доходы от независимой работы

4. Доходы от работы на предприятии

а Полная заработная плата

b Необлагаемая налогам часть доходов от социального обеспе-

чения

(40 %, но не больше

4800

марок на каждого из супру-

гов)

Необлагаемая налогом часть денежного подарка от предприни-

мателя по случаю рождества

d Необлагаемая/ налогом часть заработной платы

е Расходы на рекламу (максимум на общую сумму 564 марки)

б. Доходы от капитала

а Сумма доходов

b Расходы на рекламу (максимум на общую сумму 100 марок,

на

супружескую пару 200 марок)