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

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

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

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


strukturnaja_algoritmizacija_i_shampur-metod_-_sochinitel_stanovitsja_mudrecom

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

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

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

охрана-выбора<главного выхода развилки> ::= лог-выр

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

Важно понимать также вот что. Структура охранного логвыра, как она определена для виопа Д4 в этом подразделе, допускает при проверке охраны также вычисления арвыров. Но результаты этих вычислений используются только в течение проверки. Это значит, что полученные значения недоступны после прохождения виопа. Но не менее существенно, что они недоступны и до этого. Т.е. возможно, что мы проверяем не то, что имели в виду для данной развилки (скажем, в неформальной постановке её вопроса). И это нужно учитывать. Разумный путь — использовать в охранах только имена величин (это и есть простейшая форма арвыра, как можно видеть из определения виопа Д3).

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

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

Кросс выбора Дейкстры имеет следующую структуру:

Теперь мы не ограничиваемся схемой, а приводим также её текстовый эквивалент. Язык текста условный программный с русской лексикой и РБНФ — для кросса это ЯВУ типа Оберона (а в тексты '(*' и '*)' берутся комментарии), для смысла — Ассемблер для машин с явной адресацией памяти. Как можно видеть, атомарные конструкции допускают единообразное описание формальным текстом. Предоставляем читателю попробовать составить такое описание для лианных структур. :-)

Первая мысль, очевидная уже из схемы кросса — крайняя правая ветвь выбирается по неявному условию, которое неформально можно сформулировать как «любое другое< кроме явно заданных в развилках>». Строго же говоря, это логвыражение, определённое следующим образом. Из множества значений для каждой из величин, входящих в каждое из явных условий (охран выбора Дейкстры) выделяется подмножество значений, на котором ни один из вопросов развилок, содержащий эту величину, не будет иметь ответ «да» (т.е. ни одна из охран не будет истинна). Когда значение каждой из величин при исполнении равно какому-то из этого подмножества — выбирается крайняя правая ветвь конструкции. Объединение этих равенств по И (конъюнкция) и даёт искомое условие.

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

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

Ленивые вычисления предполагают связывание охран посредством т.н. полустрогих булевых операций. В такой операции порядок операндов зависит от их значений и смысла согласно цели вычисления. Базовыми являются операции and then и or else (подробнее см. у Мейера в Гл. 5).

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

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

Выбор Дейкстры в своё время был сформулирован в текстовом виде как т.н. конструкция IF-FI; та форма, в которой мы записали текст, известна в англоязычном варианте как IF{-EL[S]IF}-END. Разработчиками ряда текстовых ЯВУ был определён частный случай выбора по константам— т.н. CASE[-ELSE]-END-конструкция. Именно она естественно изображается в техноязыке как дракон-переключатель. Дракон-развилка есть частный случай выбора Дейкстры по единственному условию. Поэтому и выбор Дейкстры можно записать (в тех языках где нет такой конструкции) как вложение обычных операторов ЕСЛИ-ТО[-ИНАЧЕ]-ВСЁ (также вплотную — т.е. не д.б. операторов ни между ВСЁ, ни между концом предыдущей ТО-ветви и текущим ЕСЛИ).

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

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

Перейдём к циклу Дейкстры. Он также изначально был сформулирован в текстовой записи. Современная формулировка дана в новом издании классической работы «Алгоритмы и структуры данных» Н. Вирта (Приложение С). Фактически она представляет выбор Дейкстры, вложенный как тело цикла ПОКА. О смысле конструкции сказано следующее:

Грубо говоря, обычно n-веточный цикл Дейкстры соответствует конструкциям из n обычных циклов, каким-то образом вложенных друг в друга. (Алгоритмы и структуры данных, с. 268)

Каким же образом? Попробуем разобраться с помощью графит-метода (шампур-метод снова недостаточен — нам нужно привлекать и содержание вершин).

Для компоновки содержания на заданном формате мы ввели т.н. дополнительные изломы линий на верхней схеме. Как можно видеть, это затрудняет чтение схемы: поэтому обычно следует избегать такой ситуации.

Можно заметить, что ветвь N здесь необязательно было и изображать — её отсутствие в определении смысла конструкции не меняет. Кстати, в определении Вирта её нет.

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

Если сказанное неочевидно сразу — можно «расплести» петлю цикла Дейкстры на петли составляющих обычных циклов. Учитывая, что при этом недопустимы пересечения. При этом у каждй ветви появится своя точка возврата.

Следующая мысль — ветвь составляет ДО-подтело каждого из вложенных циклов; все они обычно присутствуют. Но ничто не мешает нам оставить пустой одну из ветвей. Это значит, что по данному паролю не надо ничего делать, но не надо и выходить из цикла. Если же при сочинении ЦД выходит, что нужно оставить пустыми две и более ветвей (но не все — это бессмысленно) — значит, их условия можно объединить в одно. И тогда пустая ветвь опять станет единственной.

