DRAKON.SU

Текущее время: Четверг, 28 Март, 2024 23:47

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 188 ]  На страницу 1, 2, 3, 4, 5 ... 10  След.
Автор Сообщение
СообщениеДобавлено: Пятница, 27 Апрель, 2018 18:43 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
http://www.cyberforum.ru/post12344800.html
http://www.cyberforum.ru/algorithms/thread2235975.html
Цитата:
CoderHuligan
727 / 436 / 132
Регистрация: 30.06.2015
Сообщений: 2,302

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

Эта теория возникла на западе, и продвигалась Дейкстрой, Виртом и др. Однако следуя этой теории невозможно создать ЛЮБОЙ алгоритм.

У нас в России, в университете ИТМО, профессором Шалыто была создана своя теория автоматного программирования, которая наголову разбивает всю ложь структурщины.

Тут можно ознакомиться с этим. Под автоматы заложена строгая математическая база и за ними, без сомнения - будущее.

Попытки как-то облагородить древнюю теорию структурного программирования путём применения визуального представления алгоритма ошибочными средствами, типа диаграмм Дракона, обречено на провал. Почему?

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 28 Апрель, 2018 12:09 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 219
Откуда: Казань
Да, критика некорректная. Дракон не основан на теории структурного программирования и позволяет создавать неструктурные конструкции. Но утверждается, что Дракон основан на "теории двумерного структурного программирования", может быть из-за этого возникло непонимание.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 05 Май, 2018 18:43 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
В общих чертах, без буквоедства и акцента на пафосе, тамошняя критика корректна.

Вспоминается смежная тема -- "Язык ДРАКОН, метод Шалыто и метод Ашкрофта-Манны":
https://forum.drakon.su/viewtopic.php?f=142&t=5724
Цитата:
1. В статье 1996 года Анатолий Абрамович Шалыто сравнивает свой метод с методом Ашкрофта-Манны и делает вывод, что метод Шалыто удобнее. Шалыто не сравнивает свой метод с языком ДРАКОН, так как ДРАКОН тогда был практически неизвестен.
2. Потом Анатолий Абрамович Шалыто узнал про ДРАКОН, но, по-видимому, предположил, что ДРАКОН не отличается или мало отличается от метода Ашкрофта-Манны. И снова сделал вывод, что метод Шалыто лучше.
[...]

Я узнал об этом, когда прочитал критическое замечание:
Цитата:
Язык программирования "Дракон" (http://ru.wikipedia.org/wiki/ДРАКОН_(алгоритмический_язык)). Зачем управляющие алгоритмы описывать так громоздко (http://www.youtube.com/watch?v=Ua9dUUON ... e=youtu.be), когда есть автоматное программирование (http://is.ifmo.ru/), в котором используются схемы связей и графы переходов (http://is.ifmo.ru/books/_book.pdf). Что применять схемы, похожие на схемы алгоритмов, применять нецелесообразно, показано здесь (http://is.ifmo.ru/books/djvu/pdf/A009.pdf).

Приглашаю начинающих аспирантов и соискателей исследовать этот вопрос и на эту тему написать и защитить диссертацию. Тема благодатная.
Я готов консультировать и помогать.
[...]
Владимир Даниелович, не переживайте) У Анатолия Абрамовича все хуже, нежели его метод) Ничего страшного, просто авторская любовь к детищу.
[...]
Андрей Александрович, дело сложнее.
Мне кажется, надо сопоставить метод Шалыто и язык ДРАКОН. Не просто сопоставить, а попытаться объединить эти две идеи.
Первым эту мысль высказал Мазница в Фейсбуке.
Это тема самостоятельного исследования, отдельной диссертационной работы.

Что-то желающих для диссеров пока незаметно. Но кратко сопоставить метод Шалыто (и некоторые прочие автоматные подходы) с "Дракон-автоматом" попытаться можно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 05 Май, 2018 18:54 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Ниже ссылка на указанную выше публикацию от Шалыто, но в полном объёме -- фактически, положения для основания SWITCH-технологии:
Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления (ч. 1 и 2)

Ключевое -- понимание "состояния" (как автоматного, управленческого), о чём толковалось и на форуме по ссылке в начале этой ветки. Пример графов переходов из публикации выше:
Вложение:
gr_fsm.png
gr_fsm.png [ 28.85 КБ | Просмотров: 12196 ]

Каждое состояние-вершина в первом случае детерминирована через переменную Y и предопределяет установку переменных z1, z2, t. Во втором случае состояние идентифицируется двумя переменными (бинарное кодирование).
Графы имеют некую локализованную форму (нет "громоздкости" на фоне блок-схем, о чём цитировалось ранее) -- на плоскости одновременно, единым целым, обозрима вся алгоритмическая система, состояние имеет множество входов/выходов (и шагов/петель) и они заметны, каждое состояние связано через прямой переход. Однако, есть и недостатки. Полный путь следования состояний требует отдельного построения (или развёртки, в целом существуют разные формы автоматного представления -- графовые, табличные, формульные и пр., в т.ч. направленные именно на отражение связей, включая и между автоматами). В то же время граф перехода при определенной размерности может стать трудно читаемым из-за проблем интенсивного нарушения планарности (хотя, к примеру, Р-схемы Вельбицкого остаются читаемыми и при наличии пересечений, к тому же отражают и упорядоченность).
Но первично -- явная детерминация состояния (его явное кодирование в какой-либо форме, и вариантов много), что задаёт семантику поведения с учётом всей возможной предыстории действий. Т.е. различные умолчания, возникающий неявный контекст, связанный с предысторией процессов, сводится к минимуму (из публикации выше):
Цитата:
Такая организация ... (настоящее состояние —
условие перехода — следующее состояние) соответствует нормальному
человеческому поведению, при котором, например, просыпаясь утром,
человек сначала определяет свое внутреннее состояние (жив-мертв,
здоров-болен) и лишь потом "опрашивает" значения входных
переменных (например, тепло или холодно на улице), а затем в
зависимости от значений этих переменных переходит в следующее
состояние (например, одевается соответствующим образом). Ясно, что
в этом случае поведение без учета внутреннего состояния только по
значениям входных переменных будет выглядеть странным.

