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

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

1.3. БАЗОВЫЕ КОНСТРУКЦИИ ЯЗЫКА

unit M // имя модуля program

…

interface uses M; // объявление

// подключения модуля

… // какие-то описания

// здесь уже можно

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

// модуля M

… // объявление того, что

// модуль предоставляет

// для внешнего

// использования

procedure PM(a : real);

… // вставка недоступной

// части модуля

begin

// вставка инициализации

// модуля

implementation

… // описание того, что

// • нужно для реали-

// зации модуля,

// • объявлено для

// внешнего исполь-

// зования (реали-

// зация процедур и

// функций)

procedure PM(a : real);

begin … end;

…

… // действия программы

PM(7.4); // вызов процеду-

// ры из модуля

… // действия программы

begin

… // действия, которые

// нужно выполнить до

// использования предо-

// ставляемых средств

// вставка завершающих

// действий

finalization

… // действия, которые

// нужно выполнить после

// использования предо-

// ставляемых средств

end. // конец программы

end. // конец описания модуля

Рис. 1.4. Схема подключения модуля в языках

Turbo Pascal

Object Pascal

ГЛАВА 1. ПОНЯТИЯ

1. В программе 1.3.2 описание

int X, Y, X23;

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

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

граммы.

2. Если поставить описания после строки

int main (void)

как сделано в программе 1.3.3, то будет запрещено использование

вне функции

main

, о которой говорится ниже.

3. Как показано в программе 1.3.3, можно обойтись без описания пере-

менной

X23

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

менную для хранения

X * X

(см. 4) в § 1.3.5.

различают объявление имени (предварительное упоминание)и собствен-

но описание (фиксация смысла и содержания описываемого имени). С пред-

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

шется программа в стиле объектно-ориентированного программирования,со-

стоящая из многих модулей. В простых программах обычно достаточно соб-

ственно описаний.

Описание переменных — это пассивная часть программы. Сами по се-

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

Неймановской памяти, в которой хранятся данные. В программе представле-

но еще одно описание, определяющее требуемые вычисления. Это активная

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

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

1.3.5. Действия

1. Заголовок функции. Выражение

int main (void)

определяет функцию

main

, которая должна вычислить целочисленное

значение (описатель

int

). Заданное в скобках служебное слово

void

ука-

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

метров. Компилятор не позволяет вызывать такую функцию с параме-

трами. Для языка

принято, что любая программа должна содержать

функцию

main

. Выполнение этой функции начинает выполнение про-

граммы.

1.3. БАЗОВЫЕ КОНСТРУКЦИИ ЯЗЫКА

2. Знаки группировки { и }. Строки с фигурными скобками обрамляют

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

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

main

3. Вызов функции ввода. Чтение значения переменной осуществляется с

помощью оператора

scanf ( "%d", &X );

которая задает формат ввода

и переменную

, получающую значе-

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

"&"

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

ме

scanf

используется не значение

, а его адрес, чтобы указать, куда

должно помещаться читаемое значение.

4. Тело функции. Следующие строки

X23 = X * X;

X23 = X23 * X;

Y = X23 * X23 * X;

или

Y = X * X * X;

Y = Y * Y * X;

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

чений переменным. Здесь хорошо видно, что от порядка операторов

зависит результат.

5. Вызов функции вывода. Строка

printf ("\n7 power of %d is %d\n", X, Y);

определяет формат вывода

\n7 power of %d is %d\n

и переменные

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

ждений

"\n"

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

6. Завершение. Наконец, строка

return 0;

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

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

нормально с искомым результатом (с кодом ответа 0).

***

ГЛАВА 1. ПОНЯТИЯ

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

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

Ответы на эти и другие вопросы поможет дать разбор действий и изучение

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

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

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

туре текста программы, что записанный алгоритм — это не совсем то, что

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

программистской задачи.

§ 1.4. СТРУКТУРА ВЫЧИСЛЕНИЙ И СТРУКТУРА ТЕКСТА ПРОГРАММЫ

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

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

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

мы 1.3.3 представлена на рис. 1.5, а структура ее текста — на рис. 1.6. Из

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

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

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

свободна в этом отношении.

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

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

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

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

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

а какие — нет. С другой стороны, запись в программе часто допускает от-

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

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

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

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

1.4.1. Последовательное, параллельное и

совместное исполнение

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

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

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

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

1.4. ВЫЧИСЛЕНИЯ И ТЕКСТ

Чтение X

Выделение памяти для X

Активизация main

Действия окружения

Выделение памяти для Y

В любом порядке

Y = X * X * X;

В любом порядке

Вывод X и Y

Завершение вычислений

Y = Y * Y * X;

Рис. 1.5. Структура вычислений программы

ГЛАВА 1. ПОНЯТИЯ

