DRAKON.SU

Очень спорное заявление. В таком случае более интересны визуальные нотации, основанные на состояниях (из тех же SDL, UML или ISO МЭК 61131-3). Если же протокол имеет временные ограничения - тут потребуются уже средства UML 2.0.


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

Состояние = ветка. Силуэт - чистой воды автомат. А в рамках одной ветки имеем обычное алгоритмическое управление. Мы ж тут это много обсуждали.

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

Прочитайте внимательнее:

Вообще-то, вершина графа конечного автомата не обязана быть состоянием.

Действительно, перечитайте внимательно. Подумайте над вопросом, что такое силуэт в Драконе, с формальной точки зрения? Именно КА. И если мы хотим выразить его на императивном языке, то напишем:
VAR state: INTEGER;
REPEAT
CASE state OF
ветка1: .... state := ветка2 ... state := ветка3
ветка2:
ветка3: ... state := конец
UNTIL state = конец;

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

А КА как способ синт. анализа (допуск/не допуск входной цепи знаков-сигналов) - только узкий частный случай.

Так что я не могу понять, что именно не понимаете Вы в обсуждении автоматности Дракона.

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

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

рис.4 Алгоритм "рыбная ловля" из книги Паронджанова,

где ветка завершается несколькими иконами "адрес". Жить не мешает, но конечным автоматом не является.

Если ветка не завершается несколькими иконами "адрес", то говорить об автоматности вообще не приходится. Это просто последовательная декомпозиция на ветки.



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


Чистая мат. модель - это замечательно. Но она бесполезна, пока не нагрузим её реальным, физическим смыслом. А нагружать можем по-разному, так, что математик и не признает дитятю

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

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

Да с этим всё нормально. Рисовал ужЕ(где-то тут, на форуме).

Да читал я. И прокомментировал - ерунда.

Силуэт - разновидность диаграммы ДРАКОНа. Кои по своей сути - описания потока управления (control flow, если так понятнее будет). Понимаете?

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

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

Не понимаю я, что означает в вашем представлении "формальная точка зрения".
Я Вам описал вполне прозрачно "естественную" точку зрения. Процесс и состояние - разные понятия, как ни крути и сколько слов ни городи, как Вы.


И зачем она нужна - "сколь угодно общая"? Если есть традиционная, и наиболее широко распространенная, подразумеваемая по умолчанию? Нет, я конечно, понимаю, что Вам нужно поспорить и тяжело признать собственную неправоту.


Опять принципиальная ошибка.


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

Уважаемый Илья,

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

Кстати, в блок-схемах алгоритмов и программ (естественно и у Паронджанова) прямо выделены два разных вида блоков для действий и условий. И у действия один вход и один выход, а у условия - два выхода обязаны быть как минимум. Никакой прямой аналогии, естественно, в графах переходов автоматов нет.

SWITCH-технология Шалыто описывает не все алгоритмы, а только их некоторый специальный класс.

Вот это "в общем" - нарушение строгости. Я считаю, недопустимое. Вносящее путаницу в принципиально различные понятия.

КА - сокращение слов "конечный автомат". Автомат над памятью может быть бесконечным. Кстати, у машины Тьюринга традиционно подразумевается бесконечная лента... "Физическая вычислимость всегда основана на конечном автомате" - простите, не так.

Уловка? Смысл у диаграммы состояний и управляющего графа программы - разный.

Не согласен. Дело не в личной правоте-неправоте. А в докапывании до природы вещей.


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

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


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

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

Если Вы не хотите видеть однородности понятий - Ваше право. Но упёртость в таких случаях не позволяет докапываться до глубинной сути вещей.

[quote]
Слово "состояние" у КА столь общее, что не имеет само по себе никакого смысла - реального. А грузится этим смыслом в конкретном применении.

Над памятью - да, бесконечным! За счёт бесконечности состояний памяти. Управление в машине Тьюринга (её головке) определено конечно, имеет конечное множество состояний - может быть представлено конечной таблицей правил и соотв. КА. И реализует конечный алгоритм.
Структуры управления императивного языка программирования - это автомат. Есть конечное множество состояний управления выполнением, мы всегда знаем (в отличие от декларативного п-я), в каком состоянии находимся, имеем из него конечное множество переходов в другие состояния (в зависимости от ситуации - памяти/портов. Поставьте каждой ситуации знак - и нагрузите им переход.).

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


Вы имеете в виду "оптимальна для применения в специальном классе"? Никто не спорит. По поводу "описывает" - автоматное программирование позволяет описать любой алгоритм.
А у Шалыто, как я помню, в CASE-инструменте состояние автомата нагружается обычным программным кодом, например, на С. Точно так же, как ветка у Паронджанова.


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

Допустим, процесс можно определить через смену состояний. А вот что такое состояние?

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

Так что рассуждения о "принципиальном различии" процесса и состояния... несостоятельны
Такая точка зрения может иметь место только с точки зрения конкретной формальной системы (например, UML). И эта точка зрения не представляет большого теоретического интереса.

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

Важно понять, что любая (исполняемая) программа по определению есть конечный автомат.
А вот любое формальное представление (диаграмма состояний, или потоковая диаграмма, или алгоритм) есть не более чем частная проекция КА в данной формальной системе. Ущербная проекция, недостаточная для представления системы в целом.

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

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

Вижу, ребята, что признать свою принципиальную неправоту Вы неспособны практически так же, как женщины в споре

Наводите, понимаешь, тень на плетень...

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

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

Допустим, понимаю, я для Вас - не авторитет, тогда может быть, прислушаетесь к Святославу Сергеевичу Лаврову (надеюсь, не надо объяснять, кто это такой, впрочем, на всякий случай напомню, что он - один из создателей теории схем программ)?

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

Ну что, полдень наступил? Тени рассеялись?

Простите, Илья, но ни в классических автоматах Мили, ни в классических автоматах Мура никаких операций нет.


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

О, раз такая пьянка, и раз Вы сказали "А", скажите и "Б" - то есть, расскажите подробнее всё, о чём начали говорить... если не ради флейма... то переубеждать никого не придётся А Ваш опыт может оказаться очень интересным!

Совершенно справедливо. И не вижу никаких противоречий с тем, что нами было сказано выше!

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

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

Но это всё так, в порядке флуда; а что Вы хотели сказать по существу? Мне, например, очень интересно послушать!