Алгоритмы же в форме условно явной последовательности действий, выбора и повторений, как правило, предысторию вычислений не фиксируют (нет явного кодирования состояния), и "логика программы" предусматривает косвенный ("ручной") учёт этой истории. Ограничения структурного программирования дополнительно придают алгоритму линеаризованную форму (что позволяет упростить чтение и восприятие алгоритма). Однако, чем больше косвенных (неявных) связей (в "растянутой" последовательности действий), тем сложнее понимание (и больше ошибок). Для управляющих алгоритмов, "реагирующих" на новый вход/события, такая проблематика выражена более явно. Вычислительные же алгоритмы более детерминированы в том смысле, что новых, именно внешних, данных/событий они не имеют, на чём акцентировал и В.И. Шелехов в контексте "предикатного и автоматного программирования":
https://forum.drakon.su/viewtopic.php?f=142&t=4284#p89624

, где также упомянуто и то, что любой алгоритм может быт задан в автоматной форме, о чём указывал и Шалыто в публикации выше или вот с расширенными примерами:
Преобразование итеративных алгоритмов в автоматные

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

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

Эта теория возникла на западе, и продвигалась Дейкстрой, Виртом и др. Однако следуя этой теории невозможно создать ЛЮБОЙ алгоритм.

Здесь напрашиваются уточнения. В реальности же речь была не о полноте по Тьюрингу.
Любые алгоритмы, определяемые с помощью явной последовательности действий, выбора, повторения (и прочие произвольные управляющие конструкции аля досрочные выходы, goto и его заменители всяких мастей, и т.д.) неизбежно имеют "диалект" из-за особенностей "репертуара" исполнителя (или из-за возникающих требований при конкретной реализации на определенной программно-аппаратной платформе). О чём здесь на форуме возникали соответствующие темы:
https://forum.drakon.su/viewtopic.php?p=14996#p14996

, вместе с уточнением:
https://forum.drakon.su/viewtopic.php?f=170&t=6063&start=60#p101337

Автоматная форма же -- предельно универсальная (но всё-равно, в пределах некоторых задаваемых рамок), позволяет перейти к представлению алгоритма хоть на Си, хот на Haskell-е, хоть на FBD (function block diagram). Поэтому автоматный подход лучше адаптирован для задач универсальных спецификаций (да и формальные методы проверок/верификации, как правило, основываются на понимании систем переходов в каком-либо виде, в т.ч. и возможный анализ потока данных также является производным от композиции переходов).

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 05 Май, 2018 19:10 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Далее по Дракон-у. Вроде как, формируется (или уже сформировалась) некая "каноническая" форма автоматного подхода на задействовании механизма веток силуэта:
https://forum.drakon.su/viewtopic.php?f=142&t=4284#p78588
Степан Митькин писал(а):
Как правильно изображать конечные автоматы на языке ДРАКОН?

Илья Ермаков считает, что так:
1. Берём силуэт.
2. Каждое из состояний соответствует ветке силуэта.
3. Названия веток - это названия состояний.
4. Веток, не соответствующим состояниям, в силуэте нет.

Идея хорошая, но есть проблема.
Пребывание автомата в каком-то состоянии - это ожидание сообщения извне.
(Ожидание "символа входного алфавита".)
Но икона "Название ветки" в языке ДРАКОН не означает задержки или ожидания!

По аналогии с межпроцессным взаимодействием, предлагаю использовать для
ожидания сообщений икону Ввод.
См. viewtopic.php?f=62&t=4275#p78554

Но тем не менее идея об изображении состояний при помощи веток хороша.
С учётом этого, автомат можно изобразить так:
1. Берём силуэт.
2. Каждое из состояний соответствует ветке силуэта.
3. Названия веток - это названия состояний.
4. В силуэте ЕСТЬ ветки, не соответствующие состояниям.
5. Первой иконой в ветках-состояниях является икона "Ввод".

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

И ещё одно дополнение.
Последняя ветка является особой. Она выполняется, когда автомат останавливают извне.

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

Последняя ветка - это деструктор.

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

[...]
Вообще тут хотелось бы контрпример - когда силуэт не является автоматом (и которым из: [не]детерминированным [не]конечным)?..
[...]
Не автомат - нет циклов, не детерминированный - возможен переход на случайный адрес... как-то так
[...]
А автоматный граф разве обязан быть зацикленным?
Это было ещё и к тому, что есть "автомат задачи" и "автомат представления". Например, мы получили автоматную модель, отвечающую смыслу решения. А когда стали задаваемый ею поток управления записывать как дракон-силуэт - захотели, например, по-другому разделить. Следуя Вашему же правилу "побольше сделать веток". И этот силуэт как автомат получит "лишние" состояния в сравнении с построенным... но от этого не перестанет быть трактуем как автомат (из веток-состояний)... и решать задачу тоже?..
[...]
Я просто имел в виду, что силуэт без веточных циклов - просто примитив.
Но и примитив можно представить в виде автомата.
[...]
Ну да... вот и вопрос, а что же это за силуэты, непредставимые автоматно (наличие каковых и должно делать понятие "силуэт" шире понятия "автомат" как модель потока управления деятельности)... какими свойствами они обладают?..
[...]

Критерий разделения веток на "состояния" и "алгоритмические" всё тот же, отмеченный ранее -- явная фиксация предыстории действий/вычислений и её отсутствие (необходимость косвенного учёта истории). В алгоритме, к примеру, с самого начала ещё без действий может сложится анализ условий с возникновением пересечений линий, которое вынужденно снимается через переходы по веткам. В общем случае "обычных" веток не избежать. Неизбежны они, вроде как, и в автоматном программировании от В.И. Шелехова (в целом концепция представления автоматов пока не ясна):
https://forum.drakon.su/viewtopic.php?f=143&t=6160
Цитата:
В концептуальном плане вроде бы все просто.
Всякий сегмент кода (дуга автомата) непосредственно отображается в соответствующую ветвь Дракон-схемы.
С учетом этого образ автоматной программы на C++ надо будет соответственно разметить.
Эта разметка будет определять некоторый надязык (назовем его S), ориентированный на трансляцию в язык Дракон.

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

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

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

Пример "фиксации предыстории" как для "высокоуровневого" языка -- на Lucid Synchrone -- диалект ML для автоматного программирования по мотивам Exterel/Lustre:
Код:
let count(x) = res where
  automaton
  | Zero -> do res = 0 until x then Plus(1)
  | Plus(v) -> do res = v until x then Plus(v+1)
  end;

