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

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

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

345

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

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

чения переменных

a, x, imi

ima

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

ловке цикла и во внутренних условных операторах.

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

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

состоящей из тех данных, которые:

a) определяют поведение выполнения фрагмента, и

b) изменяются при выполнении фрагмента.

(7.6)

Эти два признака характеризуют понятие обстановки. В частности, локаль-

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

элементами его обстановки. Не следует включать в обстановку и то, что не

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

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

Применительно к выделенному фрагмен-

ту программы 7.3.2 это переменная

. С одной стороны, она не обладает са-

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

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

imi

ima

облегчает понимание смысла выделен-

ного фрагмента. Сами переменные

imi

ima

можно рассматривать или с ло-

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

как поиск x среди элементов массива

a[imi],..., a[ima]

; или глобально, инте-

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

x среди элементов массива

a[0],..., a[SZA]

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

шихся шагов цикла с предусловием.

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

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

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

кализации имен, задающие контексты фрагментов программы. Дадим неко-

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

Определение 7.3.2. Локальным контекстом фрагмента программы назы-

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

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

Еще раз напомним, что часто содержательный смысл фиксируется при помощи призра-

ков.

346

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

Глобальный контекст фрагмента программы — объединение локальных

контекстов всех фрагментов программы, которые окружают данный фраг-

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

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

трые включены как библиотечные файлы директивой

#include

языка

C/C++

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

uses

языка

ObjectPascal

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

(несколько одинаковых имен или одно и то же имя в разных смыслах), они

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

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

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

Для обсуждаемого фрагмента 7.3.2 принципиально, что

int a [SZA]

— часть

глобального описания, поскольку

является элементом обстановки и вы-

деленного фрагмента, и функции

main

. Не очень принципиально, что дан-

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

Описание

inth;

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

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

int h = (imi+ima)/2;

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

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

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

ется),

b) стремиться к использованию инициализации переменных при их описа-

нии.

Определение 7.3.3. Cостояние контекста в языке традиционного типа —

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

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

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

находится выполняемое действие.

Состояние обстановки — аналогичная пара, где Z задает значения пере-

менных обстановки.

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

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

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

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

347

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

дет ли выполняться цикл (условие срабатывания). Для цикла

do ...while true

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

с условием цикла.

§ 7.4. АБСТРАКТНО-СИНТАКСИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

7.4.1. Представление циклов

Абстрактно-синтаксическое представление оператора циклов достаточ-

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

ний головных вершин структуры оказываются одинаковыми (см. рис. 7.2).

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

Выражение

ДействияУсловие

Операторы

цикла с pred-

условием

Оператор

Выражение

ДействияУсловие

Операторы

цикла с post-

условием

Оператор

Рис. 7.2. Абстрактно-синтаксическое представление оператора циклов с

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

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

ем> сводится к следующему:

1. Вычислить ветвь <Условие>.

2. Если результат вычисления 1 — истина, то

Вычислить ветвь <Действия>.

Перейти к 1.

3. Завершить вычисление <оператора Цикла с предусловием>.

348

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

Алгоритм работы абстрактного вычислителя для <Цикла с постусловием>

сводится к следующему:

1. Вычислить ветвь <Действия>.

2. Вычислить ветвь <Условие>.

3. Если результат вычисления 2 — истина, то

Перейти к 1.

4. Завершить вычисление <оператора Цикла с постусловием>.

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

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

стоятельно.

7.4.2. Структурные переходы

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

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

break;

continue;

. Их абстрактно-синтаксическое представление (см. рис. 7.3) еще

break

Оператор

continue

Оператор

Рис. 7.3. Абстрактно-синтаксическое представление оператора завершения

выполнения цикла, переключения и итерации

проще, чем в предыдущем случае.

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

затруднения в связи с нелокальностью их действия: завершается не та кон-

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

ская. Завершаемая конструкция, возможно, отстоит на много уровней от ме-

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

349

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

не ограничено)

. Это новая ситуация абстрактных вычислений.

Обратим внимание,что инструкция «Вычислить», используемая в каждом

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

ется его рекурсивным вызовом.Эта рекурсия отражает вложенность абстракт-

но-синтаксических конструкций. И цикл, и итерация цикла, и переключение,

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

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

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

дующих вызовов. Таким образом, следует откорректировать алгоритмы рабо-

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

к соседним ветвям.

Эта задача может решаться по-разному.Чаще всего определяют специаль-

ные флаги:

F_break

F_continue

. Они выставляются при выполнении опера-

торов

break;

continue;

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

ний.

В частности, алгоритм для

break;

можно задать так:

1. Выставить

F_break

2. Завершить вычисление <оператора Завершения>

break;

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

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

break;

continue;

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

Так, для <Последовательно выполняемых операторов> описание алгоритма

из § 2.3.3 исправляется следующим образом:

1. Если ветвей у вершины нет, то Завершить вычисление <Последова-

тельно выполняемых операторов>.

2. Установить первую ветвь вершины в качестве очередной.

3. Если

F_break

выставлен, то

Завершить вычисление <Последовательно выполняемых операторов>.

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

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

