DRAKON.SU

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

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

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

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

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


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


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

Совершенно согласен. Тоже коробит и тоже хочу того же

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

Да.

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

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

Я про Фому, Вы про Ерёму

Ну, давайте развёрнуто рассмотрим какую-либо методологию проектирования программных систем, хотя бы UML. Со столь любимыми диаграммами состояний. Разве кто-нибудь укладывает ВСЮ систему в одну диаграмму? Напротив, строят много мелких диаграмм... В соответствующих уровнях иерархии и инкапсуляции... То есть, с точки зрения проектировщика, на каждом уровне, на каждой диаграмме он имеет дело с информационной моделью, в которой состояния и процессы НЕ ФИЗИЧЕСКИЕ, а виртуально-абстрактные, и их содержание зависит от способа декомпозиции проекта, а вовсе не от того, какие переменные состояния (биты!) реальной исполняющей системы лежат в её основе.

Поэтому всё, что Вы сказали про переменные состояния и процессы, абсолютно справедливо, но практически малоприменимо. Всё равно что моделировать прорастающее зерно по отдельным атомам. И что дальше?

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

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

Посмотрите с такой точки зрения: алгоритм - это описание поведения некоторой системы (уже параллель №1 - автомат тоже позволяет описать поведение. Ладно, это само по себе малозначимо).
Поведение - это все возможные последовательности действий, которые мы можем ожидать от системы в разных ситуациях.
Т.е. описание поведения может служить а) генератором последовательности б) анализатором соответствия конкретной последовательности описанному поведению.
(параллель №2 - последовательность, её генерация и анализ - ничего не ассоциируется?).
Наконец, формально введу автомат поведения: основой для разбиения на состояния возьму множество последовательностей действий, которые можем ожидать далее от системы. Т.е. состояние характеризует дальнейшее поведение системы (как множество возможных дальнейших последовательностей действий).

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

Вероятно лучше говорить о характеристиках, а не о состояниях. В таком случае последнее предложение уже тавтология.

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


Кем декларированных, чьих целей? В каком начале, когда?


Да.


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


А какой "предмет" Вы считаете рассматриваемым? И какие уровни абстракции?


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


Точно.


Да что Вам так дался эта UML... Где и когда появился UML, и где и когда граф конечного автомата (очень задолго до UML).


Все это хорошо и замечательно, и правильно, как и многое другое в Киеве , но я как-то больше все об огороде...


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

Только это - разные вещи. О чем я пытаюсь тут писать.

По форме - безусловно, разные.
По сути - то же самое

Правда, глубина такой сути делает её не очень полезной практически

Но, если забыть об этой сути в теоретическом анализе, то легко заблудиться и уйти не туда, и иметь вполне осязаемые практические проблемы.

Вот почему мы и хотим заново проложить дорогу от сути к практике... Актуальная задача, между прочим!
Вот Паронджанов сделал свой эмпирический шаг "снизу", пусть методом тыка, но всё равно полезно.
Вот Илья подходит к вопросу "сверху", может, что и в теории выйдет новое!

Поэтому лучше примите посильное участие, чем доказывать очевидные вещи... Тем более что в такой формулировке Ваш тезис очень напоминает спор о том, что лучше, метры или футы...

Вот именно, что по сути - разные.
Принципиальный момент.

Вот, сошлюсь опять же на постороннее мнение:
Общие понятия

И опять Вы те же самые примеры. Правильные. Но не про то. Ну при чём тут программная реализация автомата?

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

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

Меня интересует именно этот автомат. Автомат событий алгоритма.

Не видите связи?



Зачем? Как отмечено в цитате в моем предыдущем послании, есть способы преобразования блок-схемы алгоритма в диаграмму переходов конечного автомата, и наоборот.

Довольно четко и подробно подобное преобразование описано, к примеру, вот здесь:
http://www.intuit.ru/department/algorithms/intavth/4/

А вот - просто ссылка на автоматический преобразователь графа переходов конечного автомата, изображенного в Visio, в программу на С/C++:
http://is.ifmo.ru/progeny/visio2switch/

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

Да не интересует меня алгоритм как предмет теории вычислимости. Давно изжёванный.
Интересует "физическое" понимание алгоритма как модели поведения (кибернетической) системы. (Чтобы опять не придирались - кибернетической в самом конкретном смысле. С наличием управления).

Чем поведение, которое можно описать произвольным автоматом, отличается от того, которое можно описать структурными операторами. Или Драконом, как более слабо ограниченным. (Ясно, что на памяти всё это эквивалентно. Интересен именно момент "забытия о памяти". Что можно выразить явно путями управления).

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

Функция сложности на поведении описываемом произвольным автоматом больше сложности его самого.

Если я правильно представляю смысл этого утверждения (теорию сложности не изучал), то и для автомата - аналога операторного описания - оно тоже может выполняться. Или нет?

Нет, речь и шла об их отличии. В случае операторов имеются инварианты, которые упорядочивают поведение.

Да, это важно!

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

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

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

Поскольку состояния и процессы - базовые сущности предметной области, видимо, именно из-за ясного и прозрачного всем в этой области физического смысла никакой двойственности там не возникает, и


Естественно, имеются разные графические примитивы в языке SDL для описания процессов и состояний.

Надо сказать, что у А.Н. Терехова SDL был в широком ходу (да по моему и сейчас, только под другим названием)

Да, у них целая CASE-технология - и куча диссертаций на эту тему.

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

Ув. Илья, спасибо за наводку! Интересная книга.
В тот же день разыскал в книжном магазине и приобрел.

Раньше в Сети встречал кое-какие фрагменты текстов, вошедших в книгу.

Рад, что "наводка" оказалась полезной