Представляет интерес определение порядка следования по «шапке», вплоть до выхода из цикла. В книге на этот счёт сказано следующее:

Хотя в теории Дейкстры последовательность выбора ветвей цикла и вычисления соответствующих охран не определена, в этой книжке принято, что охраны вычисляются в текстуальном порядке. (Алгоритмы и структуры данных, с. 269)

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

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

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

Текстовый код (для второй схемы) здесь не приводится — читатель может написать его сам.

В современных текстовых ЯВУ цикл Дейкстры существует как в исходном синтаксисе (т.н. конструкция DO-OD, например, в языке Promela, описанном в Гл. 8 работы Ю.Г. Карпова по гарантоспособному программированию "Model Checking..."), так и в модернизированном - как WHILE-ELSIF-END и LOOP-ELSIF-EXIT (рассмотренные в упомянутом Приложении С к книге Вирта).

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

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

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

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

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

Представим себе, что ЦД охватывает всё тело алгоритма — от заголовка до конца. Только условия «шапки» расположим так, как при раскрытии смысла верхней гребёнки — по горизонтали. Получится схема, кросс которой показан на рисунке:

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

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

Также показано, что дейкстрал можно «зациклить».

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

Текстовая запись дейкстрала возможна различным образом — в зависимости от конструкций Дейкстры, поддерживаемых текстовым ЯВУ. Если имеется только выбор Дейкстры — текст показан вверху. Кстати, здесь уточнено, что ЦД можно получить вложением выбора Дейкстры в цикл LOOP. Поскольку и этот цикл можно получить из других (об этом мы уже говорили) — то ЦД (как и дейкстрал) в принципе можно написать на любом императивном языке.

А если в языке имеется ЦД — то можно просто вложить его запись в конструкцию описания алгоритма (программы). Как показано на нижнем варианте текста. Разумеется, «впритык» - т.е. перед и после ЦД ничего не д.б. вставлено.

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

Это можно видеть на схемах ниже.

Для упрощения силуэт мы показали одноадресным и без дополнительных входов.

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

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

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

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

Итак, в дейкстрале изначально не нужны заземления лиан. Нет необходимости и в пересадках — те же варианты использования можно получить разнесением простых шампур-блоков лианного макроблока по дейкстрал-ветвям и надлежащим выбором ветвей. Это в пределе — часто можно проще, сочетая ветвления в телах дейкстрал-ветвей с выбором самих ветвей.

Дейкстрал, силуэт и примитив

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

Здесь можно видеть, чем представляются вершины кросса в системе команд типичного исполнитля алгоритмов — машины с адресной архитектурой. Это команды БП — простого и с возвратом.

Использование ЦД возможно двумя путями:

  • вывода тела дракон-схемы или его части как ЦД в рамках ШМ-правил (как варианта вложенного цикла);
  • модификации метода для использования ЦД-организации схем, начиная с аксиом.

Первый путь требует только определённого порядка вывода в ШМ:

  1. схема-дейкстрал может пониматься как примитив, так что для вывода берём заготовку-примитив;
  2. новая ветвь дейкстрала добавляется вводом дракон-атома обычного цикла как ДО-подтела обычного цикла предыдущего уровня вложенности за счёт такого единообразного порядка вложения формируем метаструктуру тела визуала (только «шапка» будет «в столбик»);
  3. чтобы сделать шапку по горизонтали («лесенкой», на манер силуэтной), последовательно рокируем плечи условий вложенных циклов.

Второй путь предполагает определение заготовки для вывода схемы как ЦД, ЦД-атома, а также операций добавления/удаления ветви (аналогично добавлению/удалению ветки силуэта). Это уже выходит за рамки исходного ШМ и потому может обсуждаться отдельно.

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

  • пользоваться известными методами формальной спецификации задачи, хорошо разработанными и допускающими эргономизацию;
  • приводить разработанные силуэты и/или лианные макроблоки к форме ЦД.

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

Показано, что дракон-силуэт можно преобразовать в ЦД-схему. Тем самым ЦД-укладка обратно совместима с силуэтной. Т.е. можно переводить «силуэтно-унаследованные» визуализации алгоритмов и потоков управления программ в ЦД-запись.

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

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

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

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

Следует основываться на этих конструкциях и при профессиональном обучении алгоритмизации и программированию. Заметим, что их введение не отменяет существующих возможностей шампур-метода. Поэтому можно пользоваться и ими. Однако, как можно видеть из раскрытия смысла, силуэтная структуризация целесообразна лишь при описании алгопроцессов с расчётом на их прямое кодирование для исполнителя-машины. Фактически такова схема работы по исходной технологии ГРАФИТ-ФЛОКС. Необходимости же в неатомарных конструкциях внутри алгоритма вообще нет.

strukturnaja_algoritmizacija_i_shampur-metod_-_sochinitel_stanovitsja_mudrecom.txt · Последние изменения: 2012/05/20 16:50 — Владислав Жаринов