Автоматы Вагнеров 002
Автомат, зная, в каком состоянии он находится, действует в зависимости от состояния и поступающей информации.
Состояния представляют ситуации, в которых, как считает разработчик, может когда-либо находиться конечный автомат == сценарий.
Конечный, потому что число состояний конечно.
Железяки и софт
Если возьмем две книги, которые имеют в своем названии «Теория автоматов», но одна книга написана для разработчиков аппаратного обеспечения, а другая — для программистов, у нас сложится впечатление, что существуют две разные теории автоматов.
Книга по аппаратному обеспечению посвящена проектированию цифровых систем.
Книга по программному обеспечению посвящена математическому описанию вычислений, особенно языков программирования.
В методах проектирования используются только детерминированные автоматы.
Одна модель КА
специфика программного обеспечения относится к среде спецификации, а не к модели конечного автомата. Модели конечных автоматов в книге не являются аппаратными или программными, поскольку существует только одно понятие конечного автомата, независимое от его использования.
Машина
Конечный автомат — это машина принятия решений.
Не упутайся в двух соснах.
Различие между
- логическими ошибками (относящимися к управлению приложениями) и
- ошибками кодирования программного обеспечения.
Первым шагом
к более эффективному использованию конечных автоматов в проектировании приложений является понимание и принятие разделения между потоками:
- данных и
- управления.
на уровне спецификации приложения мы должны думать в первую очередь о приложении и построить поведенческую модель, которая отделяет управление от обработки данных.
Троица
Традиционный подход, рассматривающий цифровой ввод (0 или 1) как простую логическую переменную, терпит неудачу в неопределенных ситуациях - когда на вход пришло и не 0 и не 1.
Расширим булеву алгебру - добавим управляющее состояние ХЕЗ - получим полное описание цифрового входа.
РасширьКА
Часть программистов при фразе конечный автомат вспоминают:
- автомат синтаксического анализатора (распознаватель, акцептор).
Для проектирования программ задействуют такой автомат:
Σ, Γ, S, s0, δ, ω〉, где:
Σ — входной алфавит (конечный непустой набор символов).
Γ — выходной алфавит (конечное непустое множество символов).
S — конечное непустое множество состояний.
s0 — начальное состояние, элемент S.
δ — функция перехода состояния: δ: S × Σ → S.
ω — выходная функция.
Если выходная функция является функцией
- состояния и входного алфавита (ω: S × Σ → Γ), это определение соответствует модели Мили.
- состояния (ω: S → Γ) Мура.
Обе модели пригодятся.
Управляемые событиями конечные автоматы ( Глава 7 Заблуждения о FSM) приводят к явлению взрыва состояния и не имеют практической ценности для проектирования программных приложений.
Превозмочь процедурное ООП.
приложение и его программная реализация — это две разные вещи — мы можем использовать разные концепции для их спецификации.
Неизбежность
Конечный автомат — это не эвристическая модель, которую можно было бы интерпретировать по-разному, по прихоти пользователя.
Относительно легко изобрести методы верификации, чтобы доказать правильность системы, построенной как система конечных автоматов. Вероятно, конечный автомат является единственной известной моделью (из многих, используемых при разработке программного обеспечения), которая действительно дает разработчику возможность проверить систему управления, и, таким образом, это единственный способ создать надежное управляющее программное обеспечение.
А смысл?
нет никаких разумных оснований полагать, что кодирование поведения системы управления без какой-либо формальной модели может привести к созданию лучшего программного обеспечения, чем система, основанная на конечных автоматах.
Наивный обмен сообщениями.
часто мы видим системы конечных автоматов, которые построены как отдельные блоки с неким каналом связи между ними, который позволяет любому конечному автомату обмениваться сообщениями с любым другим конечным автоматом.
Это наивная концепция, основанная на излюбленной структуре программистов: иметь систему, в которой каждая часть может отправлять сообщение другой части.
Удивительный факт заключается в том, что мы знаем, по крайней мере, 30 лет, что такого рода решения приводят к тупикам и подобным временным проблемам. Изобрели хорошие модели, такие как сети Петри, чтобы проиллюстрировать эти трудности. Во всяком случае, иногда мы забываем об основных правилах.
Другое сравнение — построение системы взаимодействующих автоматов без каких-либо ограничений по коммуникации — напоминает программирование с помощью «go to».
Отправка неограниченных сообщений на другой конечный автомат похожа на переход к другой части программы (Dijkstra8 показал нам 30 лет назад последствия такого «стиля программирования»). Точно такую же проблему порождают неограниченные системы конечных автоматов.
Блок-схема не является конечным автоматом
На БС нет состояния.
Без состояний программист погрязнет в отладке поведения десятков, сотен флагов (ведь ему нужно помнить состояния всех флагов - они хранят информацию о прошлых изменениях входных данных и используемых ресурсов).
Блок-схемы были первоначально введены для описания потока кода на ассеблере.
Ассемблерную программу было действительно трудно читать, даже если она была хорошо прокомментирована.
Следовательно, презентация блок-схемы была полезной.
Даже для языков программирования высокого уровня может иметь смысл описывать некоторые части программы в определенных ситуациях с помощью блок-схем.
Но и в этом случае мы должны отметить, что они не являются средством для полного описания программы.
Это способ начать работу, или для документации, или для объяснения какой-либо концепции учащимся.
Мы можем сделать БС для процедуры, но можем ли мы представить себе тысячи страниц блок-схемы с перекрестными ссылками между страницами?
Блок-схема принадлежит к бесчисленным средствам, которые фальсифицируют реальность: как будто мы действительно можем сделать с ней что-то серьезное.
Мы склонны злоупотреблять тем, чему научились. Мы наблюдаем это явление при использовании языка программирования.
Ричи и Керниган не предполагали, что C будет использоваться для написания таких больших программ, как это делаем мы.
Небрежное использование указателей, которые указывают «неожиданно» на что-то странное, является основным примером.
Блок-схема испытала аналогичный эффект: это хороший инструмент для определенных целей, но это не значит, что она всегда идеальна для описания сложной системы управления.
Сети Петри и диаграммы переходов состояний — последовательная блок-схема IEC 61131-3 типична в этом отношении — и они могут быть очень полезны для документирования намерений, но такие нечестивые комбинации могут быть опасны для использования, поскольку они отбрасывают любую теоретическую строгость их различных концепций.
Их следует использовать только для довольно простых проектов, а не для проектов, в которых может потребоваться использование десятков или более конечных автоматов в системе.
Концепции Statecharts.
Диаграммы состояний расширили модель конечного автомата элементами, которые делают ее совершенно другим инструментом моделирования.
Проектирование начинается с одного состояния, которое может быть расширено на несколько субсостояний, причем каждое из них снова расширяется до дополнительных субсостояний.
Следовательно, вместо того, чтобы иметь дело с несколькими конечными автоматами для сложной системы, мы всегда остаемся в одном конечном автомате, расширяя подсостояния.
Для реализации этой идеи Statecharts вводит несколько дополнительных понятий, некоторые из которых довольно сложные:
диаграммы состояний отличаются от конечных автоматов не только тем, что вместо окружностей используют прямоугольники со скругленными углами для состояний, но и как действительно иной способ задания поведения последовательных систем.
Концепция Statecharts возникла в попытках спроектировать сложную систему авионики и определить ее поведение как конечный автомат.
В ходе этой работы диаграмма перехода конечного автомата стала удивительно сложной, покрывая всю стену комнаты, и участники решили, что они «доказали», что с классической диаграммой переходов невозможно работать!
Они пошли в неправильном направлении, упустив возможность построения систем из подсистем или компонентов, так что каждая из них сама по себе была достаточно маленькой, чтобы ею можно было управлять.
Уроки «структурного программирования» предыдущих двух десятилетий были забыты в данном случае.
Statecharts иногда рассматривается как замена концепции конечного автомата.
Апостолы UML пытаются убить все, что не вписывается в их мир), либо просто невежество.
Прямого перевода между системой конечных автоматов и представлением системы управления Statecharts не существует.
Statecharts используется в UML для спецификации поведения и не слишком полезна для создания программного обеспечения.