что такое диаграмма состояния
диаграмма состояния
Полезное
Смотреть что такое «диаграмма состояния» в других словарях:
ДИАГРАММА СОСТОЯНИЯ — [phase equilibrium diagram) графическое изображение фазовых равновесий при разных значениях термодинамических параметров: температуры, давления и концентраций компонентов в фазах. В случае систем, не содержащих газовую фазу, слабым влиянием… … Металлургический словарь
ДИАГРАММА СОСТОЯНИЯ — диаграмма равновесия, фазовая диаграмма, графич. изображение равновесных состояний (см. Равновесие термодинамическое) в ва в виде точек в n мерном пространстве, по осям координат к рого отложены п независимых параметров состояния рассматриваемой… … Большой энциклопедический политехнический словарь
ДИАГРАММА СОСТОЯНИЯ — (фазовая Диаграмма) графическое изображение соотношения между параметрами состояния термодинамически равновесной системы (температурой, давлением, составом и др.). Диаграмма состояния позволяет определить, сколько и каких конкретно фаз образуют… … Большой Энциклопедический словарь
ДИАГРАММА СОСТОЯНИЯ — (диаграмма равновесия, фазовая диаграмма), геом. изображение равновесных состояний термодинамич. системы при разных значениях параметров, определяющих эти состояния: темп ры Т, давления р, состава системы (концентраций компонентов xi), мольного… … Физическая энциклопедия
Диаграмма состояния — диаграмма равновесия, фазовая диаграмма, графическое изображение соотношений между параметрами состояния физико химической системы (температурой, давлением и др.) и её составом. В простейшем случае, когда система состоит только из одного… … Большая советская энциклопедия
ДИАГРАММА СОСТОЯНИЯ — (фазовая диаграмма) графическое изображение равновесных состояний вещества в виде точек в n мерном пространстве, по осям координат которого отложены n независимых параметров состояния (объём, давление, температура, (см.), концентрации веществ и… … Большая политехническая энциклопедия
Диаграмма состояния — (фазовая) – графическое изображение всех возможных фазовых состояний термодинамической системы в пространстве основных параметров состояния – температуры, давления, объема или состава для многокомпонентных систем. [Ушеров Маршак А. В … Энциклопедия терминов, определений и пояснений строительных материалов
диаграмма состояния — Геометрическое изображение фазовых равновесий при разных значениях термодинамич. параметров: темп ры, давления и концентраций компонентов в фазах. В случае систем, не содержащих газ. фазу, слабым влиянием давления на фазовые равновесия обычно… … Справочник технического переводчика
диаграмма состояния — [phase equilibrium diagram] геометрическое изображение фазовых равновесий при разных значениях термодинамических параметров: температуры, давления и концентраций компонентов в фазах. В случае систем, не содержащих газовую фазу, слабым влиянием… … Энциклопедический словарь по металлургии
ДИАГРАММА СОСТОЯНИЯ — (фазовая диаграмма), графич. изображение всех возможных состояний термодинамич. системы в пространстве осн. параметров состояния т ры Т, давления ри состава х(обычно выражаемого молярными или массовыми долями компонентов). Для сложных систем,… … Химическая энциклопедия
Проектирование диаграммы состояний UML (Statechart Diagram)
Программные решения для бизнеса
В данном занятии демонстрируется построение диаграммы состояний заявки клиента. Основные шаги построения диаграммы состояний:
Каждый переход имеет метку, состоящую из следующих необязательных частей:
Триггер-идентификатор — единственное событие, способное вызвать изменение состояния. Пропуск этой части означает, что переход происходит немедленно
Защита — логическое условие, выполнение которого обязательно для осуществления перехода. Пропуск защиты означает, что в ответ на инициирующее событие переход всегда осуществляется
Активность — поведение системы во время перехода. Пропуск активности означает, что в процессе перехода ничего не происходит
Внутренние активности (internal activities) используются для описания действий объекта, совершаемых без перехода. Список основных действий включает следующие значения:
State & Transition Diagram — что это и как применять
State & Transition Diagram (сокращенно S&T) — схема состояний и переходов. Техника для визуализации ТЗ. Она наглядно показывает, как некий объект переходит из одного состояния в другое.
Вот объект находился в состоянии А, потом произошло какое-то действие, и он попал в состояние В. Потом он попадет в состояние С и другие. Принцип не меняется, было одно состояние, стало другое.
кружочки — состояния объекта;
стрелочки — то, благодаря чему из состояния А в состояние В. Это действие, но его может совершить не только пользователь, но и система сама. Например, задача запустилась автоматически в 10 часов вечера.
Такая схема позволяет нам сразу визуально оценить, какие переходы вообще возможны и что надо протестировать. Ведь нам надо протестировать и эту стрелку, и эту. Так что стрелочки — это наши готовые тест-кейсы!
Схема состояний и переходов относится к техникам тест-дизайна. Значит, про неё спрашивают на собеседованиях. И поэтому я сделаю небольшой цикл статей по таким техникам в помощь начинающим тестировщикам. Чтобы ознакомиться с каждой техникой:
State & Transition Diagram (схема состояний и переходов) — текущая статья
Сегодня поговорим про State & Transition Diagram:
Как рисовать диаграмму
Очень важно: S&T рисуется на объект! Один объект. В идеале — на объект, имеющий аналог в базе данных продукта.
Шаг 1. Вы выбираете объект в своём проекте (рабочем или учебном, не суть).
Шаг 2. Думаете, какие у него состояния. Они не должны пересекаться, то есть: объект не может быть разом в двух состояниях, и при этом он всегда хоть в каком-то одном есть
Шаг 3. Рисуете эти состояния кружочками.
Шаг 5. Смотрите, что получилось и анализируете, есть ли у объекта другие состояния? А другие действия между текущими состояниями? Переход на шаг 2.
Кто не будет выполнять эту последовательность шагов, очень рискует вместо S&T нарисовать схему вышивки крестиком)))
Чтобы начать, задайте себе вопросы:
Какой конкретно объект вы выбрали? Как он называется? (только один!)
Какие у этого объекта есть состояния?
Основное определение состояния — «набор доступных и недоступных действий с объектом». Продукт всегда должен знать, в каком состоянии каждый его объект. Вообще, когда будете думать об объектах и состояниях, старайтесь представлять их аппаратную реализацию.
Объект — это практически всегда строка в базе данных, старайтесь абстрагироваться от интерфейса вообще, и представляйте те действия, которые вы могли бы делать с объектом прямыми запросами в базу.
Вот пример хорошей диаграммы:
State Transition на примере тортика!
В чатике моей школы для тестировщиков был очень интересный диалог по поводу рисования State Transition. Студентка рисует его для просмотра сериала и пытается разобраться, как это сделать:
— В ДЗ получила фидбэк, что сделала не схему состояний и переходов, а некую инструкцию по просмотру сериала, по факту показывающую одно его состояние — в процессе просмотра. Но суть как раз в том, что сериал из непросмотренного может быть перемещен в другие состояния, отраженные в виде разделов в личном кабинете, с помощью четырех кнопок, которые на схеме являются действиями. Больше никаких действий с сериалом пользователю не доступно (загрузка, редактирование и т.д.)
— Ну смотрите, Вы продолжаете описывать и смотреть на вещи, как пользователь, а надо как тестировщик. Сериалы из пустоты не берутся. Кто-то их закачивает. Значит, все же связка «сериала не существует» и «сериал загружен на сайт» — уже есть)
— Да, конечно, есть, но выполнять ее может очень ограниченный круг лиц, и я в процессе тестирования не могу. (студенты выбирают любой общедоступный проект и тестируют его. Разумеется, доступа в админку у них нет)
— По-хорошему у тестировщиков на это есть права) и им дают необходимый доступ.
— То есть важны состояния только по отношению к сайту, а что там с этим сериалом происходит в аккаунте уже считается как одно — просмотр? Тестировщик я без году неделя, а пользователь — много лет 🙂 Поэтому и прошу постановки мозгов.
Тут моя коллега решила объяснить рисование карты на примере. Тортика! Дальнейший диалог был просто потрясающий, не могу не поделиться им с вами (разумеется, с разрешения коллеги, все же это ее идея, а не моя). Итак, приступаем:
— Вот смотрите. Торт любите? Или другую еду какую-нибудь)
Чтобы приготовить торт, нам нужны ингредиенты, правильно? Это то, из чего он состоит. Как и наши объекты из параметров, но только в граммах.
Так вот, от того, что какого-то ингредиента будет больше/меньше, состояние торта не изменится. Он будет по-прежнему «не существует».
Чтобы его состояние изменилось — надо начать что-то с ними делать. Например, смешать, залить в форму и отправить в духовку. Тогда состояние будет «В процессе готовки».
Потом, когда бисквит испечется, мажем его кремом и украшаем. Он становится у нас «Торт украшен».
Но сразу есть его нельзя, мы ставим в холодильник, чтобы украшение застыло, а только потом мы можем его есть. После холодильника состояние становится «Торт готов». А вот дальше — разнообразие)
Мы можем съесть торт, тогда он станет «Торт съеден».
Возможно, мы уедем и не съедим торт, пока его можно есть. Тогда он станет «Торт испорчен».
Кстати, в процессе приготовления могли быть и другие ответвления. Например:
— передержали бы бисквит, состояние изменилось бы на «Торт испорчен»;
— не стали бы украшать бисквит и корж испортился бы → «Торт испорчен»;
— Ну тут-то я, получается, покупаю готовый торт. И уже размышляю, что с ним делать.
— Ок, изначально торта у Вас не было. Потом у Вас появилось состояние «Торт куплен». А дальше то, что происходит после «Торт готов» ¯\_(ツ)_/¯
Торт может быть съеден, может стать испорченным, может быть подарен, а только потом его уже съедят/не съедят, может быть выброшен. Все зависит от системы.
— То есть, я правильно понимаю?
2. Поставила в холодильник на потом
3. Передумала, достала, надкусала
4. Снова передумала, решила съесть целиком, осилила половину
5. Расстроилась и решила не доедать вообще и выкинуть
Это всё не важно и состояние торта не меняется, пока он не съеден или не стух?)
— Ну он же еще является тортом? Если его начали есть, но не закончили — можно ввести промежуточное состояние «В процессе уничтожения» =))
1-2 это торт куплен
3-4 это в процессе уничтожения
— Тогда чем это отличается от
1. Купила — добавлен на сайт/загружен на сайт/находится на сайте
2. Поставила в холодильник на потом — сохранен, чтобы посмотреть позже
5. Расстроилась и решила не доедать вообще и выкинуть — просмотр прерван/торт в помойке
— 5-е он еще в процессе.
У сериалов обычно прогресс есть, и его просто так не убрать 🙂
— либо он в процессе просмотра
Примеры S&T
Примеры диаграмм можно посмотреть в конфлюенсе (доступ открытый без авторизации). Туда я выношу хорошие работы своих студентов. Их там сильно больше, чем в этом разделе статьи + обычно там можно и сам исходник скачать, чтобы внимательно всё рассмотреть. Welcome =)
Вот некоторые из этих работ:
Ольга (объект — тест)
Кристина (Fallout Shelter)
Fallout Shelter — игра под iOS, Android. В постапокалиптическом мире несколько людей было выбрано для создания светлого будущего. Их поместили в небольшое убежище, уходящее под землю. Это убежище необходимо развивать, защищать от угроз из внешнего мира, увеличивать количество жителей, производить ресурсы, выполнять квесты.
State Transition для пина в Pinterest
Типовые ошибки при составлении карты
На примере своих студентов мы собрали несколько типовых ошибок, которые допускают тестировщики, впервые рисуя карту:
1. Вместо объекта — GUI
Очень важно: S&T рисуется на объект! Это не зарисовка графического интерфейса «открыта страница такая, открыта страница сякая». Если вы описываете разные странички GUI — это уже не S&T.
Зарисовывать страницы смысла обычно нет. Это как при рисовании майнд-карты — мы не рисуем графический интерфейс, мы описываем функционал. То, зачем пользователь вообще пришел на сайт. Это намного полезнее!
Другой вариант той же ошибки: искать билет — (результаты поиска) — открыть форму покупки — (форма открыта) — ввести данные кредитной карты — (данные введены).
2. Несколько объектов в одной карте
На прошлой картинке у нас несколько объектов: результаты поиска, форма, данные. И все — плохие. Потому что там мы явно что-то покупаем, вот это «что-то» и есть объект!
Но когда мы описываем покупку, тоже легко скатиться в несколько объектов в одной карте: «пицца в корзине», «заказ оформлен».
Товар тоже очень часто путают, потому что есть два варианта:
как на авито — продается конкретная вещь: «Нет на сайте», «Продается», «Продан».
просто «товарная позиция», как какие-нибудь носки в магазине одежды: «Отсутствует», «В наличии», «Ожидается поступление» и так далее.
Если речь о сайте типа авито, то объект лучше выбрать «объявление», будет логичнее. А вот если мы покупаем пиццу — это будет товарной позицией.
3. Несколько одинаковых состояний
Вспомните пример с тортиком:
Поставила в холодильник на потом.
Передумала, достала, надкусала.
Снова передумала, решила съесть целиком, осилила половину.
Расстроилась, решила не доедать вообще и выкинуть.
Половину пунктов можно объединить. Ведь состояние торта не меняется от того, купили вы его только что или час назад, сидите любуетесь на него, переставляете с места на место или убираете в холодильник:
1-2 это торт куплен;
3-4 в процессе уничтожения;
Другой пример — объект «пин»:
пин перенесен другим пользователем себе на доску.
Но, когда пин откомментирован или сдублирован — это тоже самое, когда он просто создан. Состояние самого пина не меняется!
товар найден при поиске
Одно и то же с точки зрения товара. Он как был, так и есть.
Плюсы подхода
Плюс рисования — это визуализация ТЗ, которая:
Позволяет увидеть, что мы упустили
На входе унылая стена текста, а мы красиво зарисовали, при этом разными цветами — вот данные попали туда, вот сюда. В итоге наглядно видим весь маршрут нашего объекта.
И пока мы рисуем его маршрут, мы можем сразу же заметить, что «Ага! Вот из этого состояния, наверное, можно вернуться ещё вот в это», то есть мы можем понять, что упускаем. А если бы не нарисовали, то даже не додумались бы до такого теста!
Минусы подхода
Не всегда визуализация делает ТЗ понятнее. И тогда начинаем думать, как это решать:
Слишком насыщенная карта — разбиваем на несколько маленьких.
Сложно поддерживать — нужна ли она вообще?
Если на диаграмме куча всего — это плохо, ведь ее главная фишка — понятность. И если мы на нее смотрим и просто теряемся в этом объеме стрелочек — значит, схема нам не помогает.
Поэтому если схема насыщенная — разбиваем на мелкие. Которые, возможно, ссылаются друг на друга. То есть вот есть верхнеуровневая схема, а вот на каждое действие есть уровни подетализированнее.
Не стоит рисовать все-все-все стрелочки. Из любого состояния можно закрыть браузер, но не надо рисовать это. Просто держите в уме, что есть кнопка «закрыть», а еще может интернет пропасть, или сервер упадет, или еще какая катастрофа случится.
На диаграмме же показываем все важные стрелочки. Если их слишком много, то придумываем, как уменьшить их количество, чтобы не переборщить, потеряв наглядность.
Инструменты для рисования
Xmind (freemind, etc)
Основной инструмент — ручка и бумага, или маркер и доска. Потому что если вам надо просто обсудить, что будет, «если из этого состояния перейти в это, и как должна система реагировать, если происходит вот то», то вполне достаточно нарисовать это от руки.
К тому же от руки получается быстрее, а иногда еще и красивее. Почему? Потому что когда мы начинаем использовать инструмент, то он нас ограничивает. Вот, нам надо нарисовать стрелочку, так, а как нам это сделать. Мы начинаем думать в стиле инструмента. Это как когда мы создаем презентации в power point, то вместо мыслей о докладе думаем, как бы назвать новый слайд.
А если бумажка рядом, можно спокойно генерить в голове идеи и условия. Что придумал? Зарисовал кое-как. Если очень хочется, потом перерисовал красиво. А, может, и так сойдет.
В любом случае смотрите сами. Если удобен какой-то инструмент — используйте его! Хорошо получаются такие схемы в Xmind или Yed, или в гуглодокументах. Попробуйте использовать несколько разных инструментов, а потом выберите тот, что больше по душе. Но в целом бумага и ручка вполне себе вариант!
Итого
Рисунок — мощнейший инструмент визуализации. Вот вы открываете статью с картинками, типа этой. На что вы смотрите в первую очередь — на картинку или на текст? Правильно, на картинку.
Поэтому я за то, что рисовать! Нарисовали? Добавили в ТЗ! Всем удобнее, даже заказчику. Ведь с картинками текс становится понятнее.
Настоятельно рекомендую рисовать диаграмму состояний и переходов. Пусть даже одноразово, маркером на доске, чтобы обсудить новое ТЗ, которое пришло от аналитиков.
Зарисовали, позвали аналитика и стали обсуждать:
— А вот смотрите, вот эта стрелочка. может нам стоит сделать еще вот это?
— А что будет, если вот так?
Кстати, лайфхак. Если зарисовали маркером и жалко свое творчество (уж больно продуктивное общение с командой вышло) — сфотографируйте и выложите в конфлюенс рисунок! Не обязательно тратить время на перерисовку =)
См также (напомню ссылочки):
Как составлять вариант использования — вариант оформления требований без рисований.
Автоматное программирование. Часть 3. Диаграмма состояний и переходов. Продолжение
Как уже было сказано, диаграмма состояний это альтернативная, более удобная форма записи программных алгоритмов. Более того, диаграмма состояний это естественная форма записи динамического процесса, в то время как алгоритмическая граф-схема это искусственная конструкция, которая уже содержит в себе особенности реализации, которые бывают очевидны и не требуют того, чтобы их указывали отдельно, либо вообще ухудшают понимание, хотя технически верно описывают последовательность требуемых действий.
Но диаграмма состояний это не просто другая графическая нотация записи граф-схемы, она обладает некоторыми отличными особенностями. На рис 1 (б, в) приведены диаграммы состояний одного и того же автомата, соответствующего исходной граф-схеме статье рис. 1 (а).
Рисунок 1 а). Исходная граф-схема
Рисунок 1 б), в). Диаграммы состояний эквивалентных автоматов, реализующих алгоритм
(а).
На рис 1 (в) приведён пример некорректной записи диаграммы состояний и переходов. Некорректность в том, что переходы выделенные красным прямоугольником определяются не только входными событиями, но и дополнительно флагом с, который для этого состояния соответствует одноимённому флагу исходной граф-схемы рис. 1 (а), из-за чего уже нельзя отслеживать состояние процесса, рассматривая только входные символы, нужно каким-то образом учитывать логику изменения флага c. Проблема даже не в самом флаге с, а в том, что логика изменения этого флага не привязана к одному только состоянию s1. Если бы события связанные с изменением этого флага были бы связаны только с s1, такой проблемы не было бы. Выделенные красным цветом переходы зависят от того, каким путём попали в s1, что противоречит определению автомата, согласно которому реакция зависит только от входного символа и текущего состояния. Назовём это принцип автоматности, чтобы ссылаться на него дальше по тексту.
Граф-схему ярко выраженной неавтоматной реализации алгоритма рис. 1 (а) не так просто записать в виде корректной диаграммы состояний, поскольку явно не определены состояния, и соответственно не определены переходы между ними. Для составления диаграммы рис. 1 (б) по алгоритму рис. 1 (а) потребовалось получить эквивалентный автомат. Методика получения эквивалентных автоматов для любой граф-схемы станет предметом рассмотрения в одной из следующих статей, сейчас ограничусь констатацией, что это принципиально можно сделать, потому что любое цифровое устройство, в том числе и любая «неавтоматная» программа, это цифровой автомат, который обладает состояниями в математическом смысле, несмотря на то, что эти состояния явно не описаны. Такие состояния подобны квантовым фотонам в квантовой электродинамике, их можно упрощённо описать: они везде и нигде конкретно, но они существуют и действуют.
В этом примере, в силу случайности, каждая ветвь граф-схемы соответствует одному состоянию. Другими словами, каждый выходной символ получается только в одном состоянии. Однако, будь логика изменения флагов иной, оказалось бы, что один выходной символ получается в нескольких разных состояниях, или если сказать иначе — одна и та же ветвь граф-схемы соответствует нескольким разным состояниям. Это ещё более сложный с точки зрения понимаемости случай.
Поскольку речь зашла о состояниях, возникает совершенно естественный вопрос: «с каким количеством состояний придётся иметь дело?». При автоматной реализации количество состояний мы задаём в известной мере произвольно, исходя из потребностей.
В случае неавтоматного подхода, количество потенциальных состояний эквивалентного автомата составляет величину до:
То есть добавление даже одной переменной определяющей поведение, типа bool удвоит количество «структурных», условно назову их «схемотехнических возможных» состояний. Многие из этих состояний — недостижимые состояния. Все недостижимые состояния исключаются автоматически, специально подобранной логикой действий над переменными определяющими поведение и предполагается, что эти действия, налагаясь одно на другое, дадут требуемый результат. С точки зрения психологии, напомню, это динамический процесс как последовательность разнонаправленных действий дающих в итоге требуемый результат. Как было сказано ранее, очень сложная форма для понимания. Неплохой аналогией отличия между автоматным описанием (диаграмма состояний) и алгоритмическим описанием (граф схема) динамического процесса может быть исследование вместо графика функции графика её производной.
В случае, когда переменных определяющих поведение немного, сложность алгоритмического описания не столь заметна, но с ростом количества таких переменных сложность восприятия алгоритма растёт экспоненциально, и угнетающе действует на психику.
Следует пояснить термин Переменная определяющая поведение. В случае неавтоматной реализации это фактически любая переменная, создающая ветвление алгоритма. В случае автоматной реализации это переменная Внутреннее состояние. В качестве переменной Внутреннее состояние может быть переменная типа перечисление, где перечислены все состояния(=просто int), или даже просто переменная типа bool если всего два состояния. Далее я продемонстрирую разные варианты программных реализаций автоматов.
Как уже было сказано в начале статьи, граф-схема это не только форма записи автомата, но и форма записи обычного алгоритма. То, что операция условного перехода изображается стрелкой перехода, думаю, не вызывает удивления, но как изобразить цикл? Допустим наш автомат перебирает прямоугольную таблицу, то есть общее число комбинаций переменных вертикального и горизонтального циклов составит m * n. значит ли что у результирующего автомата будет столько же состояний, или иными словами как записать в автоматном стиле цикл?
C точки зрения условия этого цикла значения счётчика 5,4,3,2,1 – одно и то же значение. Да, внутри тела цикла i это параметр, поведение программы отличается при разных значениях этого параметра, но с точки зрения режима работы цикла for, переменная-счётчик может принимать два значения 0 и не 0. Переменная i это так сказать псевдофлаговая переменная.
Возвращаясь к автомату обхода таблицы, отмечу, что этот автомат имеет два состояния и две псевдофлаговые переменные:
Рисунок 2. Запись вложенных циклов при помощи диаграммы состояний.
Автомат Out_text из примера в «Введении» показанный на рис. 3 представляет интерес с точки зрения событий, вызывающих изменение состояния автомата.
Рисунок 3. «Автомат отображения текстовых блоков», диаграмма состояний.
Единственное событие, которое можно рассматривать как внешнее, — конец строки, все остальные события этого автомата сугубо внутренние, они порождаются работой самого алгоритма. Однако это не нарушает принцип автоматности, рассмотренный выше, потому что все события влияющие на переход из некоторого состояния, порождаются самим этим же состоянием, то есть поведение автомата не зависит от того каким путём мы попали в это состояние.
Автоматно реализованную программу можно изобразить в виде граф-схемы, и она останется автоматно реализованной. На рис. 4. приведён пример граф-схемы соответствующей диаграмме состояний и переходов приведённой в начале статьи
Рисунок 4. Граф-схема, соответствующая автомату, описываемому рис. 1 (б)
Как видно, при записи автоматно-реализованных программ, граф-схема заметно проигрывает диаграмме состояний в отношении компактности.
Теперь рассмотрим, что отличает автоматное программирование от автоматной схемотехники.
Артефакты автоматной схемотехники.
Чтобы лучше понимать о чём идёт речь, введём две категории программных автоматов – символьные и функциональные. Символьные автоматы это автоматы, принимающие последовательность символов на входе, и выдающие последовательность символов на выходе. Это полный аналог классических абстрактных автоматов, автоматов которые собственно и рассматривает дискретная математика. Символьные автоматы используются для распознавания кодов, разбора регулярных выражений, лингвистического анализа, а так же для оптимизации функциональных автоматов, и алгоритмов в целом. Мы затронем способы их реализации далее в сегодняшней статье, и подробно обсудим в одной из следующих статей.
Этим автоматам противопоставляются функциональные программные автоматы, (буду их называть в тексте программаты) — полный аналог прикладных и управляющих программ компьютера или микроконтроллера. Это те же самые модули, подпрограммы, которые управляют периферией микроконтроллера, или выполняют какую-либо полезную работу, или реализуют интерактивную работу с пользователем, но они спроектированы и реализованы автоматно.
В автоматной схемотехнике следующим этапом после разработки абстрактного автомата является структурный синтез, когда абстрактные сигналы и состояния кодируются «живыми» битами, выбираются способы кодирования, строится логическая схема, работающая с уже закодированными битами. Функциональные программные автоматы это программный аналог структурных автоматов.
Если рассматривать функциональные автоматы исключительно с позиций схемотехники, и не видеть в них ничего большего чем структурные автоматы, то такой узкий взгляд скорее мешает. Такой подход, являющийся калькой с автоматной схемотехники даёт шаблон того, как должен быть устроен автоматно спроектированный модуль.
Рисунок 5. Общепринятый шаблон реализаций программных автоматов
Механическое копирование поведения разработчика схемотехнических автоматов, вот что я имел ввиду под словом артефакты, от которых автоматное программирование избавляется, покидая колыбель автоматной схемотехники, мы ведь имеем дело с программой. Программа чрезвычайно удобный и пластичный материал, и именно пластичность этого материала сделала его столь популярным. Программируя обычным способом, мы избавлены от рутины проектирования цифровых схем. Когда нам нужно выполнить действие, мы проверяем условие и выполняем его, и не требуется писать специальную функцию-триггер. О чём я? Можно написать так:
Единственное что могут возразить сторонники сверхформализма – при обычном программировании меньше учёта, при автоматносхемотехническом способе все биты сосчитаны. На это я отвечу, что если возникает проблема с учётом какого-то параметра, стоит создать подавтомат, который будет заниматься учётом, и освободить основной автомат от рутины. Это совет по конструктивной декомпозиции.
Драматизм ситуации, связанной с программатами, в том то и состоит, что автоматный ментальный шаблон, давая удобный инструмент моделирования и анализа динамических процессов, одновременно тяжёлой дланью доминирует над разработчиками, лишая их простых радостей обычного программирования. Это на мой взгляд одна из самых серьёзных причин того, что технология автоматного программирования не может подняться выше чем экзотическая диковинка.
Как несложно догадаться, естественный путь преодоления этой противоречивой ситуации — взять лучшее от обеих парадигм. В этом случае внутреннее состояние становится не столько указанием как обрабатывать следующее входящее событие, но оно становятся неким режимом работы. Это важно. Состояние скорей следует рассматривать как подпрограмму, в которой алгоритм находится некоторое время. При этом он может обрабатывать входные сигналы, транслировать их в выходные, никуда не переходя. Подразумевается, что в одном состоянии программат выполняет однотипную работу, всё что выходит за рамки однотипности переносится в другое состояние. Переход из состояния в состояние производится не любым сигналом, а только значимыми для этого алгоритма событиями. И эти события мы выбираем сами, исходя из выбранных нами же состояний. И соответственно, каждое состояние-режим может содержать вложенные программаты.
Рисунок 6. Конструктивный шаблон, при котором состояние это режим работы.
Но программат не находится монопольно в функции-режиме до тех пока не совершит переход. Он выполняет короткие итерации, в ходе которых контролирует обстановку. При этом приложение в целом выглядит как:
Рисунок 7. Сообщество программатов.
То есть используя программаты, мы приходим к концепции корпоративной многозадачности, только в отличии от классических алгоритмов корпоративной многозадачности, когда обычное с виду приложение само в какой-то момент обращается с какой-либо целью к ОС и таким образом возвращает управление системе, программаты изначально проектируются как программы, которые получают управление только на один шаг, выполняют его и передают управление обратно, до следующей итерации. Отличие корпоративной многозадачности и программатов формально условное, но сам автоматный взгляд на программы подразумевает их итерационный характер, поэтому не возникает таких проблем, что программат «забывает» передавать управление обратно.
Программаты могут без проблем работать и под управлением многопоточных ОС, как это показано на рис. При этом, конечно, их корпоративная многозадачность оказывается вроде как и не нужна, однако само автоматное устройство модуля сохраняет все рассмотренные выше плюсы, связанные с автоматным проектированием.
Рисунок 8. Программаты в многопоточной среде.
Поскольку программат может выполнять однократные действия, происходящие при совершении перехода, а может совершать протяжённую деятельность, находясь в одном и том же состоянии — режиме работы, то его диаграмма состояний приобретает черты и автоматов Мили и автоматов Мура. Например автомат парковочный счётчик, описывается диаграммой состояний.
Рисунок 9. Программат «Парковочный счётчик», описание совмещает черты автоматов Мили и Мура.
Пример парковочного счётчика ещё не рассматривался, однако глядя на диаграмму состояний без труда можно понять, о чём идёт речь. Обратите внимание, описание этого счётчика диаграммой состояний гораздо информативней, чем было бы описание этого же автомата сделанное при помощи текста.
С точки зрения теории, я не совершаю ошибки, объединяя в одной диаграмме состояний черты автоматов Мили и автоматов Мура. Когда нужно будет осуществить математические операции над таким автоматом, он может рассматриваться как автомат Мили. Для абстрактных автоматов, при том же функционале автомат Мили может получиться с меньшим числом состояний. Существуют математические методики преобразования автоматов Мили в автоматы Мура и наоборот.
Описанное проливает немного света на то, чем являются программаты, перейдём к способам их реализации.
Способы реализации функциональных программных автоматов.
Начнём с граф-схемы рассматривавшейся ранее, для удобства показанной на рис. 10.
Рисунок 10. Граф-схема, которую требуется реализовать.
Самое очевидное, вытекающее напрямую из граф-схемы решение «в лоб», – использовать для определения состояния конструкцию множественной альтернативы языка Си, оператор switch. При получении очередного входного символа программа определяет текущее состояние, и для каждого состояния проводится анализ входного символа, при этом для каждого входного символа задан не только переход в определённое состояние, но и выходной символ.
Подобными способами реализованы автоматы в Switch-технология и в IAR visualState.
Поскольку концепция состояний программата трактует их как режимы работы программы, в которых та может некоторое время функционировать, не совершая переходов, но в то же время продолжая свою «мелкую деятельность», то должен быть входной символ, который гарантированно не переводит программат в новое состояние (если только он не перейдёт сам, по внутренним причинам), однако активирует его каждую итерацию. Символ шаг – mStep.
Второй вариант реализации, принципиально отличающийся: сделать обработчик каждого события, как это показано на листинге
Рассмотренные выше варианты – базовые варианты, отражающие основные идеи, но они довольно громоздки и медлительны. Однако, они модифицируются безо всяких проблем в сторону уменьшения громоздкости (относительного) и ускорения работы (реального).
Модифицируем код, приведённый на листинге Вариант 2. Разобьём каждый обработчик событий Message_ixx_handler на набор функций, соответствующих каждому состоянию
Всего подразумевается что нужно States * Messages функций, хотя часть может повторяться, более того их может быть всего несколько.
Если теперь объединить все полученные методы в массив, то автомат будет работать из корневой функции-движка, и движок можно будет записать в виде.
При таком варианте хорошо реализуется схема диспетчеризции событий в обработчиках прерываний и их обработки из единого движка.
Схожий способ лежит в основе реализации шаблона boost.statechart.
Основной недостаток предыдущих двух вариантов: они артефакты автоматной схемотехники, то есть программируя таким образом, невозможно сохранить «программистский стиль» программирования, приходится использовать табличный стиль программирования, чрезмерно раздутый.
Рассмотрим что даёт табличный стиль программирования:
Немудрено, что компания IAR пошла по пути графического программирования автоматов visualState, посчитав что текстовый автоматносхемотехнический стиль программирования не для людей.
Гораздо более благодатным в плане возможностей для модификации оказывается вариант приведённый на листинге Вариант 1, если его расширить принятой концепцией состояний-режимов работы.
Пусть обработчик входных сигналов для каждого состояния (внешний switch) вынесен в отдельную функцию (функция-режим).
Все свежевычлененные функции-состояния поместим в массив, чтобы функцию-состояние можно было указать её индексом. Тогда переменная Внутреннее состояние это индекс, значение типа uint, а движок принимает вид
При кажущемся сходстве с вариантом 3, этот больше соответствует концепции программата, как набора сменяющихся режимов. Каждая функция-состояние это функция-режим, которая сама опрашивает всю требуемую ей периферию, или засинхронизованный кадр данных из периферии, и совершает переходы на основании этого, а не только на основании символа Input.
Символ Input при этом может содержать однотипные для всех программатов системные сообщения. Это означает в частности, что сама функция-состояние может быть написана традиционным, максимально привычным способом.
Этот вариант показывает более высокое быстродействие по сравнению с вариантом 1, в силу того, что каждое значение переменной Внутреннее состояние однозначно сопоставлено с функцией, которая обрабатывает это состояние, и вызов функции-состояния сводится к тому, чтобы по индексу получить ячейку таблицы, которая содержит указатель нужной функции. В то же время, при реализации варианта 1, переменная Внутреннее состояние многократно сравнивается со значениями, которые соответствуют номерам-названиям состояний.
Хотя этот вариант более скоростной, количество рутины не сокращается. Главный минус этой реализации в том, что нужно иметь и таблицу состояний, и вести параллельный учёт состояний в заголовочнике и в файле кода, причём не copy/paste, так сказать проблема двойного описания. Однако и эта проблема решается довольно просто. Модифицируем указанный пример. Вместо переменной Внутреннее состояние, которая есть индекс указателя в константной таблице, можно использовать переменную Внутреннее состояние, которая сама и является указателем на функцию-состояние:
Описанный вариант уже почти не отличается от «естественного» программирования. Это становится ещё очевидней, если представить, что внутри конструкций switch и даже вместо них можно использовать конструкции типа
От «естественного» программирования этот вариант отличается только тем, что отдельные состояния-режимы вынесены в отдельные функции. Однако, разбиение задачи на простые подзадачи-функции это один из основных приёмов любого программирования. Здесь же речь идёт только о том, что есть конструктивный критерий разбиения программы (отдельное состояние — отдельная функция), позволяющий избежать механистического, наивного дробления исходного кода: эта функция получилась большая, разделим её, например, по диагонали. Я утрирую, но когда нет критерия разбиения, оно будет либо скатываться в крайности (любой чих — отдельная функция), либо будет производиться на основе некоторого внутреннего чувства правильности происходящего, которое тренируется годами и даже тут автоматный способ представления процессов отличная помощь воображению, посколько удачно «структурирует поток сознания» в процессе разработки.
Ярким примером «естественного», но автоматного программирования является автомат tDisplay::Out_text, из «Введения». Этот автомат описывается диаграммой состояний и переходов.
Рисунок 11. Диаграмма состояний и переходов автомата разбиения текста на блоки
Как видно из этого примера, все состояния вполне можно реализовать в виде одной функции. В этом примере нет необходимости использовать оператор goto, но я добавил его к имеющимся классическими структурными конструкциями — ветвлениями и циклу. Это сама по себе ещё одна структурная конструкция программирования — переход в состояние автомата. Пару слов подробней об этой структурной конструкции.
В общем случае каждое состояние помечено меткой а переходы между состояниями выполняются при помощи структурной конструкции goto Имя_метки_состояния;
Состояние всегда начинается с метки, программа не может попасть внутрь состояния иначе как через его входную точку. Их даже можно заключить в скобки <>, и могут быть вложенные автоматы внутри одной функции(!). Но это уже чересчур. Так обеспечивается соблюдение принципа модульности, даже при работе внутри единственной функции, поэтому ничто не нарушает принципов надёжного программирования допуская использование операторов goto. Все переходы совершаются в полном соответствии с диаграммой состояний. Это позволяет вносить изменения без повышения сложности, всё как бы разложено по полочкам и ничего лишнего.
Единственный минус такого решения – когда автомат начинает свою работу, он будет находиться в нём до тех пор, пока не перейдёт в состояние Stall. Для Дисплея это даже приветствуется, но функциональные программаты в системах реализованных как сообщества автоматов рис 7, бывает, не имеют возможности работать подобным образом. В таком случае каждое состояние следует описывать отдельной функцией, как и в примере Вариант 6. Для удобства реализации программного кода, переход будет осуществляться макросом:
Этот несложный API позволяет управлять поведением автомата из функций-состояний этого же автомата.
Такие команды невозможно вызвать для какого–то автомата находясь вне этого автомата, потому что их выполнение заканчивает работу функции.
Использование описанной системы команд выполняется по схеме.
При таком варианте реализации движок автомата может запускаться не в теле функции а в отдельном потоке, так сказать «совершать шаги». В случае с дисплеем такая необходимость неочевидна, но представим, что после отображения каждого блока требуется время, чтобы новые данные обработались и после этого передавать следующую порцию. Автоматно это реализуется эффективно даже когда нет многозадачной среды. Этот пример даёт возможность представить сферу полезности автоматной реализации. В этом случае вызов Out_text заряжает процесс, движок которого периодически запускается фоновой суперпетле или в обработчике прерывания, если объём вычислений позволяет это сделать.
Описанный простой API очень удобен и весьма функционален. С его помощью можно модифицировать пример 4, и он будет выглядеть следующим образом. Движок тот же что и для варианта 4.
Этот API удобен в практическом применении, несмотря на простоту охватывает огромную часть потребностей автоматосоставления.
Такой вариант в дальнейшем называется базовая конструктивная реализация. Слово конструктивная означает, что этот способ реализации вытекает непосредственно из практического опыта, как наиболее приемлемый.
В части примеров переменная внутреннее состояние объявлена в теле функции-движка как static, но это условность. На самом деле автомат описывается классом, и эта переменная часть класса-описателя автомата. Условимся называть описатель состояния автомата и рабочие переменные этого автомата термином контекст автомата. Вопрос контекста автомата, того какой конкретно структурой описываются автоматы, имеет много нюансов. Этому вопросу будет посвящена отдельная статья.
Способы реализации символьных программных автоматов.
Напоследок рассмотрим способы реализации простых символьных автоматов. Как было сказано выше, они образуют отдельное семейство, их концепция серьёзно отличается от функциональных автоматов, они являются классическими абстрактными автоматами, и способы реализации двух семейств автоматов отличаются, хотя имеют общие черты. Пусть имеется автомат, на вход которого поступает последовательность символов a,b,c, и который выдаёт 1 в случае, когда обнаруживает указанную последовательность, и 0 во все остальных случаях.
Пусть искомая последовательность bacab. Диаграмма состояний этого автомата изображена на рис. 12
Рисунок 12. Автомат определения входной последовательности bacab.
В одной из следующих статей я покажу алгоритм автоматизированного составления таких автоматов, сейчас же рассмотрим, как максимально эффективно реализовать этот автомат. Проще всего составить двумерный массив
в котором каждый вложенный массив соответствует состоянию, а каждый элемент вложенного массива содержит индекс следующего состояния для каждого входного символа. Каждому входному символу, в общем случае сопоставляется индекс от 0 до Размер_алфавита – 1. Этот массив – классическая таблица переходов автомата. Поскольку выходной символ всегда 0, кроме единственного случая «код распознан», то таблицу выходов можно не создавать, но в случае, когда код распознан, в ячейке таблицы вместо следующего состояния, значения 0, 1,2, … будет стоять число 0xff..ff. В этом случае код возврата из движка 1, а индекс следующего состояния 0.
Движок таких автоматов описывается простой функцией, без комментариев.
Я привёл основные способы реализации автоматов. Дальнейшее развитие способов реализации связано с соединениями автоматов. Это отдельная большая тема и ей будет посвящён отдельный цикл статей.
Сегодняшний обзор подошёл к концу. В следующей статье речь пойдёт об эффективности – о тех плюсах, которые можно измерить.