Визуальный язык ДРАКОН

Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность

Инструменты пользователя

Инструменты сайта


shampur-ukladka_na_ploskosti_-_svet_i_teni_siluehta

Шампур-укладка на плоскости: свет и тени силуэта

Структуру связей предмета описания не всегда можно показать двумерно без пересечений. В математике схему типа представляющей структуру императивного знания — маршрутов деятельности, потоков управления — называют аранжируемым/устремлённым/сводимым графом, а если в этом графе нет пересечений — говорят, что он также планарный. Непланарный же устремлённый граф нужно «уложить» на плоскости, устранив пересечения. Конечно, необязательно, чтобы этот граф имел смысл именно структуры маршрутов алгоритма — речь идёт только о структуре схемы.

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

Непланарная аранжированная схема (в терминах ШМ — примитив) с пересечениями разделяется веточными соединителями на блоки-единицы укладки — ветки — так, что из каждой пары пересекающихся цепей одна оказывается проходящей через подсхему связи веток — своего рода кросс (по аналогии с сетями связи; в проводке компьютерных сетей часто называется «патч-панель»). Тем самым пересечение устраняется. Уложенная на плоскости с применением соединителей аранж-схема в ШМ называется силуэтом, а кросс-подсхема— петлёй силуэта.

Силуэт можно и получать сразу — выводом из заготовки (ШМ-аксиомы). Только такой путь и допустим в ШМ; поэтому Паронджанов рекомендует мало-мальски сложный алгоритм визуализировать сразу как силуэт — чтобы избежать его вывода заново. Заготовка имеет исходно минимальное число веток (две); определены операции добавления/удаления ветки в силуэт.

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

Видно, что в петлю силуэта можно уложить и петлю цикла. Так образуется т.н. веточный макроцикл (далее — ВМЦ).

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

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

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

Если раскрыть вершины гребёнок, то видим, что по главным входам/выходам ветки силуэта связаны в цепочку. Однако она представлена как цикл. Это и есть приём силуэтной укладки — чтобы на схеме не появлялись вертикали следования против шампура — вместо них рисуем петлю цикла (где следование против шампура разрешено). В рамках шампур-метода это не фиксируется — он исходно определён для «слепышей». Но сочинитель должен знать — тексты вершин Адрес на главных выходах веток однозначно определяются по правилу «чем правее ветка — тем она дальше по шампуру от заголовка силуэта».

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

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

Развилок в теле ветки м.б. много (или не быть ни одной — потому они тоже показаны пунктиром и подведены под РБНФ-итератор с независимым индексом). И побочных выходов можно сделать более одного (при соблюдении ограничений на операции с лианой). Располагаются развилки как на главной вертикали ветки, так и м.б. на любой побочной (если таковые имеются) — поэтому стрелки-указатели направлений итерации на плоскости направлены «на все стороны света».

Мысль следующая — силуэт тоже можно зациклить. Мы уже говорили, для чего это нужно. Но зациклить можно и часть веток внутри силуэта (или одну ветку). Для этого нужно, чтобы хотя бы один побочный маршрут выходил из тела ветки на нижнюю гребёнку. Тогда он заканчивается вершиной Адрес, текст в которой уже можно выбирать любым из числа имён веток данного силуэта. Если это имя ветки, лежащей левее, чем данная — то получается, что нужно идти против шампура. Так что получится уже реальный цикл. Он и называется веточным макроциклом (ВМЦ). Почему «макро» — а потому, что ветки задают макроструктуру маршрутов алгоритма. И ВМЦ возможен только с «шагом ветками» - т.е. ни его начало, ни конец не могут располагаться внутри тел веток.

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

Третья мысль — в силуэт можно войти не обязательно с начала. Но и через каждую ветку, если она не внутри ни одного веточного макроцикла. Если определить дополнительные входы на имена веток, либо не входящих ни в один ВМЦ, либо начальных в одном и более веточных макроциклов.

Ну и наконец — если все полные ветки из силуэта удалить (РБНФ-продукции допускают такой вариант), то получится… примитив. Причём в нашем определении видно — он тоже м.б. как обычным, так и «зацикленным».

А что за величина b? Это — переменная номера следующей ветки. Здесь мы, в сущности, проиллюстрировали сказанное Паронджановым об укладке маршрутов:

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

В присваиваниях значений этого номера мы видим то же самое правило «чем правее — тем дальше» (у Паронджанова дана эквивалентная формулировка: «чем правее — тем позже»).

Такое детальное раскрытие выявляет интересный факт — выбор-то следующей ветки на самом деле организуется в теле предыдущей. И вершины-разветвители в верхней гребёнке «петли силуэта» на самом деле оказываются фиктивными — ничего они сами по себе не выбирают…

Тогда нужен ли нам этот «второй тур выбора»? Мы же не претендентов в консерваторию отбираем… или на выборную должность… :-) Из той же схемы по зрелом размышлении можно увидеть, что не нужен. Достаточно воспользоваться тем, что имена веток — это метки БП. И на каждую из них можно прямо «разадресовать» команды БП из «подвала» силуэта. Вместо того, чтобы адресовать их все на начало силуэта (имя Сш<1>). Команды, находящиеся на главных выходах веток адресуются каждая на следующую ветку, на побочных выходах — на любую ветку по выбору сочинителя. Схему предоставляем сочинить читателю.

Силуэтная укладка есть физическое подразделение структуры маршрутов. Петля силуэта представляет связи веток как совокупность возвратных переходов с выходных соединителей на входные. В императивном смысле (для дракон-силуэта) это простые безусловные переходы. Достоинство их силуэтного употребления — в том, что передачи возможны не в произвольные места схемы, а лишь в заданные делением на ветки. Тем самым допускается goto, но также ограниченный — только на начала веток. Недостаток — в том, что переходы явные, и в терминах программирования дракон-силуэт м.б. представлен только на языках с явным БП (на ЯВУ с goto и на машинах с командой jmp-типа).

shampur-ukladka_na_ploskosti_-_svet_i_teni_siluehta.txt · Последние изменения: 2012/04/07 13:35 — Владислав Жаринов