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

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

7.2. ПОТОКОВАЯ ОБРАБОТКА

325

Программа 7.2.9

program MN3(Input, Output);

const N = 15;

var A : array [1..N] of Integer;

X, L, i, j : Integer;

incl : Boolean;

begin

if not eof

then

begin

read (A[1]); L := 1;

while not eof do

begin

read ( X ); i := L; incl := False;

if (X > 0) and (X < 1000) then

repeat {

цикл поиска места вставки

A }

if A[i] < X {

нашли в

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

}

then begin {

будут сдвиг и завершение цикла

}

incl := True;

if L < N then

{ А

не заполнен, нужен сдвиг вправо:

}

begin for j := L downto i+1 do A[j+1] := A[j];

A[i] := X; L := L+1

end

else

{ А

заполнен, нужен сдвиг влево:

}

begin for j := 1 to i-1 do A[j] := A[j+1];

A[i] := X

end

else if A[i] = X

then incl := True

{

нашли элемент, равный

, цикл завершается

}

else A[i] > X

begin i := i + 1;

incl := i = 0

end

326

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

{

только при

i <> 0

}

{A[i] > X

цикл продолжается

}

until incl {

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

X }

end;

for i := 1 to L do write ( A[i] )

end

end.

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

7.2.4. Потоки и цикл for

Цикл

for

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

цикла и генерацию нового элемента. Дадим его конкретно-синтаксическую

структуру для языка

“

for

” “(” <инициализирующий оператор> <выражение-условие> “;” <вы-

ражение пересчета> “)”<оператор>

Такая структура оператора цикла исторически сложилась для достижения

сразу трех целей:

1. наглядности;

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

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

3. обогащения возможностей программирования: например, за счет воз-

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

for

цикл

while

становится избы-

точным в

C/C++

Оптимизационное назначение цикла

for

— это традиция, восходящая к

Algol

и даже к языку

FORTRAN

. В цикле

for

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

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

, можно явно вы-

делять так называемые параметры цикла — переменные, принимающие те

значения, при которых должны быть пройдены итерации. Переменные цикла

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

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

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

жать все множество, определенное в цикле, в том порядке (а это — отличие

от логики), как предписывает цикл.

7.2. ПОТОКОВАЯ ОБРАБОТКА

327

Например, во фрагменте

for ( i = 0; i < 100; i++ )

...

оператор,обозначенный многоточием, выполняется при i, равном 0,1, ...,99.

i —это параметр данного цикла. В других языках параметр цикла —понятие,

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

Pascal

for i:=0 to 99 do S

переменная

внутри

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

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

предупреждение. В языке

Алгол-68

цикл имеет еще более изощренную фор-

му:

for i from 0 to 99 while P<i> do S<i> od

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

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

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

ром и имеет областью действия лишь условие

и оператор

. Так что все

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

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

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

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

отпадает. Решение, принятое в языке

Ada

, синтаксически ближе к решению

Алгола-68

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

Pascal

Если переменная

будет размещена на быстром регистре, то цикл будет

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

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

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

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

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

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

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

ленными трансляторами.

Чтобы позволить транслятору осуществлять оптимизирующие преобра-

Эта услуга порою превращается в медвежью, поскольку автор программы может даже

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

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

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

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

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

ваться еще долго...

328

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

зования, в описания некоторых языков (

Алгол

Pascal

и др.) включают до-

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

for

не определено после естественного завершения, т. е. завершения из-за лож-

ности условия продолжения (в примере i < 100). Смысл указания становит-

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

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

конкретной вычислительной среде.

Пример 7.2.6. Оптимизация,цикл

for

и массивы.Рассмотрим фрагмент про-

граммы:

for ( int i = 1; i < 100; i++ )

a[i] = b[i] = i;

Путем анализа текста можно узнать, что этот цикл можно реализовать в ко-

дах процессора

Intel-80?86

следующим образом (в частности, организовав

обратный порядок итераций):

mov ecx,64h // инициализация i(register ecx) i = 99

c1: mov [b - ecx*4],ecx // запись i в b[i]