Выше объявлена функция (точнее, это уже не комбинаторная функция, а автомат с состоянием, как некий аналог метода объекта в ООП, где объекты содержат данные). Внутри реализации содержится оператор "automaton", напоминающий "match ... with" в ML или "case of"/"switch" в Pascal/C, где задаются "ветки-состояния". Оператор "<процесс1> until <условие> then <процесс2>" исполняет <процесс1> до тех пор, пока не возникнет <условие>, затем <процесс2>. Дискриминант состояния "Plus" содержит и параметр, и нет потребности внутри состояния разбираться, как получен этот входной аргумент (иначе нет и смысла в автоматном подходе). Связь между состояниями вырождается в понимании их последовательности. В данном примитивном примере выстраиваются Zero, Plus(1), Plus(2) и т.д. (переход осуществляется при истинном "x" -- в ином случае каждое состояние может "срабатывать" многократно, т.е. при вызове count (такт автомата) функция возвращает "прошлое" значение).
Кроме оператора "automaton", нацеленного на отражение небольших состояний, возможна и параллельная композиция самих функций-автоматов, когда "состояния" немаленькие и их лучше функционально разнести/локализовать (в т.ч. и для совместного исполнения, но не с "разорванной" логикой управления по callback-ам или "обработчикам событий" в каком-либо виде, а как средство избавления от "callback hell", включая асинхронное исполнение, т.е. с собственными исполнителями как истинно параллельные процессы, но не как "активные объекты" с политикой "монитора" над общими данными). Такой автоматный подход напоминает школу В.Е. Зюбина:
https://forum.oberoncore.ru/viewtopic.php?f=152&t=5978#p99829

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

И последнее, насчёт потребности в реализации ожидания "символа входного алфавита" для веток-состояний в модели Дракон-автомата (на чём акцентировано в цитате в начале сообщения). На данный момент трюки с иконами "ввода" и подобное есть "проколы сути в семантике" ("ввод/вывод", всё-таки то, для внешнего взаимодействия, и не уместны иконы для иных потребностей -- в примере выше для автомата данные подаются "снаружи", он сам не занимается IO):
https://forum.drakon.su/viewtopic.php?f=142&t=4284#p78600
Цитата:
Цитата:
А вот пример реального автомата на ДРАКОН-Си, который производит несложный лексический анализ.
Вместо иконы "Ввод" по бедности используется икона "Действие" с текстом "RECEIVE".

Правильно ли я понимаю, что RECEIVE считывает 1 символ из output и работает с ним до следующего RECEIVE?
Т.е. в алгоритме существуют "проколы сути" от иконы "Параметры" до икон с RECEIVE?

И понятна потребность в особых ветках-состояниях как "деструкторы", чтобы "не рисовать много лишних и однообразных путей". Также возможны и "общие" состояния -- исполняемые вне зависимости от текущего состояния (для подготовки данных для последующих тактов исполнения автомата). К тому же "хозяин автомата" может не только "завершить его работу, когда автомат находится в любом состоянии", но и выполнить типовой "сброс" -- переход в начальное состояние (возможно с коррекцией, и для совокупности автоматов). Иными словами, неизбежно имеется потребность в явных семантических конструкциях для автоматных переходов, с соответствующими правилами (они с "оттенками" в разных "автоматных" школах, включая и самые известные, начиная от всяких UML). Тем более с потребностями иерархической композиции автоматов (в частности, ведь возникает некая потребность кроме в "ветках-состояний" и в каких-то "вставках-состояний") и организации их групп (параллельная композиция -- "параллельные линии" для "вставок-состояний"?). Композиции автоматов (опять же, реализуемых в разных технологиях по-разному) есть и у Шалыто:
Switch-технология — автоматный подход к созданию программного обеспечения «реактивных» систем

Итого, ни в блок-схемах, ни в Дракон-е на сегодня нет явного понимания "управленческого состояния". И, видимо, "Анатолий Абрамович Шалыто узнал про ДРАКОН, но, по-видимому, предположил, что ДРАКОН не отличается или мало отличается от метода Ашкрофта-Манны". В самом деле, ветки в Дракон-е есть всего лишь "контролируемый goto" с метками, т.е. предназначение -- условно эргономичная помощь в реализации линеаризованного алгоритма, с косвенной поддержкой предыстории вычислений/действий (или без её фиксации). Без нарушения имеющейся семантики для выражения желаемой "шины состояний" (и не смешивая в одну кучу мух с котлетами) и остаются варианты действовать по мотивам Ашкрофта-Манны (хотя в тех краях первично ставилась задача достижения "структурности" алгоритмов) -- алгоритмически интерпретировать некие автоматные состояния, кодировать их через общую переменную (или переменные, как целочисленные/перечисления и т.п.) и выполнять анализ значений переменных через оператор "выбора" с "шиной вариантов-состояний" и т.д.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 05 Май, 2018 19:31 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
PSV100, спасибо за важные и подробные соображения.
Буду изучать.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 06 Май, 2018 08:46 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
PSV100, просьба пояснить, в чем вы не согласны со Степаном Митькиным относительно использования языка ДРАКОН применительно к конечным автоматам.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 08 Май, 2018 17:22 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Скорее, не несогласие, а возникает необходимость в уточнении понимания сути, что есть автомат.

В целом, на сегодня в IT это понятие крайне широкое и, главное (и печальное) -- крайне размытое. В исходных же теоретических положениях (упрощённо, как некий общий вариант) автомат представляется как некая функция "z=f(x)", которая возвращает значение в зависимости от своего внутреннего "состояния" (Шалыто, в частности, в основном обозначает его через Y-ки). Если у функции нет "состояния" -- комбинаторный автомат, т.е. обычная функция, детерминированная лишь входными аргументами. В рамках проектирования вычислительных ЭВМ (из-за чего развивалась теория автоматов в своё время) оперировали примитивными операциями, в т.ч. на состояниях регистров, триггеров и т.д. (и основная проблематика была в синтезе автоматов, одиночный автомат сам по себе мало интересен или полезен). Сегодня для алгоритмики лишь используются те принципы и пытаются придать алгоритмам некую автоматную интерпретацию. Но ключевое для понимания -- схема: вход -> действие -> выход, где результат может быть зависим и от внутреннего состояния (сохраняемого после каждого такта автомата).