грамм.

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

тельстве теоремы Бема-Джакопини.

350

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

4. Если

F_continue

выставлен, то

Завершить вычисление <Последовательно выполняемых операторов>.

5. Вычислить очередную ветвь вершины.

6. Если следующей ветви для очередной ветви у вершины нет, то

Завершить вычисление <Последовательно выполняемых операторов>

иначе Установить следующую ветвь вершины в качестве очередной

7. Перейти к 3.

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

ранее «Вычислить последовательно все ветви вершины». Сброс флагов —

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

го цикла или переключения, которое должно завершится. Значит, алгоритмы

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

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

кла с предусловием>:

1. Вычислить ветвь <Условие>.

2. Если результат вычисления 1 — истина, то

Вычислить ветвь <Действия>.

3. Если

F_break

F_continue

сброшены, то

Перейти к 1.

4. Сбросить

F_continue

. // Нет нужды его специально проверять!

5. Если

F_break

выставлен, то

Сбросить

F_break

. Завершить вычисление <оператора Цикла с преду-

словием>.

6. Перейти к 1.

Аналогично корректируются остальные алгоритмы. Предлагается проделать

это самостоятельно (см. задачу 10 на стр. 361).

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

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

щей памяти для экстренного завершения всех вызовов типа “Вычислить”: это

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

351

переменные

F_break

F_continue

. В реальных трансляторах могут оказаться

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

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

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

вызвать чувство неудовлетворенности. Проверки на каждом шагу с тем, что-

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

ния конструкции, кажутся не очень естественными.

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

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

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

тическом языке имеет вид

Программа 7.4.1

:Метка уровня:

начало //

конструкции 1;

операторы

начало //

конструкции 2;

операторы

начало //

конструкции 3;

операторы

завершить Метка уровня; //

т. е. прекратить

выполнение конструкции 1 и

всех вложенных конструкций,

с передачей управления

к строке !!!

операторы

конец //

конструкции 3;

операторы

конец //

конструкции 2;

операторы

конец //

конструкции 1;

/*!!!*/

...

то это есть просто спрятанный go to (ниже он и его метка выделены курси-

вом):

Программа 7.4.2

352

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

:Метка уровня:

начало //

конструкции 1;

операторы

начало //

конструкции 2;

операторы

начало //

конструкции 3;

операторы

go to РМ //

метка, добавляемая транслятором

операторы

конец //

конструкции 3;

операторы

конец //

конструкции 2;

операторы

конец //

конструкции 1;

РМ: /*!!!*/

...

Любой конкретный вычислитель имеет среди своих команд оператор без-

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

точно следующего. Просматривая транслируемый текст, надо:

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

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

2. составить таблицу таких меток с полями: имя метки и адрес в про-

грамме,

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

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

струкции 1–3).

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

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

ние текста, осуществляемое транслятором, которое никакого отношения к

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

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

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

Тем не менее,имеется более эффективная,чем преобразование Бема-Джа-

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

лей, реализуемая интерпретатором. Но для этого необходима память вычи-

слителя, включающая структурированый стек контекстов (см. рис. 7.4).

7.4. АС-ПРЕДСТАВЛЕНИЕ ЦИКЛОВ

353

…

Контекст 0

Контекст 1

Контекст 2

Стек растет вниз. Нынешний кон-

текст назван

Контекст 0

. Самая

нижняя единица в стеке — текущий

результат. Стек структурирован

как стек стеков. Каждый подстек

включает данные для блока про-

граммы. Таким образом, каждый

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

вычислений в соответствующем

блоке. В начале каждого подстека

находится его маркер, который

содержит всю необходимую слу-

жебную информацию о подстеке, в

частности, ссылку на предыдущий

маркер.

Рис. 7.4. Стек и контексты

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

струкции нужно запомнить в стеке текущий экземпляр состояния контекста.

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

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

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

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

ваться их именами. Далее можно выполнять обычные действия по вычисле-

нию конструкции.

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

1. Найти на стеке все экземпляры контекста, которые соответствуют вло-

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

завершить;

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

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

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

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

ние следующему найденному и т. д.).

354

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

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

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

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

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

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

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

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

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

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

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

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

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

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

мах команд машин серий

Barroughs

Эльбрус

. Такие машины называются

машинами со стековой архитектурой. Часто стековая архитектура и тегиро-

вание (см. рис. 1.7) совмещаются.

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

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

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

Эль-76

(см. [25]: язык высокого уров-

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

ный язык для машин серии

Эльбрус

) метки могут ставиться только к завер-

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

означает завершение соответствующего блока.

Пожалуй, только в языках

ЯРМО

LISP

концепция структурных перехо-

дов корректно соединена с концепцией вырабатываемых значений. Практи-

чески каждый оператор в

ЯРМО

может иметь часть

иначе

, в которой про-

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

При явном завершении (например, при применении структурного перехо-

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

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

того, чтобы стать значением завершаемого блока. Насчет языка

LISP

смотри-

те главу о функциональном программировании.

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

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

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

на них. В частности, именно так работает выражение

new

C/C++

, см., на-