Различия

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

--- jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:drakon_shampur_ocenka [2012/03/22 16:37]
Владислав Жаринов [Упорядочение маршрутов]
+++ jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:drakon_shampur_ocenka [2012/03/22 17:13]
Владислав Жаринов [Разметка схем и гибридные техноязыки: ДРАКОН начинает, ГРАФИТ выигрывает]
@@ Строка 7: / Строка 7: @@
-===== Структурная алгоритмизация и шампур-метод =====
-Недостаток силуэтной укладки как физической можно преодолеть, если перейти к логической укладке маршрутов. Имеется в виду, что вход в единицу укладки определяют не соединители, а условия выбора. Часто об условных переходах говорят, что их условие «охраняет» выход, соответствующий истинности (или просто называют условное выражение //**охраной**//). Тогда любой набор значений входящих в это выражение величин, при котором условие истинно, можно называть «паролем» охраны. Понятно, что паролей м.б. и больше одного — это зависит от выражения (вида условий, значений входящих переменных и констант).
-Проще говоря, нужно перейти от деления схемы соединителями к делению разветвителями. Фактически они присутствуют в «петле силуэта», но их условия (охраны) имеют смысл исключительно проверок совпадения значений адреса целевой ветки и имени текущей. Возможность и логической укладки (исключения межветочных БП), и отказа от явных БП в теле схемы даёт //**цикл Дейкстры**// (далее - ЦД) как иная форма универсальной программы. Это можно видеть на схемах ниже.
-{{ :jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:st_drakonsu_-_ocenka_texnojazyka_i_ishm_html_6ead9a8e.gif? |}}
-Для упрощения силуэт мы показали одноадресным и без дополнительных входов.
-Здесь фактически вводится новый тип устремлённого планарного графа, называемый //дейкстралом//. Он обеспечивает универсальность за счёт того, что ЦД-ветви можно выбирать в любом порядке (пока мы не вышли из цикла). Если представить, что телом каждой ветви служит простой шампур-блок (отдельный линейный участок) схемы алгоритма — скажем, примитива, — то это значит, что мы можем организовать в ЦД любой из порядков выбора, возможный в этой схеме.
-В силуэте реален как циклический (действительно идёт против шампура) только один переход — с конца на начало силуэта, когда он «зацикленный» (реагирующий). Остальные переходы на главном маршруте силуэта реально идут по шампуру. Поэтому разветвления для выбора их в петле силуэта фиктивны — никаких условных переходов на самом деле для этой цели не нужно. Как следствие, адрес перехода с главного выхода ветки предопределён — всегда на следующую справа ветку. Можно считать — хотя в шампур-методе это не оговорено, ибо он исходно определён только для «слепышей» — что тексты икон Адрес для главных выходов веток назначаются автоматически по правилу «чем правее, тем позже» — соответственно и циклы по этим выходам невозможны.
-В многоадресном силуэте побочные выходы, возможные в любой неконечной (т.е. заземлённой по шампуру) ветке, могут давать как прямые, так и возвратные переходы — всё зависит от желания сочинителя, т.к. он имеет право ввести в икону Адрес любое имя ветки данного силуэта. Если это имя текущей или более левой ветки — образуется ВМЦ. Вообще говоря, такие циклы тоже нельзя образовывать произвольно, если хотя бы два из них охватывают более, чем по одной ветке. Поскольку тогда возможно пересечение циклов, что в структурной алгоритмизации не допускается.
-В дейкстрале каждый переход между его ветвями реально циклический — т.е. идущий против шампура. Потому и выбор ветви реальный — каждый раз надо проверять условие на входе каждой ветви, начиная слева, пока не обнаружится первое истинное — в эту ветвь и войдёт исполнитель на очередной итерации цикла. Задача сочинителя — так сформулировать выражения охран, чтобы выбирались ветви, нужные по условию задачи. Конечно, и тела ветвей дейкстрала не обязаны быть линейными — в них также м.б. развилки (плечи которых не выходят за пределы тела ветви).
-В принципе можно организовать внутри ветви и один или больше локальных циклов — но часто бывает удобнее замкнуть все циклы алгоритма через кросс дейкстрала. Тогда тело простого цикла целиком будет телом какой-то ветви, а тело гибридного — двух ветвей (для ДО- и ПОКА-частей).
-Принцип практической реализации всех упомянутых типов схем можно показать совмещённо, как на следующем рисунке.
-{{ :jazyk:soobschenija_o_jazyke_i_metode_ischislenija_ikon:st_drakonsu_-_ocenka_texnojazyka_i_ishm_html_7405715d.gif? |}}
-Здесь можно видеть, чем представляются вершины кросса в системе команд типичного исполнитля алгоритмов — машины с адресной архитектурой. Это команды БП — простого и с возвратом.
-Использование ЦД возможно двумя путями:
-  * вывода тела дракон-схемы или его части как ЦД в рамках ШМ-правил (как варианта вложенного цикла);
-  * модификации метода для использования ЦД-организации схем, начиная с аксиом.
-Первый путь требует только единообразного порядка вложения при выводе схемы как примитива — новая ветвь ЦД добавляется вводом дракон-атома обычного цикла как ДО-подтела цикла предыдущего уровня вложенности.
-Второй путь предполагает определение заготовки для вывода схемы как ЦД, ЦД-атома, а также операций добавления/удаления ветви (аналогично добавлению/удалению ветки силуэта).
-Определённая сложность логической укладки в том, что структуру нужно логически выводить изначально, пользуясь методами т.н. доказательного программирования. Для неподготовленного сочинителя это может представлять известную проблему. Возможны следующие пути её решения:
-  * пользоваться известными методами формальной спецификации задачи, хорошо разработанными и допускающими эргономизацию;
-  * приводить разработанные силуэты и/или лианные макроблоки к форме ЦД.
-Среди первых можно выделить т.н. [[http://forum.oberoncore.ru/viewtopic.php?p=52313#p52313|автоматное программирование]]. Спецификации конечными автоматами естественны для задач управляющего (реагирующего) рода и рядом специалистов считаются наглядными.
-Показано, что дракон-силуэт можно преобразовать в ЦД-схему. Тем самым ЦД-укладка обратно совместима с силуэтной. Т.е. можно переводить «силуэтно-унаследованные» визуализации алгоритмов и потоков управления программ в ЦД-запись.
-Важное преимущество ЦД как замены силуэта в том, что его ветви имеют один выход. Тем самым отпадает нужда в ШМ-операции «заземление лианы». Кроме того, в рамках доказательного программирования Дейкстрой, Виртом и другими исследователями было показано, что в теле ЦД также не нужно употреблять явных БП, чтобы получить те же маршруты, что и с их использованием; соответственно не требуется операция «пересадка лианы». Как следствие, редактор, реализующий только логическую укладку, м.б. упрощён в плане как алгоритмов, так и структур данных; очевидно, это даст большую его производительность.
-Другое преимущество в том, что доказательность достигается с участием текста вершин. Тем самым сочинитель уходит от частичной корректности программы в визуализированной форме (которую только и обеспечивает ШМ, как указывал Паронджанов) к полной. Но визуализация может облегчать правильное построение программы и проверку корректности.
-===== Разметка схем и гибридные техноязыки: ДРАКОН начинает, ГРАФИТ выигрывает =====
-В ШМ она, по сути, не рассматривается. По определению это исчисление «слепышей», т.е. неразмеченных графов (без учёта текстоэлементов синтаксиса схем). Однако на практике возникает необходимость по крайней мере в двух типах разметки шампур-схем:
-  * для выходов развилок — надписями «да»/«нет» при выходных рёбрах;
-  * для веточных макроциклов (ВМЦ) — какими-нибудь индексами, позволяющими отличить разные ВМЦ в одном силуэте.
-Первый тип можно реализовать и иначе — вершинами, несущими надписи. Такое решение можно видеть в предложениях Рэйлвей Кагена для его ПРОТОН-нотации. По сути, такие вершины — эквиваленты икон ''Вариант'' в макроиконе ''Переключатель''.
-Второй тип может иметь синтаксис, предложенный некоторыми пользователями техноязыка и показанный у Паронджанова(см. выдержку в [[http://forum.oberoncore.ru/viewtopic.php?p=57898#p57898|этом сообщении]]). В веточные соединители добавляется поле индекса ВМЦ.
-По Паронджанову предлагается разделять шампур- и гибридную формализацию императивных знаний. В первом случае определён т.н. маршрутный граф-язык «слепышей», представляющий только управляющие знания — т.е. структурную часть императивной составляющей знания — для любых существующих и мыслимых чисто текстовых языков (узко императивных или содержащих императивную составляющую). В этом понимании маршрутный язык есть полиязык для текстовых. Во втором определяется гибридный техноязык путём:
-  - выделения в чисто текстовом языке управляющей части и замены её на маршрутный язык (синтаксис «слепышей»);
-  - разметки остальным содержанием текстового языка вершин и рёбер «слепыша».
-Выделение управляющей части может оказаться нетривиальной задачей; её наличие определяется высотой абстракции языка от алгоритмического исполнителя (машины или арифметической модели алгоритма).
-Управляющие знания логически есть одна часть из двух (структурной и атрибутивной) в одной составляющей из четырёх (императивной, декларативной, активностной и обобщающей). Это следует из известного тезиса Н. Вирта (программа = алгоритм + структура данных + систематическое представление об исполнителе; см. в [[http://forum.oberoncore.ru/download/file.php?id=1881|этой статье]]), а также из факта существования т.н. [[http://ru.wikipedia.org/wiki/Парадигма_программирования#.D0.A0.D0.B0.D0.B7.D0.BB.D0.B8.D1.87.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|парадигмы программирования]] как способа увязки частей описания программы (по Вирту) в единое целое. Однако синтаксический объём этих частей в разных языках не обязательно одинаков. Существует и [[http://forum.oberoncore.ru/viewtopic.php?p=71247#p71247|подход В.Ш. Кауфмана]] — язык программирования определяет данные, операции и их связывание.
-Проще говоря, любой язык программно строгой формализации распадается на ряд подъязыков, один из которых играет интегрирующую роль. И нужно определить синтаксис каждого языка. Создатель техноязыка указывает на необходимость единых правил построения объектных имён, информативных и удобных для восприятия; для этого нужна и достаточная длина имени:
-//«...множество 32-символьных идентификаторов образует весьма выразительный, хотя и своеобразный, язык, законы и правила оптимизации которого ещё предстоит открыть, обсудить и подвергнуть экспериментальной проверке.»// /Как улучшить работу ума, с.163/.
-В то же время командная часть императивного подъязыка (так сказать, «имена действий») также должна иметь текстовый синтаксис. Нужен и синтаксис их сочетания в дракон-вершинах.
-Определённое достоинство такого пути (можно сказать, частной гибридизации) в его простоте — определение гибридного языка можно получить без больших видимых усилий. На практике же проявляются недостатки. Их можно объяснить, исходя из сказанного выше при обосновании языка и метода.
-Во-первых, неуправляющее содержание языка, полного в смысле Вирта и парадигмы программирования, как нетрудно видеть, логически составляет семь восьмых от всего содержания любого описания на этом языке. Поэтому объём разметки м.б. весьма значительным. Практически в любом случае возникает «перекос» в сторону текста в гибридной схеме, что может умалять эргономический эффект от визуализации маршрутов.
-Во-вторых, для некоторых парадигм, не императивных по своей сути, возможность выделить управляющую часть вообще неопределённа. Это возможно для языков высокой абстракции, тяготеющих к дескриптивности («ЧТО-формализации»). В частности, тех или иных языков спецификации программ/задач.
-В-третьих, существует часть знания, отражаемая в формальном тексте неявно. На это, в частности, указывал И. Ермаков при обсуждении визуализации [[http://forum.oberoncore.ru/viewtopic.php?p=68824#p68824|здесь]]. При буквальном переводе части текстового синтаксиса в графику нет оснований полагать, что эта часть станет явной.
-Преодолеть недостатки частной гибридизации можно следующим образом:
-  * визуализировать в каждой составляющей текстового языка её структурную часть;
-  * рассматривать парадигмы «ЧТО-формализации» на предмет выделения их структурной части и нахождения структур графов, формально и эргономично представляющих эту часть;
-  * выявлять содержание, не отражённое в конкретном языке явно, и находить средства его выражения.
-Тем самым определение гибридного языка на базе только дракон-схем для языка программирования или спецификации м.б. лишь началом гибридизации.
-Безусловно, путь, намеченный Ермаковым, требует и теоретических изысканий, на что он [[http://forum.oberoncore.ru/viewtopic.php?p=26640#p26640|также указывал]].
 ==== Доалгоритмическая формализация: хороший командир указывает, ЧТО, но не указывает, КАК ====

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

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

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

Различия

Инструменты страницы