Д Р А К О Н О Г Р А Ф И К А

Маршрутами ДРАКОНа | Краткое руководство по техноязыку | Циклические алгоструктуры


Содержание

Цикл

Сложные циклы: диоформы и произвольное следование

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


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

Цикл

Является нелинейной структурой с обратной связью (ОС) - маршрутом, включающим участки как с прямым следованием, так и с обратным, причём последний замыкается на главную вертикаль конструкции выше ветвления. Выбор этого маршрута приводит к итерации - очередному выполнению охваченных ОС операторов, но, возможно, в иной алгоритмической обстановке (которая может изменяться в ходе итерации); выбор другого маршрута означает выход из цикла. Как следствие, маршрут циклической структуры включает повторяющиеся фрагменты; определение же маршрута цикла (и его формулы) аналогично ветвлению.

Традиционные варианты этой структуры в техноязыке записаны эргономично. Так, замыкание обратной связи оформлено как икона Петля цикла; т.о. в ней невозможно размещение икон. В результате сохраняется принцип, по которому вертикаль обратного следования не считается шампуром (отсюда и топологический запрет на загибы вертикалей шампур-блоков вверх, и отдельная икона Период для паузы в петле цикла), а расположение вертикалей такое же, как в развилке; то и другое удобно для составления и чтения схем.

Традиционные «наукообразные» названия обычных циклов «с предусловием» и «с постусловием» в техноязыке заменяются соответственно на цикл ПОКА и цикл ДО, а цикл «с параметром» называется циклом ДЛЯ. Кроме того, вводятся новые виды циклов, максимально использующие возможности языка.

Важно уяснить себе, что в техноязыке цикл любого вида организуется только добавлением макроиконы в нужную вертикаль. Пересадки лианы возможны в теле цикла для организации т.н. досрочных выходов; образовывать новый цикл при этом не допускается.

Рассмотрение начнём с гибридного цикла, представляющего собой общую форму структуры обычного цикла (см. схему далее).

Обычный цикл – формальная структура на техноязыке

Здесь мы также выделяем штрихпунктиром обобщённые блоки, на которые структурируем конструкцию.

В цикле развилка играет иную роль – условия выбора между маршрутом, который завершается возвратом, и маршрутом, продолжающим следование (до конца шампура либо до следующего ветвления). Поэтому здесь в общем случае не имеет смысла понятие главного маршрута и операция рокировки.

Далее проведём «очную ставку» с блок-схемами, результаты которой показаны на рисунке.

Обычный цикл (гибридный) – «очная ставка» на техноязыке и языке блок-схем

Цикл ЖДАТЬ позволяет регулировать темп итераций за счёт введения в цепь обратной связи оператора задержки (иконы Пауза).

Также м.б. необходимо расположить тело полностью до или после условия цикла; так приходим к частным формам обычного цикла.

Цикл ДО и цикл ПОКА отличаются, кроме блочного состава тела, также конфигурацией соединительных линий (см. схемы); изменения объяснены в формальной структуре (см.).

Как частные подвиды возникают также циклы ЖДАТЬ ДО и ЖДАТЬ ПОКА.

Конструкции обычного цикла частных типов (ПОКА и ДО) на техноязыке

Цикл ДЛЯ применяется, когда число повторений либо заранее известно, либо м.б. вычислено по известным граничным значениям некой числовой переменной и величине её приращения за один повтор цикла. Всё это иллюстрирует формальная структура цикла, записанная через цикл ДО (см. схему).

Здесь мы применили другой прием приведения обобщённой схемы к стандарту техноязыка – замену шампур-блока иконой Вставка; так целесообразно поступать, когда содержание блока нам известно.

Конструкции цикла с параметром – формы записи на техноязыке

Наконец, в Обероне-2 имеется конструкция LOOP-EXIT-цикла. Его также можно записать с использованием БП. Результаты показаны ниже:

Цикл LOOP-EXIT – формы записи через безусловные переходы

Здесь мы для наглядности сопоставления с ТЯП-формой записали метки линейных БП иначе, чем ранее для сложных ветвлений. Естественно, что переход на начало цикла (метку входа в цикл) оказывается кратным (мы это обсуждали для иконы Петля цикла).

По сути, получено инвариантное представление для выкладки простых циклов; это очевидно на правой схеме, полученной путём рокировки условия цикла в левой. Её мы показали в полной лиоформе (готовой для выкладки на «ленту памяти» исполнителя-информашины).

А что получится, если любые развилки ведут внутрь тела цикла? Тогда не имеем выхода и получаем «зацикленную» (логически бесконечную) конструкцию. Она также имеет и практическое, и теоретическое значение; подробнее см. п. 2.3.1.

По правилам Оберона, данный цикл может иметь и более одного выхода, но любой из них должен вести на следующий за циклом по ходу следования оператор (икону). При этом получится сложный цикл; визуализацию и анализ его оставляем читателю, а далее займёмся другими сложными (и в то же время регулярными) циклическими алгоструктурами.