mov [a - ecx*4],ecx // запись i в a[i]

loop c1 // уменьшение ecx, goto, если не 0

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

код для данного фрагмента программы?

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

Само определение цикла

for

указывает на то, что эта конструкция отража-

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

элемента потока (см. табл. 7.16).

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

и большинства других языковых конструкций) могут использоваться в смы-

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

for

возможны

реализации иных схем (см., к примеру, использование

for (;;)

, которое обсу-

ждалось выше). Тем не менее, использование конструкций, специально при-

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

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

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

или, по крайней мере, приняли свои современные формы.

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

329

Схема Пример

ИНИЦИАЛИЗАЦИЯ, ВКЛЮЧА-

ЮЩАЯ ГЕНЕРАЦИЮ

for (<инициализирующий опера-

тор

пока ПОТОК НЕ ИСЧЕРПАН

цикл

<выражение-условие>;

ОБРАБОТКА ЭЛЕМЕНТА

Задается как часть <операто-

ра>, указанного

ниже

ГЕНЕРАЦИЯ ОЧЕРЕДНОГО

ЭЛЕМЕНТ

<выражение пересчета>)

конец цикла

<оператор>

ЗАВЕРШЕНИЕ

Явно не записывается

Таблица 7.16. Цикл

for

§ 7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

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

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

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

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

нятость греха не является извинением для грешника), и углубляться в них.

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

предметом одной из глав фундаментального курса (скажем, «Семантики ал-

горитмических языков»).

7.3.1. Инвариант и параметры цикла

Любой вид потоковой обработки — это схематическое описание процес-

са, управляемого последовательностью S

, такой, что получение элемента

i+1

из элемента S

задано генерацией потока.

С формальной точки зре-

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

некоторого “общего” потока, состоящего из сложных (структурированных)

элементов:

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

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

Так что цикл

Алгола-68

остановился в развитии на полпути к важной кон-

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

Указанные в §7.2.1варианты независимой и функциональной генерации потока на уровне

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

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

330

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

но изменяющихся элементов.

Для параметров цикла язык

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

значительно более последовательное и красивое решение. Параметры цикла

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

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

полнения цикла.

Конечно же, концепция выражений, вырабатывающих значение, также

принятая в

Алголе-68

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

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

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

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

Ал-

гол-68

допустил очередную непоследовательность: этот оператор значения

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

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

влена.

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

ЯРМО

, созданный в

Новосибирском филиале ИТМ и ВТ для поддержки разработки системного

программного обеспечения на ЭВМ

БЭСМ 6

и обеспечившего возможность

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

Эльбрус

еще до

того, как эти машины начали выпускаться. В языке

ЯРМО

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

ний реализована в полной мере: все операторы вырабатывают значение, при-

чем в большинстве случаев значение сложной конструкции наследуется от

вложенного оператора, исполнявшейся непосредственно перед ее заверше-

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

запоминающий значение предыдущего оператора:

<источник значения>

→

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

Символ “

;

” означает забывание последнего значения.

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

ный вопрос. Цикл типа потока бессмысленен, если из него нет выхода. По-

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

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

чаще всего число оставшихся шагов в программе не фигурирует явно (иначе

задавался бы цикл

for

). В данном случае мы очередной раз сталкиваемся с

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

мы призраки как минимум не нужны (порою они могут быть даже вредны),

но нужны для ее обоснования (см. стр. 127). Неявным значением-призраком

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

лями

Алгола-68

, явилась основной бедой данного языка.

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

331

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

числа оставшихся шагов. Поскольку любая убывающая последовательность

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

зрака гарантирует конечность цикла.

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

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

Потоковый цикл соответствует математическому доказательству по ин-

дукции. Базис индукции — его инициализация, шаг индукции — итерация

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

тому, что требовалось доказать.

Теперь рассмотрим форму рассуждения по индукции. Шаг индукции име-

ет вид (мы выписали его с явным указанием всех параметров цикла):

∀i



A(i, x

, . . . , x

) ⇒

A(i + 1, f

(i, x

, . . . , x

), . . . , f

(i, x

, . . . , x

))