К примеру, в рамках ООП мы можем для объектов задать автоматную спецификацию исходя из декларируемой в ООП семантики для понимания объектов как некоей сущности, хранящей состояние. Так для класса File мы можем выделить состояния:
Код:
class File
  [RAW -> READY]
  open(fname, attr);
  create(fname, attr);

  [READY]
  read(data);
  write(data);

  [READY -> RAW]
  close();
end;

, где каждая операция (метод) через атрибуты "привязывается" к виртуальным состояниям. Первичное состояние -- "RAW", в котором допустимы операции "open" и "create", после чего объект-файл "переходит" в состояние "READY". В этом состоянии возможны операции чтения и записи (виртуальное состояние объекта-файла не изменяется), и операция "закрытия" вновь переводит объект в состояние "RAW". Можем расширить декларации, напр., уточнить через какие-то операторы спецификации обязательны или нет для вызова методы read, write, уточнить их порядок вызова, если он важен и т.п.
Так объект-файл представляется неким виртуальным автоматом, которому на входе могут подавать сообщения в виде вызова методов (кстати, в ООП такая популярная трактовка методов размывает понимание фактов совершения работы и передачу "предметов труда" для неё). После отработки метода получаем результат (который может быть и "void" согласно заданным типам для методов, или же сам объект служит "хранилищем" результата). В данном случае все детали внутреннего устройства объекта не раскрываются, лишь уточняется интерфейс с учётом предыстории действий (обычно в ООП для задания упорядоченности в интерфейсах есть лишь понятие конструктора и деструктора -- т.е. только начальные и конечные операции).
И автомат в примере выше сам по себе может быть выделен отдельно, в виде графа переходов или в любой требуемой форме.

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

А в общем случае, кроме представления алгоритма как "чёрного" ящика и "серого", можем задать и полностью "белый" автоматный ящик, включая и вычислительные алгоритмы:
Вложение:
alg_evkl.png
alg_evkl.png [ 21.58 КБ | Просмотров: 12131 ]

Выше алгоритм Евклида в виде Р-схемы Вельбицкого и графа переходов по методике Шалыто (нижний рисунок) для представления вычислительных алгоритмов в автоматной форме. Последний случай имеет особенность -- "нулевое" состояние есть и начальное, и как бы конечное, в котором начинается и заканчивается вычислительный алгоритм (в целом в графах может быть много состояний, необязательно лишь два). Именно в этом состоянии подразумевается вход и выход после отработки такта автомата -- лишь в этой точке (вершине) мы подаём входные данные и забираем результат алгоритма (т.е. самого целевого автомата как такового). А в целом, в прочей каждой точке-вершине мы можем осуществлять лишь "наблюдение" -- после каждого перехода или шага (петли) алгоритм как бы виртуально "останавливается", и мы можем в вершине-состоянии прочитать значения всех необходимых переменных (возможен контекст вычислений, т.е. виртуально необходимо откатываться назад, чтобы понять состояние переменных -- зависит от особенностей конкретной нагрузки графов в каждом случае). Шалыто вводит некое понятие "наблюдаемости" для алгоритмической системы по аналогии с подобным в теории автоматического управления (при реализации алгоритма (напр. на императивном языке) в точках-"состояниях" можем осуществлять логирование значений переменных для изучения работы системы).
Если алгоритм содержит и ввод/вывод -- самостоятельная "добыча" данных -- то необходимо учитывать "ожидания" для "наблюдаемости".

Примерно такая вырисовывается "автоматная наблюдательная" обвертка-спецификация -- но это лишь некая автоматная интерпретация по мотивам "оригинальных" автоматов, где требуются соответствующие договорённости между моделирующими субъектами.