Сложные циклы: диоформы и произвольное следование

К сложным прежде всего относятся циклы в цикле, как иерархия вложенных друг в друга простых циклов. Такую конструкцию называют ещё «гнездом циклов».

Цикл в циклеконструкция, в которой тело цикла, входящего в её главную вертикаль (внешнего), содержит в себе другой цикл (внутренний); при этом внутренний цикл может располагаться как до условия цикла, так и после него.

И внешний, и любой из внутренних циклов м.б. любого типа. Схематически простые циклы в цикле (имеющие только один внутренний цикл) показаны в /1, Гл.9/. Ниже показана общая структура гнезда циклов для одного уровня вложенности.

Обобщённая структура вида "цикл в цикле" (с одинарным вложением)

Каждый шампур блок на схемах, конечно, в свою очередь может включать в себя циклы; так образуются цепочки циклов и циклы в цикле более глубокой вложенности (гнёзда циклов).

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

Переключающий цикл можно разложить на петлю цикла и переключатель-условие цикла (специально изменённый переключатель, см. верхнюю форму записи); но можно выделить в нём (см. нижнюю форму) условие цикла (первую развилку) и особый блок, который включает ветвление внутри тела цикла по остальным условиям; его связь с главной вертикалью конструкции можно получить только пересадкой лианы (поэтому блок и назван лианным).

Переключающий цикл – формы записи на техноязыке

Очевидно, по шампур-методу этот вид цикла формируется путём добавления вариантов в макроикону Переключающий цикл изнутри слева.

Как мы увидим далее, по этому принципу можно построить и иную разновидность переключающего цикла; поэтому рассмотренную будем называть циклом Паронджанова.

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

Ещё один сложный цикл Дейкстры был предложен как структурная конструкция Э. Дейкстрой ещё для текстовых прогязыков. В ТЯП-форме он описан, в частности, Виртом1. Визуализация этого описания возможна, если считать условие цикла сложной развилкой. Выберем инверсную запись этой развилки, которую мы использовали для сложных ветвлений; получим следующую конструкцию:

Цикл Дейкстры в инверсной записи

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

А как построить такую конструкцию по шампур-методу? Для этого надо выделить петли составляющих циклов.

Принцип образования цикла Дейкстры

Теперь построим цикл с условием в прямой записи. Для этого введём в предыдущую схему линейные БП, затем обратим развилку условия и подставим тела ветвей. Результат показан на схеме ниже:

Цикл Дейкстры в прямой записи

Как и ранее при введении линейных БП в дракон-схемы, считаем, что рассматриваемая конструкция есть i-тая из N частей, на которые содержащий её некий визуал поделён такими переходами. Исходя из этого формируются имена (метки) для линейных БП.

По сути, здесь выбирается один из возможных маршрутов, но не однократно, как в сложном ветвлении, а с возможностью повтора. Эта возможность определяется анализом состояния при очередном проходе условия; при этом каждая развилка в общем случае проверяет величины состояния (переменные алгоритма), существенные для выбора «своего» маршрута.

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

А можно ли устранить возникшие пересечения? Ответ нам подсказывает запись цикла Паронджанова через цепочку развилок – попробуем сдвинуть содержимое ветвей «по кругу» относительно вертикалей на одну позицию вправо – т.е. та ветвь, что была на первой вертикали, д.б. на второй и т.д... а то, что было на последней вертикали, окажется на первой. При этом нужно также добавить новую развилку, чтобы сохранить смысл вопросов выбора ветвей, а соответствующая «любому другому» значению крайняя правая вертикаль оставляется ненагруженной.

Результат показан ниже:

Цикл Дейкстры в прямой лиоформе без пересечений маршрутов

Интересен вопрос: а как выбирать нужную ветвь? Очевидным представляется использовать порядковый номер ветви как значение переменной выбора; тогда вопрос для очередной ветви сводится к проверке равенства этого значения её номеру. Формируется значение в конце очередной ветви как результат т.н. (восстановления/продвижения) инварианта цикла; проще говоря, сочинитель определяет зависимость номера следующей ветви цикла от результатов (состояния алгоритма), полученных при исполнении текущей ветви. Процедура вычисления по этой зависимости оформляется в конце ветви и получаемое значение присваивается переменной выбора; далее в развилках по цепочке происходит просмотр и выбор нужной ветви (а при определённом значении – выход из цикла Дейкстры).

Понятно, что текущая ветвь м.б. нелинейной; тогда номер следующей ветви может зависеть и от маршрута, по которому текущая исполнялась на этот раз (возможно, простейшим образом – в конце маршрута переменной выбора просто присваивается номер следующей ветви без дополнительных вычислений).