#include <stdio.h>

int main (void)

{

int X;

int Y;

scanf( “%d”, &X );

Y = X * X * X;

Y = Y * Y * X;

printf (“\n7 power of %d is %d\n”, X, Y );

return 0;

}

Программа

Глобальные

описания

Подключение

внешних текстов

Объявление

главной функции

Подключение

внешних текстов

Заголовок Блок

Описания Тело Конец блокаНачало блока

Описания

Оператор Операторы

Оператор ввода Оператор Операторы

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

Оператор Операторы

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

Оператор Операторы

Оператор вывода

Оператор

Оператор возврата

Рис. 1.6. Структура текста программы 1.3.3

1.4. ВЫЧИСЛЕНИЯ И ТЕКСТ

полнения.

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

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

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

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

ленных

";"

, в языках

Pascal

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

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

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

по-

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

Алголе-68

Concurrent Pascal

и других

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

скобками, например,

parbegin

parend

; обрамляемые ими операторы могут

быть выполнены параллельно).

Даже если на машине всего один процессор, указание на параллельность

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

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

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

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

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

тратит на ожидание завершения операции ввода-вывода. Например, при та-

ком исполнении отрезок программы

printf("Первый результат: %d, %d\n", X, Y);

Оператор 1;

...

Oператор n;

printf("Второй результат: %d , %d\n", Z, V);

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

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

Если они не успеют выполниться, пока печатается первая строка, то все в

порядке, если успеют, то перед печатью второй строки придется подождать,

пока допечатается первая.

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

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

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

В частности,

C++

Java

Object Pascal Delphi

имеют операторы порождения

процессов, подобные

thread(run_this,"Новый процесс")

ГЛАВА 1. ПОНЯТИЯ

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

но с основным текстом программы (и правильно делают!).

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

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

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

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

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

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

раторе

x = a*b+c*d

a, b, c, d

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

того из подвыражений

a*b, c*d

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

Если

a, b, c, d

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

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

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

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

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

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

общем случае невозможно. И поэтому в руководствах по языкам можно часто

увидеть загадочную фразу «побочный эффект игнорируется», смысл которой

соответствует тому, что в данном месте могут быть элементы совместного

вычисления.

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

дена лишь в

Алголе 68

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

“,”

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

“;”

x := 1, y := 2, z := 3;

a[x] := b[y], d[z] := e[x];

(1.1)

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

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

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

нения. В приведенном выше фрагменте совершенно безразлично, в каком

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

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

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

Если изучить стандарт языка

Java

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

слабое совместное исполнение (см. ниже) в чистом виде.

1.4. ВЫЧИСЛЕНИЯ И ТЕКСТ

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

раторов в программе алгоритмически неразрешима. Хотя ее можно решать в

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

мы помечать, какие действия независимы.

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

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

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

кает в той форме условного оператора, которую предложил Э. Дейкстра [30]

и интенсивно использовал Д. Грис

[27]:

Охраняемые команды:

→ S

. . . ,

→ S

ﬁ

(1.2)

Этот оператор исполняется следующим образом. Совместно вычисляются

все условия A

,пока одно из них,например,A

,не окажется истинным.Далее

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

тор S

. Если истинных условий не оказалось вообще, оператор (1.2) выдает

ошибку.

Например, вычисление минимума двух чисел в форме Дейкстры

выглядит, как показано ниже:

x 6 y → z := x,

y 6 x → z := y

ﬁ

return

(z);

(1.3)

Если наши данные не являются числами и лишь предупорядочены (см.,напр.[34]),

то не определено, какое значение получит z в итоге, но это нам и безразлично.

К сожалению, в общераспространенных системах таких средств не предусмотрено.

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

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

реализованы на практике: с

Алголом-68

Это более технологично, чем соглашение об эквивалентности пустому оператору любого

непредусмотренного случая.

ГЛАВА 1. ПОНЯТИЯ

Даже если мы рассматриваем обычные числа, то в случае x = y мы можем

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

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

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

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

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

нормированы стандартом и, соответственно, не должны использоваться. Не

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

Pascal

запреще-

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

вычислено раньше. Ведь именно при программировании вычислений фор-

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

ния.

Исполнение следующего фрагмента программы иллюстрирует, что ис-

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

X := 1;

parbegin

X := X + 1;

Y := 5 + X;

parend;

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

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

первого из указанных операторов завершится ранее, чем начнется чтение X

во втором операторе, то Y получит значение 7, а в противном случае — 6.

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

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

1.4.2. Управление порядком вычислений

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

можно было создавать содержательные программы. Следующий пример ил-

люстрирует этот тезис. Пусть требуется написать программу для решения

квадратного уравнения

+ pX + q = 0.

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

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