У Вельбицкого в данном случае (по картинке) схема ближе к императивному пониманию (включая явные начало и конец). Петля, задаваемая в примере в виде двойной "поглощающей" дуги напоминает цикл Дейкстры -- если проход на "поглощённых" дугах невозможен согласно предикатам, цикл заканчивается. А в целом вычислительные алгоритмы могут задаваться и с явной фиксацией предыстории в вершинах-"состояниях":
Вложение:
velb_kvadr_ur.PNG
velb_kvadr_ur.PNG [ 347.63 КБ | Просмотров: 12131 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 08 Май, 2018 17:39 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Теперь вновь по Дракон-у. Прежде всего, необходимо определиться с пониманием "автоматности". Если же потребность в "автоматной наблюдательности", где "вводом/выводом" в каждом условно зафиксированном состоянии алгоритма занимается "наблюдатель" -- это одно дело. Однако, если те же базовые Р-схемы Вельбицкого есть лишь "пустые" (семантически) графические структуры, которые можно применять для формирования своих технологических языков моделирования, то в Дракон-е "уже всё украдено до нас" -- т.е., как и в блок-схемах, семантика задана, причём в жёсткой императивной форме. В отличие от графов переходов -- нет явных точек "наблюдения". Проблематика в данном случае решается методически -- условными инструкциями для читающего: мол при чтении наблюдатель останавливается на (или перед) иконой "действие", здесь можем узнать состояние (значения) переменных, на иконе "вопрос" -- не останавливаться, а "решаем" вопрос, и т.д. и т.п. Или же "выкраивать" автоматные состояния по Зюбину (рис. 2):
http://reflex-language.narod.ru/articles/03text_vs_graph.htm

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

Уточним особенности "канонической" модели "Дракон-автомата":
https://forum.drakon.su/viewtopic.php?f=142&t=4284#p78588

По ссылке выше, согласно рисунку примера алгоритма разбиения текстовой строки на слова, получается примерно, в общих чертах, такая картина (псевдокод по Pascal-мотивам):
Код:
procedure Разбить_на_слова(текст, разделитель): список_строк;
var
  i, символ, аккумулятор, список;
begin
  аккумулятор := '';
  список := [];

  for i := 1 to len(текст) do
  begin
    символ := текст[i];

    automaton
    | Разделитель:
          if символ = разделитель then
            continue;
            moveto Разделитель
          else
            аккумулятор := аккумулятор + символ;
            moveto Слово;
          end

    | Слово:
          continue;
          if символ = разделитель then
            добавить_аккумулятор_в_результат;
            moveto Разделитель;
          else
            аккумулятор := аккумулятор + символ;
            moveto Слово;
          end
    end
  end;

  добавить_аккумулятор_в_результат;
  return список;
end;

(реализации подпрограммы "добавить_аккумулятор_в_результат" выше нет -- второстепенно). Оператор "automaton ... end" символизирует "автомат-силуэт" Дракон-а, оператор moveto -- переходы в ветки-состояния. Оператор continue -- некая вынужденная мера согласно примеру -- это особый оператор (в отличие от типового continue), необходимо понимать как начало новой итерации цикла, и как бы не покидая положения в алгоритме -- находясь в automaton при вызове continue выполняется временный выход из автомата, выполняется новая итерация цикла, и после отработки "символ := текст[i]" при входе в automaton вновь возвращаемся в исходное место (в результате вид веток-состояний чуть отличен от оригинала. И "подготовка" с "завершением" не заданы как ветки силуэта, чтобы выделить сам содержательный автомат как таковой, эти стадии задаются явно императивно согласно структуре алгоритма).
Таким образом в исходной схеме есть некая попытка скрыть внешний цикл для самого автомата (внешние "управляющие" циклы в каком-либо виде для автоматов неизбежны). Т.е. схема есть не строго по-Драконовски детальный императивный алгоритм ("без самодеятельности" и всё наглядно), а некий "протокол о намерениях" как какая-то спецификация:
https://forum.drakon.su/viewtopic.php?f=142&t=4284#p78600

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

Отмеченное выше положение, можно сказать, есть частный случай для типовых алгоритмов (для которых возникает естественное желание какого-то обобщения для удобства). Но в целом наблюдается некое семантическое перемешивание -- алгоритм выше является на самом деле то комбинаторным автоматом -- ему на вход дали текст и символ-разделитель, выполняется такт автомата (без никакого запомненного состояния по результатам проделанной работы в прошлом), и получен результат -- у алгоритма нет никаких иных вариантов для пользователей этого алгоритма. А все прыжки по goto в рамках силуэта выше -- лишь особенности реализации "действия" как условно линейного алгоритма. И силуэт в данном случае есть какой-то встроенный автомат внутри алгоритма (о чём ещё нужно догадаться), скорее, это некий "наблюдательский автомат" для изучения алгоритма, с основной особенностью -- возникает необходимость для читающего (и моделирующего) в локализации входа/выхода этого встроенного автомата (и каждого состояния) и их соотнесение с входом/выходом самого алгоритма. Т.е., согласно самой Дракон-схеме имеется глобальный (других-то и нет) силуэт как бы для самого алгоритма как такового, но на самом деле то это внутренний автомат в рамках спрятанного цикла. В случае, скажем, если "управленческий" цикл какой-то "не стандартный" (т.е. нечто иное от интуитивного перебора линейного списка/массива), то потребуется автомат явно куда-то вкладывать. Да и в любом случае скрытые, не декларируемые самой семантикой Дракон-а (подробной императивной), действия (и не простые то) не есть хорошо. Из-за отсутствия вложенных силуэтов остаётся возможность лишь применять отдельные схемы, напр.:
Код:
procedure анализ_символа(символ): строка;
var
  аккумулятор = '';
automaton
    | Разделитель:
          if символ = '' then
            yield аккумулятор;
            аккумулятор := '';
            moveto Разделитель;
          else if символ = разделитель then
            yield '';
            moveto Разделитель
          else
            moveto Слово;
          end

    | Слово:
          if (символ = разделитель) or (символ = '') then
            yield аккумулятор;
            аккумулятор := '';
            moveto Разделитель;
          else
            аккумулятор := аккумулятор + символ;
            yield '';
            moveto Слово;
          end
end;

procedure Разбить_на_слова(текст, разделитель): список_строк;
var
  i, символ, слово, список;
begin
  список := [];

  for i := 1 to len(текст) do
  begin
    символ := текст[i];
    слово := анализ_символа(символ);
    if слово <> '' then
      список.add(слово);
    end
  end;

  слово := анализ_символа('');
  if слово <> '' then
    список.add(слово);
  end;

  return список;
end;

, где автомат выделен в отдельную процедуру "анализ_символа", причём само тело вместо "begin ... end" завёрнуто в "automaton ... end" для подчёркивания семантики, выражая тем самым глобальную конструкцию силуэта. Используется оператор yield -- возвращает результат как return, но лишь приостанавливает алгоритм. Это целенаправленный приём всего лишь для примера, вместо общения через аргументы и результаты процедур можно использовать операторы ввода/вывода (запустив на исполнение условно параллельно две процедуры, они будут общаться через какие-то каналы ввода/вывода, где "Разбить_на_слова" будет управляющим автоматом). В любом случае ключевое в автомате "анализ_символа" -- каждое состояние (ветка в силуэте) принимает вход и возвращает результат всего(!) алгоритма. Реагируя на каждый входящий символ, автомат "накапливает" вычисления и выдает непустую строку тогда, когда он разобрал слово. При пустом символе на входе выполняется выдача накопленных данных и производится "сброс" ("хозяин автомата" может решить прекратить работу ("уничтожить" автомат) или начать сначала, новую серию работ).
Алгоритм-автомат "анализ_символа" явно локализован, со своим входом/выходом и внутренним состоянием. Потребность в максимальной локализации сразу же ощущается, как только задействуется какая-то композиция автоматов (аналогичная проблематика при использовании процедур/функций с глобальными переменными, даже для отдельных "автоматных состояний" напрашивается использование параметров/аргументов вместо общих переменных), если что-то используется автоматами совместно, то это должны быть специальные "провода между агрегатами" -- специализированные средства/каналы общения.
Стиль построения кода выше -- по-Драконовски детально, т.е. все переходы и паузы (передача результата и возобновление работы) указаны явно, список состояний линеен. В других языках со специализированными автоматными конструкциями иногда поступают иначе. К примеру, объявляют лишь условия перехода (т.е. явно не указывая аля "moveto" на себя же), где-то понимание "пауз" может быть неявным исходя из семантики необходимых операторов, возможны общие условия переходов для состояний (для иерархических автоматов, групп, и для примера выше напрашиваются удобные средства для обработки общего условия проверки входного символа как пустого для организации "сброса" аккумулятора вместо дублирования функционала). Или же, напр., в состоянии "Слово" нет необходимости проверять условие перехода (первая ветка оператора if) при первом такте, когда оказываемся в этом состоянии (операторы перехода могут учитывать подобные факты). Т.е. семантика именно переходов несколько отлична от типового оператора if. В адекватных технологиях не допускают каскадных переходов -- не более одного на такт. И др.
И тогда возникает автоматная спецификация для алгоритма, аналогично спецификациям для объекта-файла из предыдущего сообщения -- есть возможность как для "серого" ящика уточнить семантику поведения алгоритма с учётом фиксации истории вычислений, с особенностями продвижения по этапам. Функциональное понимание алгоритма-автомата расширил Зюбин: полиморфная функция (функция с разными вариантами поведения/реализации) с динамической диспетчеризацией на основе событий (а не типов аргументов, к примеру. Или же в Лисп-ах есть некое близкое понятие "мульти-методов" -- диспетчеризация функций на произвольных гибких условиях. Проблематика в форме организации гибкой диспетчеризации, и задача непростая).

Замечания выше не стоит воспринимать, мол Дракон-автоматы должны быть именно какими-то такими. Выше всего лишь перечислены принципы, где основное: локализация "вход -> вариант алгоритма -> выход" плюс политика переключений вариантов. И если на любой автомат смотреть как на "наблюдательский автомат", то чем больше умолчаний или возникающего контекста на основе предыстории, тем сложнее или больше усилий для построения/понимания этой локализации. Если же силуэт автомат-алгоритма на самом деле какой-то встроенный с особенной политикой, то, видимо, должна быть какая-то стандартная семантика в Дракон-е, плюс понимание, когда автомат не встроенный, а "прямой" что ли.

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

Как-то так, в общих чертах...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 09 Май, 2018 01:17 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
У вас длинные посты, PSV100. Непонятно, что вы хотите сказать.

Вот факты:

DRAKON Editor и ИС Дракон реализуют автомат Мили при помощи силуэта. Детали реализации различаются, но суть одна.

95% опрошенных мной программистов не знают, что такое конечный автомат. Ни один не применяет автоматы в повседневной работе.

Критики ДРАКОНа из числа автоматчиков никогда не программировали автоматы на ДРАКОНе.

Вот моё мнение:

Конечные автоматы на ДРАКОНе – это бомба. Жаль, что земляне этого не понимают.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 09 Май, 2018 12:01 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1356
См. https://forum.drakon.su/viewtopic.php?p=101644#p101644

Изображение


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 10 Май, 2018 19:18 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Степан Митькин писал(а):
У вас длинные посты, PSV100. Непонятно, что вы хотите сказать.

Вот факты:

DRAKON Editor и ИС Дракон реализуют автомат Мили при помощи силуэта. Детали реализации различаются, но суть одна.

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

Ниже "классический" автомат:
Вложение:
classic_autom.png
classic_autom.png [ 4.8 КБ | Просмотров: 12046 ]

, который определяется функцией вида: z = f(x), при этом заданы два состояния автомата: Y = {A, B}. Согласно схеме необходимо его понимать так:
- в начале автомат находится в состоянии А, при исполнении f(false) автомат будет продолжать находится в этом состоянии и возвращать 0;
- как только произойдёт вызов алгоритма с "истиной": f(true) -- автомат перейдёт в состояние B и вернёт 1. Теперь же автомат при вызове f(false) будет возвращать уже 1, оставаясь в состоянии В, до тех пор, пока вновь не выполнится вызов с "истиной", переводя автомат в состояние А. И т.д.

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

Если автомат не имеет состояний (вариантов поведения) -- на графе одна вершина или одна петля-дуга с действием (для Мили) -- комбинаторный автомат или обычная функция, детерминированная лишь входными аргументами. Если возникает желание это единственное действие представить более подробно, раскрыть детальнее, то в рамках автоматных спецификаций можно поступить так, как было приведено выше в теме в рамках примеров алгоритма Евклида и решения квадратного уравнения:
https://forum.drakon.su/viewtopic.php?f=142&t=6246#p101640

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 10 Май, 2018 19:24 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Вновь к примеру с разбиением текстовой строки на слова:
https://forum.drakon.su/viewtopic.php?f=142&t=4284#p78588
Цитата:
С учётом этого, автомат можно изобразить так:
1. Берём силуэт.
2. Каждое из состояний соответствует ветке силуэта.
3. Названия веток - это названия состояний.
4. В силуэте ЕСТЬ ветки, не соответствующие состояниям.
5. Первой иконой в ветках-состояниях является икона "Ввод".

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

И ещё одно дополнение.
Последняя ветка является особой. Она выполняется, когда автомат останавливают извне.
[...]
Последняя ветка - это деструктор.

Вложение:
lex.png
lex.png [ 64.36 КБ | Просмотров: 12046 ]

Согласно примеру выделяются два автоматных состояния: "Разделитель" и "Слово". Если предположить, что это "интерфейсные" состояния, задающие варианты поведения алгоритма, то тогда возникает возможность рассуждать примерно так:
- алгоритм (автомат) находится в состоянии "Разделитель", ему на вход подают текст и разделитель (осуществляют исполнение алгоритма), алгоритм возвращает результат;
- после чего алгоритм (автомат) может перейти в другое состояние ("Слово"), и при новом исполнении с одними и теми же данными алгоритм может вернуть уже иной результат, и т.п.

Соображения выше не соответствуют действительности, т.к. алгоритм является комбинаторным автоматом и не зависит от предыстории вычислений. Вот альтернативная его форма:
Вложение:
lex1.png
lex1.png [ 37.12 КБ | Просмотров: 12046 ]

, где более-менее прослеживается то, что результат алгоритма зависит лишь от внутренних вычислений в рамках всего алгоритма (такта автомата). Схема выше целенаправленно неправильна в том смысле, что нарушает правила Дракон-а -- силуэт вписан вовнутрь цикла. Однако, эта схема примерно отражает то, что на самом деле происходит в алгоритме в исходной схеме, в которой также нарушены правила Дракон-а, поскольку подразумевается некая частная трактовка семантики силуэта и оператора ввода. Силуэт, как правило, понимается как аналог совокупности меток для goto-переходов, а иконы-адреса и есть goto-операторы. В иконах ввода/вывода "драконовский поезд" останавливается (вся схема алгоритма "теряет" исполнителя, замирает, никакой закулисной работы), после завершения операции "драконовский поезд" возобновляет движение (схема вновь приобретает исполнителя).
Возможно, сказывается отсутствие каких-то встроенных силуэтов. Но в любом случае, если вводится какая-то новая семантика для языковых элементов, то, согласно принципам Дракон-а, силуэт, его линии, и необходимые иконы ввода/вывода, заголовки для особых веток (как деструктор в примере) должны иметь иную визуальную форму (поскольку линии и геометрические фигуры имеют метафоры и должны однозначно отличаться).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 10 Май, 2018 19:34 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Попробуем построить алгоритм без нарушений правил Дракон-а (как минимум, чтобы все силуэты были на месте как глобальная структура для всей схемы). Исходный алгоритм распадается на части -- на подпрограммы. Подразумевается, что они запускаются для совместного исполнения и общаются между собой с помощью каналов ввода/вывода.

Основной алгоритм, имеющий первичные входные данные и выдающий конечный результат:
Вложение:
lex2.png
lex2.png [ 20.51 КБ | Просмотров: 12046 ]

Алгоритм выше отправляет подпрограмме "Анализ символа" каждый символ в тексте. Алгоритм "Анализ символа" накапливает результаты своих вычислений и выдаёт разобранное слово после его обнаружения, в т.ч. и в случае пустого символа на входе (последняя ветка-"деструктор" оставлена в примере, но согласно имеющейся семантики Дракон-а -- это goto-метка, на которую нет переходов -- мёртвый или недостижимый код, проблематика второстепенна, в данном случае):
Вложение:
lex_analiz.png
lex_analiz.png [ 34.14 КБ | Просмотров: 12046 ]

В свою очередь, "Анализ символа" использует подпрограмму "Проверка символа для слова":
Вложение:
lex_check.png
lex_check.png [ 6 КБ | Просмотров: 12046 ]

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 10 Май, 2018 20:09 

Зарегистрирован: Среда, 03 Май, 2017 09:55
Сообщения: 200
PSV100 писал(а):
Исходный алгоритм распадается на части -- на подпрограммы. Подразумевается, что они запускаются для совместного исполнения и общаются между собой с помощью каналов ввода/вывода.

Нехорошо же, что "вызывающая" и "вызываемая" подпрограммы связаны в обе стороны.

Например, почему "Проверка символа для слова" использует ввод-вывод из "Анализ символа"?
Получается, мы уже не сможем использовать "Проверка символа для слова" для других алгоритмов.
Равно как не получится использовать эту проверку символа 2 раза в разных частях проекта.
Печально же?

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 11 Май, 2018 00:14 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
Цитата:
подразумевается некая частная трактовка семантики силуэта

Да. В.Д. Паронджанов в своих книгах не писал об автоматном силуэте. Автоматный силуэт отличается от обычного силуэта. В автоматном силуэте окончание ветки вызывает yield, как выразился Владимир Ситников. Yield этот не простой, а с несколькими точками обратного входа. Если бы был простой yield, то получился бы автомат Мура. Так как точек входа несколько, по одной для каждого входного символа, то автоматный силуэт изображает автомат Мили.


Цитата:
. если вводится какая-то новая семантика для языковых элементов, то силуэт, его линии, ..., заголовки для особых веток ... должны иметь иную визуальную форму

Может быть.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 11 Май, 2018 20:03 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Владимир Ситников писал(а):
PSV100 писал(а):
Исходный алгоритм распадается на части -- на подпрограммы. Подразумевается, что они запускаются для совместного исполнения и общаются между собой с помощью каналов ввода/вывода.

Нехорошо же, что "вызывающая" и "вызываемая" подпрограммы связаны в обе стороны.

Например, почему "Проверка символа для слова" использует ввод-вывод из "Анализ символа"?
Получается, мы уже не сможем использовать "Проверка символа для слова" для других алгоритмов.
Равно как не получится использовать эту проверку символа 2 раза в разных частях проекта.
Печально же?

В том примере я прежде всего акцентировал на смешанном представлении веток ("обычных" и с "yield"-ом), и какая в итоге возникает каша. А вот семантику каналов ввода/вывода не уточнял, видимо, исходя из обычного представления о том, что если именно подпрограммы работают совместно, то подразумеваются сопрограммы -- кооперативная многозадачность (с единственным общим исполнительным потоком, а не истинно параллельные процессы). Через каналы ввода/вывода исполнитель "перетекает" вместе с данными (но не обязательно сразу же в другой конец "провода", в зависимости от диспетчеризации). Каналы, конечно, можно "оторвать" от процессов, т.е. как самостоятельные точки связи, как в гугловском Go (но с единственным потоком для случая "кооперации"), однако в целом семантика исполнения в тех краях довольно таки размыта (вместе с пониманием моментов переключения контекста и пр.). В качестве примера адекватной реализации "фиберов" именно через специализированные каналы ввода/вывода могу указать на Felix, где вовсе "не печально" (небольшой "скриптовый" ML-подобный язык как препроцессор для С++, но сайт в данный момент чотто не пашет):
http://felix-lang.org/share/src/web/tut/fibres_index.fdoc
Владимир Ситников писал(а):
Если я правильно понимаю, то вы пытаетесь систематизировать то, как Дракон-схемы возвращают или не возвращают управление в вызывающий алгоритм (грубо говоря, вопрос о том, где в Дракон-схеме находится yield).
Верно?
Но я не увидел вывода. По-вашему этот самый yield есть? Или его невозможно добавить в Дракон?

В блок-схемах, кроме начального входа и конечного выхода (а "автомат" то может и глобальные данные изменять), прежде всего операторы ввода/вывода и есть передача данных или "yield" (даже аля чтение/запись в файл подразумевает "прерывание" либо аппаратное или со стороны ОС и т.п., с приостановкой потока и временной "передачи управления").
"Паузы", "ожидания таймеров" и т.п. тоже могут быть "yield"-ами. Или же какие-то "suspend"-процедуры, приостанавливающие ("ворующие") поток исполнения до окончания операции. Но если подобные вызовы спецфункций задавать на схемах как обычные действия, то теряется смысл графических языков, где геометрические фигуры имеют определенную метафору.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 11 Май, 2018 20:16 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
Степан Митькин писал(а):
Цитата:
если вводится какая-то новая семантика для языковых элементов, то силуэт, его линии, ..., заголовки для особых веток ... должны иметь иную визуальную форму

Может быть.

Здесь на форуме неоднократно был отмечен В.Е.Зюбин. Основные результаты:
В.Е. Зюбин. Программирование информационно-управляющих систем на основе конечных автоматов

Графический язык:
Разработка графического формализма для описания алгоритмов в процессориентированном стиле

Текстовая форма языка выглядит так (есть вариант и с русскоязычными ключевыми словами):
Вложение:
reflex.png
reflex.png [ 169.32 КБ | Просмотров: 11979 ]

Диаграммы в таком стиле (с "вертикальным" силуэтом):
Вложение:
HPD.png
HPD.png [ 86.01 КБ | Просмотров: 11979 ]

Не в курсе, насколько именно результаты Зюбина удобны/применимы в рамках целевой платформы -- контроллеров (не спец в этой сфере), но как минимум в рамках спецификаций "для кухарок" на основе блок-схем -- очень так ничего себе...

Для задач логического управления подразумеваются "логические параллельные" процессы (кооперативная многозадачность) над разделяемыми переменными (в Esterel-вариациях эта семантика не менее удобно и контролируемо расширяется и для многопоточного/многопроцессорного исполнения, включая и для задач-"числомолотилок"). Выделяются процессы-автоматы (с переключающимися функциями-состояниями) и обычные функции. Для процессов в реальности переменные глобальные все (прежде всего из-за особенностей конечной платформы), но есть дисциплина логической привязки по процессам при потребности, причём с особенностями, по-своему удобными. К примеру в примере выше есть объявления переменных и параметров в таком стиле:
INT ФП_Температура = { АЦП[16] } FOR PROC ПодогревБака;
FROM PROC Инициализация ФП_Температура;

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

Ключевое -- принципы отражения ожидания событий. Они отличаются, напр., от примеров в этой ветке форума:
https://forum.drakon.su/viewtopic.php?f=172&t=5370

Фактически, для ожидания используется типовой "if", что, в отличие, напр., от оператора "выбор" (и шины вариантов), позволяет выражать аля "join calculus" (согласно всяким "алгебрам процессов"). Т.е. не только "A or B or C", но и "(A and B) or C". Для Дракон-а расширить "if" для ожиданий можно было бы так:
Вложение:
wait_icons.png
wait_icons.png [ 3.52 КБ | Просмотров: 11979 ]

Тогда правая икона могла бы использоваться как "пауза" (одиночная, без вариантов, а в рамках "ожидающего if" таймеры доступны также, как и прочие объекты и ничем не отличаются). В оригинале (т.е. сейчас) это икона запуска таймера. У Зюбина есть стандартная политика таймеров (стартуют в начале перехода в управляющее состояние, когда и начинается ожидание). Произвольный взвод таймеров, по-видимому, при потребности ничем не отличается от прочих операций с иными объектами.
Если применить модифицированный "if" для ожидания событий, то тогда иконы ввода/вывода остаются со своей исходной семантикой для внешнего взаимодействия (причём в отношении всей подсистемы, не только конкретного алгоритма, внутри подсистемы используются общие переменные).
Для параллельных процессов вместо "параллельных линий" используются явные операции дивергенции и конвергенции потоков (пуск/стоп процессов). Для Дракон-а возможны и они:
https://forum.drakon.su/viewtopic.php?t=4275#p78554

При таком подходе ветки в процессе (потенциально в рамках Дракон-а, по-видимому, необходимо разделять типы схем -- для процесса с "автоматным" силуэтом, и обычные функции/процедуры с семантикой "каскадов по внутренним состояниям"), как правило, модифицируют общие переменные (или/и запускают/останавливают процессы, что равноценно отправке управленческого сигнала) -- так выделяется "автоматный" ввод/вывод, при переходе выполняется "yield" и обычно возникают последующие ожидания. Может быть в результате (из-за отсутствия возможности "произвольно нарезать" алгоритм) ветки могут растягиваться по высоте (не вмещаясь на экране, кстати "вертикальный" силуэт у Зюбина может быть менее чувствительный к таким эффектам, с удобной индикацией переходов вида: именно "следующее" состояние, или "конкретное"). Но, как правило, "управленческие" ветки выражают "логику верхнего уровня" -- события для смены поведения в системе, максимально близко к стилю построения автоматных переходов в виде графов. Причём, вроде как, часто прослеживается следующий стиль: ожидание события -> запуск обслуживающих процессов -> переход в новое состояние для ожидания останова этих процессов (или некоторых) и т.п.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 14 Май, 2018 09:20 

Зарегистрирован: Среда, 07 Январь, 2015 14:53
Сообщения: 1356
http://programming.iis.nsk.su/student/neifeld_nikita_sergeevich_0
Цитата:
Тема работы:
Разработка транслятора автоматных программ в Дракон-схемы
Дата утверждения темы:
07.11.2017


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 15 Май, 2018 18:56 

Зарегистрирован: Понедельник, 25 Июнь, 2012 17:26
Сообщения: 396
И очень любопытно, какое именно решение для выражения автоматных состояний на Дракон-е сформирует команда В.И. Шелехова, с учётом ожидаемой концепции: автоматное состояние -> ветка силуэта:
https://forum.drakon.su/viewtopic.php?f=143&t=6160

Причём:
Цитата:
Например, можно будет запрыгнуть на ветку условного оператора напрямую минуя проверку условия.
Возможно, появятся несводимые циклы, т.е. циклы с несколькими точками возврата на начало тела цикла.

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

Образование веток силуэта и переходы между ними намечаются интересными. И сами автоматы со своей изюминкой:
В.И. Шелехов, Э.Г. Тумуров. Технология автоматного программирования на примере программы управления лифтом
Код:
process atFloor( : #idle  : #start) {
    open -> openDoor(), set t, opened;
    opened, closeButton() or t >= Tdoor -> closeDoor(), close;
    close, closedDoor() -> decisionClosed( : #idle  : #start);
    close, blockedDoor() -> open;
}

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

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

Если в рамках икон для действий так и указывать, как: "decisionClosed( : #idle : #start)", и "прыгать" на ветки силуэта без всяких маршрутов через иконы-адреса -- уж совсем "наглость" в Дракон-е. Тогда необходим "выбор" и "варианты" с переходами по адресам, но вызовы трансформируются в стиль аля "decisionClosed()" без раскрытия результата (который отражается "визуально" в иконах, вместе с возможными данными для "передаваемых" управляющих состояний), что вызывает отличие от исходной текстовой формы (входные аргументы остаются, если таковы определены).

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 188 ]  На страницу 1, 2, 3, 4, 5 ... 10  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB