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

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

245

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

сывающей некоторый процесс.Программа есть структурное объединение сво-

их составляющих: выражений, операторов и др. Но отношение “

быть соста-

вленным из

” — лишь формально-лингвистическая основа структуры про-

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

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

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

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

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

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

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

экземпляры объектов и т. д. Наконец, еще одним измерением, с которым при-

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

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

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

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

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

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

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

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

рархически соподчиненных и соединенных для выполнения процесса. В по-

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

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

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

ждаться.

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

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

для дальнейшей обработки. Самый наглядный пример — компилятор, кото-

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

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

рерабатывает данные. В этом примере текст на языке программирования —

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

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

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

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

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

ма. Это естественная идеализация вычислительного процесса, позволяющая

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

246

такие, кажущиеся экзотическими обычному программисту, случаи (напри-

мер,в

Рефал

PROLOG

LISP

),когда программа для обработки данных может

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

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

нейшей обработки. Этому подходу уделено внимание в соответствующем ме-

сте (см. § 13.1, 13.2), а в данной части сосредоточим внимание на структурах,

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

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

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

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

вень знаний и метода с уровня умений и композиций эмпирических рецеп-

тов.

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

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

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

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

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

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

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

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

ля структурного программирования.

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

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

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

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

принадлежащие другим стилям.

Так как выражения являются основным строительным материалом про-

грамм данного стиля, изложение начинается с них. Затем рассматриваются

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

программы, т. е. данными, потоками информации и призраками. Структура

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

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

ние без анализа этой структуры невозможно: в конце главы, посвященной

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

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

Глава 5

Выражения

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

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

батывают значения. Выражений в этом смысле слова нет лишь в некоторых

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

мер, в

Рефале

). Простейшими выражениями являются имена и литералы.

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

ке

((x++)*(++y)/(*z=>a**z=>b))>=3.0

(5.1)

являются выражениями.

Рассмотрим подробнее структуру выражений. При этом, как всегда, мы

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

туру. Первая из них описывает текстовое строение выражения, а вторая —

вычислительные аспекты.В обоих представлениях в качестве основного «стро-

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

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

язык

(точнее, соответствующее

подмножество языка

С++

). Переписы-

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

ких затруднений, но новых качеств изложению материала это бы не доба-

вило. Вместе с тем, семантика конструкций

и, скажем,

Pascal

’я различа-

ется, и это подчеркивается в пояснительном тексте. Для освоения материа-

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

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

, ко-

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

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

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

247

248

ГЛАВА 5. ВЫРАЖЕНИЯ

§ 5.1. ОПЕРАЦИИ

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

ством операций.

Определение 5.1.1. Операция — лексема языка, которая в абстрактно-син-

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

выра-

жения

V , что остальные составляющие V сами являются

выражениями

, на-

зываемыми ее операндами.

Среди операций различаются префиксные — стоящие в конкретно-син-

таксическом выражении перед операндами; постфиксные — стоящие после

своих операндов; и инфиксные — стоящие между операндами.

Конец определения 5.1.1.

Пример 5.1.2. В выражении (5.1) вхождение

x++

является постфиксом,

++y

— префиксом, из двух идущих подряд звездочек

первая звездочка

интерпретируется как инфикс, вторая — как префикс.

Конец примера 5.1.2.

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

ческой структуре выражения. Если же рассмотреть абстрактно-синтаксиче-

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

исчезают.

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

операции одноместны. Но в трансляторах и системах символьных преобра-

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

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

торые включают многоместные префиксы или многоместные постфиксы. В

таких представлениях все остальные типы операций исключаются. Если в

Оговорка «почти» связана с тем, что операции ++ и −− языков

Java

выполняются

по-разному в зависимости от того, применены они как префиксные или как постфиксные. В

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

после него. В сочетании с совместностью вычисления операндов ‘нормальных’ операций,

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

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

реализациями, и целиком оставлено на “добрую” волю оптимизаторов.

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

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

C/C++

нужно иметь в операторе лишь одно

присваивание.

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

не видны ни на входе, ни на выходе системы.

5.1. ОПЕРАЦИИ

249

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

ется польской записью, или прямой польской записью, если все операции —

постфиксы, то обратной (инверсной) польской записью.

Пример 5.1.3. Формула

(x + y)/(a ∗ b + 2) (5.2)

в польской записи выглядит как

/ + x y + ∗a b 2.

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

гументов польская запись всегда позволяет обойтись без скобок.Конечно,это

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

Конец примера 5.1.3.

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

ческое представление дерева вычислений выражения. Тем самым она макси-

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

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

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

прямое соответствие текстов программ их представлению в объектносм коде.

В частности, язык

АЛМО

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

ставления выражений.

В практически забытом сейчас языке

APL

где конкретно-синтаксиче-

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

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

гических формул, где в то время (20-е гг. XX века) еще не было груза традиций внешней

формы.

АЛМО

— русская попытка (1967 г.) создать то, чем затем стал язык

: язык высокого

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

АЛМО

до середины 80-х гг.

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

транслировались на

АЛМО

, а уже затем в машинные коды.

APL

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

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

XX в. В

APL

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

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

над элементами автоматически распространялись до операций над массивами; многие опе-

рации были совмещены с присваиваниями (оставшиеся в

рудименты этого, в частности,

упоминавшиеся выше ++ и−−) и т. п. В итоге

