Конечный автомат (FSM) – инструмент программиста

[mmMike]

Да исходную статью “Конечный автомат (FSM) – ловушка для программиста” даже комментировать смысла не было. Когда увидел, что автор там рисовал что то в своих терминах и рассуждал “как он понял”.

Стало ясно что, та статья из серии “Слушал я вашего Карузо. Мне Рабинович напел. не понравился!”

[lws0954]

Тут хотелось бы услышать мнение Рабиновича. А, может, он "напел" не хуже Карузо и при этом высказал свое мнение по его поводу? Стоит ли комментировать его мнение? В том-то и дело, что"Рабинович" не только напел, но еще и что-то сказал. Вот такая примерно ситуация ;)

Кстати, вчера была оценка статьи +4, а сегодня уже +3. Кто-то, может, учел мнение "Рабиновича"?

[mmMike]

ну так с самого начала в статье “Конечный автомат (FSM) – ловушка для программиста” автор статьи изложил свое представление о теории конечных автоматов.

И сразу, стало понятно, что он “где то чего то слышал про ТКА”, но только слышал и знания поверхностные.

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

И тут же стал критиковать свое видение ТКА и предлагать что то свое, критикуя свое же представление о.

Тут же не важно правильно не правильно и в чем суть критики… Факт тот, что он критиковал свое представление о ТКА разделе математики (кривое представление, к слову).

ТКА - это инструмент со своими достоинствами и недостатками и применениями. Как и любая математическая абстракция.

[Andreas_Fogel]

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

[lws0954]

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

[eao197]

Единственная мысль после просмотра листингов кода из статьи: как же хорошо, что не приходится иметь с этим дел!

[lws0954]

Вы еще не понимаете своего счастья: Вам есть куда развиваться! :)

[eao197]

Я уже давным давно сделал то, что нужно было лично мне. И даже давным давно об этом статью здесь же опубликовал.

[rukhi7]

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

Вам осталось показать как легко ваше решение изменяется, например под такой запрос, из комментариев к моей статье Конечный автомат (FSM) — ловушка для программиста:

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

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

[misha_erementchouk]

У Вас абстракции очень абстрактные. Функция nextRec(Table) получается с сохранением состояния (statefull function). Таким макаром все программы в одну строчку получаются. Надо на телефон получить сообщение, что кошка в лоток сходила?

doStuff();

Надо рак продиагностировать?

doStuff();

Без всяких заумностей, портируемо, масштабируемо и т.п.

[rukhi7]

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

[misha_erementchouk]

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

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

[rukhi7]

Например, переключение того же светофора можно организовать как инкремент по модулю три.

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

Вопрос стоит так: называть это конечным автоматом или нет?

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

[misha_erementchouk]

В простом случае переключения идут по циклу. Сделайте не по модулю три, а по модулю 50. Пусть это значение записано в переменной state. Времена задержек и всякое такое можно и как LUT организовать tableColor[state], GPIOlevels[state], и можно явно вычислять, tableColor(state), GPIOlevels(state). Это проблем не создает.

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

[lws0954]

Все тяжело и заумно, когда не знаешь. Например, для меня очень тяжелы и заумны новые языки программирования. Просто потому, что я их не знаю, а не знаю просто потому, что они мне не нужны, т.к. есть великолепный С++. Тут я думаю все понятно.

Теперь о решении. Автомат - это управление программы. Оно может быть сколь угодно, сложны, большим. Это такая универсальная модель, которая оперирует запуском определенных функций - предикатов и действий.

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

Кстати, если заметили, то выделенное управление позволяет изменять алгоритм, не трогая остального кода. Кстати, Ваше решение близко к этому - можно менять программу управления (Ваш цикл), не трогая код таблицы.

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

.

[misha_erementchouk]

Вопрос неспециалиста. Разве в первом листинге весь автомат не спрятан в мистическую функцию nextRec(Table)? Называть это или не называть автоматом - дело вкуса, но где-то состояние должно же быть. Так-то программа

while(true)
{
	setDevice(tablRec);
    tableRec = pollBlock(tableRec);
    tableRec = Table.nextRec(tableRec);
}

вообще что угодно описывает.

[rukhi7]

а вы думаете если исполнять вот такую таблицу:

LArc TBL_TraffikRukhi7[] = {
    LArc("s1",		"s2","--",	"y1"),      // начало. 1-я строка
    LArc("s2",		"s3","--",	"y2y3"),    // цвет; таймер
    LArc("s3",		"s4","--",	"y4"),      // след строка
    LArc("s4",		"s2","x2",	"y1"),      // на 1-ю строку
    LArc("s4",		"s2","^x2",	"--"),      // очередная строка таблицы
    LArc()
};

то там внутри где вам не показывают как-то по другому сделано?

Эта таблица и работа по ней у вас не вызывает вопросов?

[misha_erementchouk]

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

ЗЫ А не, вспомнил, у меня тут устройство в трех состояниях может быть. В конце концов, реализовал явно автоматом.

[lws0954]

А какие здесь могут быть вопросы. Это известная табличная форма описания автомата. Что не ясно-то?

[lws0954]

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

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

[misha_erementchouk]

действие "взять следующую строку таблицы"

Следующую по отношению к чему? Это означает, функция nextRec(Table)внутри себя содержит переменную состояния и возвращает некую функцию от нее. Как именно она по текущему внутреннему состоянию получает следующее зависит от конкретной реализации nextRec(Table). Эта реализация может быть, в том числе, в виде кода, демонстрирующего конечный автомат.

[rukhi7]

А вот программа - это уже вычислительная модель. 

Это аргумент такой? Это многое объясняет.