Выбор

Рассмотренные до сих пор сети данных представляли в первую очередь тот случай, когда в программе нет значительных альтернативных блоков. Условие было лишь средством проверки перехода от одного этапа вычислений к другому. Однако на самом деле, как правило, программа содержит выбор. Для представления выбора в языках программирования имеются условные операторы и операторы выбора. Рассмотрим, что же стоит за выбором.

Пример 14.3.1. Пусть в некоторый момент исполнения программы Вам необходимо временно выбросить больший из двух хранимых в основной памяти обрабатываемых блоков на диск. Поскольку разница в длине менее 216=65536) несущественна, мы можем записать выбор примерно в следующей форме.

if length(A)-lengtn(B)>65536

{ Save(A); Dispose(A); A_present:=false;}, length(A)-lengtn(B)<65536 { Save(B); Dispose(B); B_present:=false;} fi

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

Предложенная форма записи базируется на концепции охраняемых команд, предложенной Э. Дейкстрой. Охраняемая команда исполняется лишь при условии, когда выполнена охрана. Но если данный текст читает программист, он должен понимать, что 'лишь' не всегда означает, что при выполнении условия команда будет выполнена. Оператор выбора по Дейкстре состоит из множества охраняемых команд. В конкретном синтаксисе мы используем для них форму

Guard

Command

Относительное расположение охраняемых команд в операторе выбора безразлично9). Выполняется одна из охраняемых команд, охрана которой истинна. Имеющиеся в языках конкретные формы условных предложений и предложений выбора являются подпорками для реализации охраняемых команд.

Из изложенного следует, что по своей сути выбор так же недетерминирован, как и исполнение структурной программы. Если выполнено несколько охран, с точки зрения задачи абсолютно все равно, какое из действий выбирать. Однако имеющиеся средства программирования10) заставляют нас однозначно сделать выбор, и конечно же почти всегда мы забываем написать в комментариях, что на самом деле выбор безразличен, а затем при модификациях программы появляются заплатки на подпорках и т.
п.

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

-графам. Некоторые вершины могут быть помечены как -вершины, это означает, что достаточно получить один из результатов, соответствующий входящим дугам, и инициировать лишь одно из исполнений, соответствующее выходящей дуге. Для структурированности &--графа необходимо, чтобы он был сетью, удовлетворяющей следующему условию: имеется инъекция , сопоставляющая каждой -вершине ?, из которой выходит несколько дуг, -вершину (?), из которой выходит лишь одна дуга, такую, что любой путь, проходящий через первую вершину, проходит и через вторую. Это неудобоваримое теоретическое условие всего лишь формулирует на точном языке, что -вершины должны группироваться в структуры следующего вида, показанного на рис. 14.2 (количество вариантов может быть любым).


Рис. 14.2.  Сеть охраняемых команд


Содержание раздела

---

---