(7.1)

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

няется отношение между ними.В математике это отношение называется пред-

положением (или утвеждением) индукции, в программировании — инвари-

антом цикла.

Пример 7.3.1. Для программы

Prime_Numbers_1

инвариантом основного

цикла является простая логическая формула

Prime ⇔ Prime(i),

где P rime — предикат ‘Быть простым числом’. Для следующей программы

Prime_Numbers_2

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

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

го языка:

P r(j) 6 i < P r(j + 1), где P r — функция, перечисляющая

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

Prime

имеет значение

P r(j) = i, и для всех k < j a[k − 1] = P r(k).

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

рассуждений по индукции — парадокс изобретателя: очень часто для успешного доказа-

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

строго обосновано, что имеются утверждения вида

∀i f(i) = 0,

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

сколь угодно высоких порядков (см., напр., [63]).

332

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Для последующих вариаций программы инвариант цикла еще больше услож-

няется.

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

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

мые в программе значения (например, a[k −1] и P r(k) выше). Это необхо-

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

слимости и концентрируемся на их свойствах и их отношениях к понятиям

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

дать с призраками (ведь функция P r(k) определена для всех натуральных k,

а не только для множества индексов массива).

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

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

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

риантом цикла. Для выделенного ниже, в программе 7.3.2, цикла имеется,

например, следующий полный инвариант:

(imi <= ima) && (x != a[( imi + ima )/2 ])

Полный инвариант существенно зависит от выбора присутствующих в нем

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

единственным.

7.3.2. Цикл Дейкстры и цикл-‘паук’

Данный параграф перебрасывает мостик к следующей теме нашего изло-

жения: циклам, не являющимся потоковыми. Э. Дейкстра, осознав концеп-

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

оригинальной форме цикл Дейкстры имеет вид

→ S

. . .

→ S

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

с совместного вычисления охран. Затем выбирается то из действий, которое

соответствует истинной охране (если истинных охран несколько, то, как и

в условном операторе, любое, но одно). Выполняется это действие, и цикл

возобновляется.

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

333

Таким образом,условие выхода из цикла неявно: это ложность всех охран.

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

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

и на этом основании отвергал часть

else

. В операторе цикла он же суще-

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

кла. Если уж явно выписывать условия, то все существенные. Альтернатива

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

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

ется следующий вариант цикла (цикл-‘паук’), в котором условия завершения

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

для сообщения об ошибке.

→ S

. . .

→ S

out

→ T

. . .

→ T

else

Error_Analysis

В отличие от традиционного цикла, логические корни цикла Дейкстры и ци-

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

например, в нильпотентных логиках. Эти формы циклов естественно сопря-

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

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

7.3.3. Совместный цикл

Какую дисциплину выполнения цикла не отражает ни цикл

for

, ни другие

виды циклов в языке

и в других языках традиционного типа? Нет цикла,

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

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

в языке конструкцию

для всех <параметр цикла> из <множество значений параметра> <оператор>

Смысл цикла, о котором идет речь, в том, что <оператор> выполняется

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

334

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

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

SETL

со-

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

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

мере, в двух отношениях:

• отпала необходимость фиксировать порядок перебора значений пара-

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

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

нятнее;

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

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

ствие, облегчилось распараллеливание.

Оператор совместного цикла

‘{’ <

параметр

> ‘ ∈ ’ <

множество значений

> ‘|’ <

оператор

> ‘}’

(или

(

∀

∈

X: S)

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

СЕТЛ

), позволяет исполнять

для различных

в порядке, наиболее подхо-

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

шую эффективность вычислений (в частности, это существенно при возмож-

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

ки).

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

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

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

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

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

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

Несколько слов о множестве значений параметра в цикле для всех. Спо-

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

ке

Pascal

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

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

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

жественные операции (как это делается в языке

СЕТЛ

), говорить о вызовах

функций, вырабатывающих значения множественного типа и т. д. А вот ре-

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

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

СЕТЛ

, поскольку он был со-

вместной советско-американской разработкой.