По сути, в цикле Дейкстры можно структурировать содержимое на логические части так же, как в дракон-силуэте; только выбор части условный, а каждая часть м.б. только шампур-блоком. Логика же получается равносильной; роль адреса ветки в «подвале» силуэта играет процедура вычисления номера, в общем случае разная на разных маршрутах внутри ветви. В то же время условность перехода даёт возможность выбора по более сложным основаниям, чем просто маршрут, пройденный в текущей ветви; в пределе можно анализировать алгосостояние целиком. В силуэте аналогичная возможность обеспечивается созданием в конце ветки адресного блока, в котором происходит условный выбор одного из маршрутов, ведущих в «подвал», а далее безусловно по петле силуэта – на нужную часть.

Теперь покажем, как можно представить цикл Дейкстры в виде переключающего:

Цикл Дейкстры как переключающий

Сопоставление этих циклов показывает, что цикл Дейкстры обеспечивает выбор варианта содержания в каждой итерации, тогда как цикл Паронджанова даёт возможность выбора варианта лишь при выходе; итерация же всегда одинакова по содержанию.

Цикл Дейкстры, являясь универсальной программой, может служить и для представления дракон-силуэта; подробности пока изложены в виде примера в п/п 3.1.1.3.

Ну и наконец перепишем полученный результат как прямую диоформу — без линейных БП - и с общей петлёй цикла аналогично инверсной диоформе, с которой начали рассмотрение цикла Дейкстры:

Цикл Дейкстры в прямой диоформе

Интересен вопрос: а как выбирать нужную ветвь? Очевидным представляется использовать порядковый номер ветви как значение переменной выбора; тогда вопрос для очередной ветви сводится к проверке равенства этого значения её номеру. Формируется значение в конце очередной ветви как результат т.н. (восстановления/продвижения) инварианта цикла; проще говоря, сочинитель определяет зависимость номера следующей ветви цикла от результатов (состояния алгоритма), полученных при исполнении текущей ветви. Процедура вычисления по этой зависимости оформляется в конце ветви и получаемое значение присваивается переменной выбора; далее в развилках по цепочке происходит просмотр и выбор нужной ветви (а при определённом значении – выход из цикла Дейкстры).

Понятно, что текущая ветвь м.б. нелинейной; тогда номер следующей ветви может зависеть и от маршрута, по которому текущая исполнялась на этот раз (возможно, простейшим образом – в конце маршрута переменной выбора просто присваивается номер следующей ветви без дополнительных вычислений).

По сути, в цикле Дейкстры можно структурировать содержимое на логические части так же, как в дракон-силуэте; только выбор части условный, а каждая часть м.б. только шампур-блоком. Логика же получается равносильной; роль адреса ветки в «подвале» силуэта здесь играет процедура вычисления номера, в общем случае разная на разных маршрутах внутри ветви. В то же время условность перехода даёт возможность выбора по более сложным основаниям, чем просто маршрут, пройденный в текущей ветви; в пределе можно анализировать алгосостояние целиком. В силуэте аналогичная возможность обеспечивается созданием в конце ветки адресного блока, в котором происходит условный выбор одного из маршрутов, ведущих в «подвал», а далее безусловно по петле силуэта – на нужную часть.

Понятно, что любой из рассмотренных сложных циклов (а равно и любой простой цикл, который можно выделить в составе сложного) м.б. типа ЖДАТЬ.

Мы для простоты не показывали в петлях циклов икону Период. Однако попытка показать её выявит неравнозначность схем с общей и раздельными петлями вложенных циклов — в первом случае мы приходим на каждом выходе из цикла к одной и той же иконе Период, во втором — для каждого выхода к своей.

Какое изображение правильное? Очевидно, с раздельными петлями — оно исходит строго из шампур-синтаксиса дракон-схем. Отсюда видно, как важно при визуализации целостно определять смысл исходных конструкций.

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

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

Цикл с досрочным выходом является допустимой в техноязыке произвольной циклической структурой. К такому циклу приводит необходимость произвольного ветвления на пути к петле цикла и/или к досрочному выходу, а также нескольких досрочных выходов (точек слияния с главной вертикалью, разделённых шампур-блоками). Общая цель – учесть факторы, возникающие по ходу выполнении тела цикла, как условия окончания повторения и/или изменения маршрута в блоке ПОКА (пропуска каких-то частей блока). Досрочные выходы образуются вливанием в главную вертикаль конструкции ниже основного выхода из цикла вертикалей отдельных развилок блока ПОКА; остальные вертикали ведут в петлю цикла. Для вливания пересаживаются лианы; т.о. образуется разновидность лианного макроблока дракон-схемы. Точек слияния с петлёй м.б. несколько; в любом случае это соединительные вершины, связанные между собой горизонтальными и/или ломаными линиями (конечно же, не содержащими икон).

Как и для произвольных ветвлений, для произвольных циклов можно придумать лишь частные иллюстративные примеры, см. напр. /1, Гл.9/.

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

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

Как и произвольные ветвления, произвольные циклы образуются из матрёшек; здесь они включают макроиконы циклов и, возможно, макроиконы ветвлений в блоках тел циклов.

В начало страницы | Оглавление | Главная | Версия для печати

Copyright © Жаринов В.Н.

1Вирт Н., 2010. – Приложение С.



Hosted by uCoz