APL

породил одно из древнейших племен ха-

керов — совершенно непонятные однострочечники — писавших любую программу в виде

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

APL

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

250

ГЛАВА 5. ВЫРАЖЕНИЯ

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

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

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

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

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

ки.Например, выражение

A*B+C*D

понималось как математическая формула

(A ∗ B + C) ∗ D.

Простейшие операции практически во всех современных языках програм-

мирования имеют стандартное изображение. Это +, −, ∗, которые применя-

ются и для действительных, и для целых чисел, и интерпретируются едино-

образно.

Операцию деления стоит рассмотреть внимательнее. Интерпретация де-

ления для действительных и целых чисел в подавляющем большинстве язы-

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

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

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

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

для отрицательных чисел... тут может быть самое безумное решение. Кое-

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

Pascal

Алгол-68

) явно разделяется целочисленное

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

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

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

div

. Поэтому результаты вычислений операторов

x := a/b;

x := a div b;

(5.3)

где

x, a, b

— целые переменные, могут быть различны.

Аналогичный эффект можно получить и в языке

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

явном виде еще одно важное понятие современных языков.

x=ﬂoat(a)/ﬂoat(b);

x=a/b;

(5.4)

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

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

сел с действительным результатом. Затем этот результат переводится обратно

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

ной части.

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

5.1. ОПЕРАЦИИ

251

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

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

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

имеют синтаксическую форму

TYPE(<выражение>)

, берущую начало из

Ал-

гола-68

), либо неявными. Например, если у нас есть присваивание

d=x*n

;

где

—переменная типа

double

— типа

ﬂoat

— типа

int

, то сначала

целое

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

результат умножения — в действительное число двойной точности. Таким

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

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

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

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

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

лителя. В

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

, а в языке

Pascal

—

mod

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

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

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

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

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

форму и применяются стандартные функции exp и log. Существовали

даже

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

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

ственно, вычисление (−1) ∗∗n могло привести к ошибке. Этот пример пока-

зателен: стремление к универсализации не всегда благо. Так что возведением

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

лучше пользоваться лишь для целых чисел и для возведения положительных

действительных чисел в целую степень.

В языках

Pascal

от операции

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

Некоторые операции определяются лишь через конкретные машинные

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

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

тель либо делимое отрицательны.

А, может быть, существуют и сейчас.

Например, из стандарта языка

FORTRAN-90

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

0**0

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

252

ГЛАВА 5. ВЫРАЖЕНИЯ

представления операндов.Таковы,в частности,поразрядные логические опе-

рации в общераспространенных языках программирования. В языке

это

операции

. Для их понимания нужно помнить, что

рассчитан толь-

ко на такие машины, в которых целые числа (да и другие объекты) имеют

машинное представление в виде последовательности битов. Результат опе-

рации

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

левской конъюнкцией соответствующих разрядов операндов. Соответствен-

но,

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

— поразрядное отрицание (ин-

вертирование всех битов),

— поразрядное исключающее или.

Операции над машинным представлением особенно эффективны в тех

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

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

ичных разрядов.

Аналогичные операции в языке

Pascal

обозначаются

and, or, not, xor

Язык

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

нии символов операций. Один и тот же символ операций имеет абсолютно

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

Например,

как бинарная операция означает умножение, а как унарная —

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

как бинарная операция означает по-

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

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

бидная операция, как унарный

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

за неявного преобразования в другой тип.

В языках

C++

Ada

Алгол-68

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

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

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

тов нового типа. В

Алголе-68

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

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

§ 5.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ

Рассмотрение начнем с примера. Пусть требуется написать программу,

которая печатает «Да», если точка принадлежит области S, и «Нет» — в про-

тивном случае. Область S образована пересечением следующих «простых»

5.2. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ

253

областей (см. рис. 5.1, где данная область выделена штриховкой):

O1 = {(X, Y ) | 0 6 X 6 1} полоса шириной 1 над осью X;

O2 = {(X, Y ) | X 6 Y } полуплоскость под прямой Y = X;

O3 = {(X, Y ) | X2 + Y 2 6 4} Круг радиуса 2

с центром в начале координат.

Точка принадлежит области, если она принадлежит пересечению областей

O1, O2 и O3.

Таким образом, задачу можно свести к следующим действиям:

1. проверить принадлежность точки области O1;

2. если свойство выполняется, то проверить его для O2;

3. если опять свойство выполняется, то проверить его для O3;

4. напечатать «Да», если опять получится истина;

5. во всех остальных случаях печатать «Нет».

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

не зависит.

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

грамме. Типа данных «Точка» в языке

нет, следовательно, его надо моде-

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

чисел X и Y . Эти числа — декартовы координаты точки на плоскости. Пред-

ставление областей в программе — это задание соответствующих им опре-

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

области — условие соответствующего условного оператора.

Программа 5.2.1

Проверка принадлежности области

#include <stdio.h>

int main()

{

ﬂoat x, y;

printf( "Введите координаты в виде <число> <число>:");

scanf( "%f% %f", &x, &y );

if ( 0 <= x )

254

ГЛАВА 5. ВЫРАЖЕНИЯ

Y = 0

+ Y

= 4

Y = X

Y = 1

Рис. 5.1. Область плоскости