Журнал «Информационные технологии» об автоматном программировании
Существуют менее исследованные или менее популярные методологии по сравнению с широко применяемыми. Среди них отмечается методология автоматного программирования — это подход, предполагающий использование аппарата конечных автоматов [Шалыто 1998]. В основу проектирования программы закладывается алгоритм — конечный автомат в виде диаграммы состояний или таблицы переходов и выходов. Программисту удобно использовать в рамках автоматного программирования конструкцию switch (переключение), имеющуюся в ряде языков программирования.
В движении в направлении роста свободы программного обеспечения можно выделить три основных этапа.
Идея открытой проектной документации возникала неоднократно. Она звучала еще в концепции грамотного программирования, предложенной в 1984 году Дональдом Кнутом (Knuth D. Literate Programming (CSLI Lecture Notes. N 27).- Stanford: Center for Study of Language and Information, 1992). В рамках этой концепции программа рассматривается не как последовательность инструкций, а как литературное произведение, в котором программист описывает действия, ожидаемые им от компьютера, и вставляет в соответствующие места текста код на языке программирования.
Давно возникло понимание того, что ценность документации (например, описания архитектуры и интерфейсов) может значительно превышать ценность самих исходных текстов.
Удачные примеры открытой проектной документации можно найти на сайте СПбГУ ИТМО (http://is.ifmo.ru).
Лекция 9. Автоматное программирование: анализ задачи
Таблица состояний и переходов. Автоматы Мура и Мили. Программирование в состояниях и переходах. Построение таблиц и их представление.
Ключевые слова: А.А. Шалыто, таблица состояний и переходов, состояние, переход, автомат Мура, автомат Мили, автоматное программирование, блок-схема.
Термин «автоматное программирование» принадлежит, насколько нам известно, А.А. Шалыто. Во всяком случае, ему принадлежит заслуга его развития вопреки моде и мнению большинства.
P.S. Нонконформизм - отказ от общепринятых взглядов и отстаивание своего. Замечу, что я сильно увлекался нонконформистской живописью 70-90-х годов прошлого века. А.Ш.
9.1. Автоматные задачи
Многие программистские задачи удобно решать с помощью методов, формализацией которых могут служить таблицы состояний и переходов (напр., их собрание см. [Шалыто А.А. Switch- технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 628 с.] и на сайте http://is.ifmo.ru).
В книге имеется еще три лекции, посвященных автоматному программированию:
Лекция 10. Автоматное прогрнаммирование: от таблицы к программе
Лекция 11.Автоматное преобразование структурированных текстов
Лекция 12. Переход от данных к конечному автомату
В примечании к разделу 16.1. Что нужно для переиспользования сказано:
«Интересно проделать следующий мысленный эксперимент: а что было бы, если математики работали бы примерно в таких же условиях, как программисты?
Ну, ясно, что если бы математик, опубликовавший теорему, брал бы деньги (а тем более требовал бы их заранее) за каждое ее использование, то переиспользование (повторное использование) сразу бы сильно сократилось.
Даже если бы он не брал деньги за теорему саму по себе, но секретил бы ее доказательство и угрожал бы уголовным преследованием всякому, кто осмелится понять (дизассемблировать) написанный им текст, ситуация пришла бы к тому же мертвому концу (здесь эта калька английского слова лучше русского словечка «тупик»).
Да достаточно бы, видимо, всего-навсего оплачивать труд математиков на повременной основе, проверяя обоснованность отчетов о затраченном времени по числу строк написанного доказательного текста. Это, может быть, не убило бы переиспользование полностью, каждый математик (а не только жулики) при каждом удобном случае переписывал бы чужие доказательства своими терминами и с маленькими изменениями. Здесь к тупику пришли бы медленнее, но столь же неизбежно.
Как видите, мы пришли к важному социальному и практичному выводу: единственным шансом на излечение нынешних подростковых болезней программирования является работа сообществ открытого программного обеспечения и открытой проектной документации [Шалыто А.А. Новая инициатива в программировании. Движение за открытую проектную документацию //PC WEEK/RE. 2003. N 40. http://is.ifmo.ru/works/open_doc/]
В словаре понятий, приведенном в конце книги поясняется термин «Автоматное программирование»:
Автоматное программирование-стиль программирования, при котором вычисление ориентируется на структуру конечного автомата: программа представляется как совокупность состояний, каждому состоянию программы сопоставлено глобальное действие, изменяющее состояние вычислительной системы. Переход к новому состоянию осуществляется по результатам анализа характеристик измененного состояния системы.
Автоматное программирование (называемое в книге Непейвода Н.Н., Скопин И.П. Основания программирования. Москва-Ижевск, РХД, 2003 «программированием от состояний») наиболее адекватно тогда, когда действия глобальны, а условия локальны. Оно может быть реализовано множеством способов (программа, интенсивно использующая goto, система объектов, в которой каждое конкретное состояние описано как наследник общего объекта «состояние программы» и т. п.) Оно требует, чтобы конкретные локальных действия и описания были упрятаны в реализации процедур, изменяющих состояние системы, поскольку автоматное программирование глубоко концептуально противоречит, в частности, структурному. Концептуальные противоречия между автоматными сентенциальным программированием намного менее резкие.
Автоматное программирование имеет два варианта: последовательный, когда система неделима, и остается лишь совладать с широким пространством состояний программы, и параллельный(асинхронный), когда систему можно разбить на подсистемы, и каждая подсистема действует относительно независимо. Вариантов могут реализовываться одним из двух методов: когда действия сосредоточены в состояниях или когда они выполняются на переходах между состояниями.
1. Объектно-ориентированное программирование получило широкое распространение, так как базируется на таких понятных человеку абстракциях как «класс» и «объект».
Поэтому, можно предположить, что и у автоматного программирования есть будущее, так как оно основано на такой характерной для человека абстракции как «состояние» (например, «состояние души»), которая при совместном использовании с такими абстракциями как «входное воздействие» и «выходное воздействие», образует понятие «автомат».
Совместное применение понятий «класс», «объект», «состояние» приводят к стилю программирования, названному мною «объектно-ориентированное программирование с явным выделением состояний».
При этом отметим, что под входным воздействием понимается либо «входная переменная», либо «событие».
В последнее время при моделировании бизнес-процессов значительное внимание стало уделяться понятию «событие» (Черняк Л. EDA — архитектура, управляемая событиями //Открытые системы. 2005. N2, c.18-25. Черняк Л. Сложные события и мониторинг бизнеса //Открытые системы. 2005. N2, c.38-41).
Из изложенного следует, что применение понятий «состояние» и «автомат» может оказаться продуктивнее, чем применение понятия «событие».
2. Последнее время я часто слышу от людей, которые не способны похвалить автоматное программирование, слова о том, что оно применимо только для задач небольшой размерности, а это им не интересно, так как задачи, решаемые ими на практике, весьма сложны. И это говорят люди, которые небольшие задачи задачи «красиво» решать не умеют.
Это звучит весьма странно, так как еще В.И. Ленин учил, что «не следует браться за решение больших задач, не научившись решать малые». Для кого Ленин не авторитет, должен помнить, что «когда человек хочет передвинуть гору, он начинает с того, что убирает мелкие камни», а не наоборот.
//Информационно-управляющие системы. 2005. В печати.
1. Проект UniMod опирается на ясную парадигму — автоматное программирование. В соответствии с парадигмой автоматного программирования приложение рассматривается как совокупность некоторых объектов предметной области и управляющих ими конечных автоматов.
Объекты управления могут выполнять некоторые действия и в них могут происходить события. При поступлении событий автоматы вызывают соответствующие действия объектов.
В данной статье автор не намерен отстаивать и разъяснять концепцию автоматного программирования (автору эта идея представляется бесспорной), отсылая читателя за блестящими аргументами и многочисленными примерами к первоисточникам (htpp://is.ifmo.ru).
2. Правомерно ли утверждать, что инструмент поддерживает описание поведения с помощью UML, если он позволяет нарисовать диаграмму состояний и не более того?
Между тем даже известнейшие инструменты (например, Rational Rose и Together Control Center), декларируя поддержку UML различных версий, ничего не умеют делать с упомянутым базовым средством описания поведения в UML (то есть, с конечными автоматами).
Среди последних инструментов визуального конструирования программ наибольшего внимания, по нашему мнению, заслуживает проект UniMod. Автор наблюдает развитие этого проекта с близкого расстояния, и скорость роста возможностей этого инструмента впечатляет.
Концептуально модель приложения в UniMod состоит из диаграмм двух типов:
Функции входных и выходных воздействий при использовании UniMod пишут вручную.
Символьные имена на диаграммах выбираются в соответствии с очень жесткой дисциплиной их формирования, принятой в этом инструментальном средстве. Она кажется непривычной и даже архаичной, но у нее есть важные для визуального конструирования достоинства.
Во-первых, имена получаются короткими, и поэтому даже сложные выражения легко размещаются, например, на дугах, по которым выполняются переходы в диаграммах состояний.
Во-вторых, имена типизированы на лексическом уровне, что очень важно для читабельности диаграмм.
Такой стиль формирования имен противоречит якобы общепринятому правилу обязательного использования длинных содержательных идентификаторов. В UniMod содержательность достигается комментариями в схеме связей и всплывающими подсказками. При этом не требуется использовать уродливых паллиативов наподобие «венгерской нотации».
Из изложенного следует, что для визуального конструирования программ не обязательно «поддерживать» весь язык UML. Например, диаграмма связей в UniMod является весьма узким, и к тому же специализированным подмножеством диаграммы классов UML. С другой стороны, если некоторая концепция поддерживается средством, то она должна поддерживаться в полной мере, например, как поддержаны диаграммы состояний в UniMod.
Это средство было с самого начала ориентировано на визуальное конструирование приложений, и оно ориентировано на главное: исполняемой визуальной модели приложения, которая может быть как проинтерпретирована или скомпилирована.
3. По мнению автора, защита интеллектуальной собственности разработчиков путем сокрытия исходных кодов программ — это укоренившийся, но общественно вредный анахронизм. Практика сокрытия исходного кода невыгодна самим разработчикам.
Действительно, сокрытие исходного кода затрудняет его повторное использование, и упущенная выгода намного перевешивает ущерб злономеренного нарушения авторских прав. При разработке, ориентированной на модели, сокрытие моделей — нонсенс, противоречащий самой сути подхода.
Общественные движения, направленные на расширение публичного доступа к информации, экономически обоснованы, и поэтому победа будет за ними.
В этой связи, по нашему мнению, особого внимания заслуживает «Движение за открытую проектную документацию», поскольку оно наибольшей степени соответствует духу модельно-ориентированной разработки программ.
Четвертая глава полностью посвящена так называемому «автоматному программированию». Суть этой концепции состоит в том, чтобы писать алгоритмы, по своему поведению напоминающие устройства, подобные конечным автоматам.
Конечные автоматы, по сути, вымышленные устройства, оказались на редкость полезными в практическом программировании. Работа со строками и подстроками — не единственная область, в которой конечные автоматы могут принести пользу. Существуют процессы, удобно представимые в виде состояний и переходов. Представление подобных устройств с помощью конечных автоматов может заметно сэкономить наши усилия по их моделированию.
Говорю о конечные автоматах, нельзя не затронуть еще одну тему, довольно популярную в последние годы: автоматное программирование, которую я хочу представить как новый блестящий инструмент для вашей коллекции.
Видимо, расплывчатое понятие «удобства» использования той или иной парадигмы во многом определяется личными склонностями и образованием программиста. Вполне возможно, что математику всегда проще думать в терминах предикатов и функций, а инженеру - в терминах автоматов.
Под «автоматом» в автоматном программировании понимается куда более мощное устройство, чем конечный автомат, традиционно применяемый применяемый в программировании: очередное состояние автомата определяется с помощью вычисления любой, сколь угодно сложной функции, а при переходе автомата из одного состояния в другое может выполняться сколь угодно сложный фрагмент кода.
Таким образом, получается гибридное устройство, в котором чисто автоматная модель сочетается с произвольными фрагментами кода на используемом языке программирования.
Психологическое значение автоматов очень велико. Компьютеру все равно, какую программу выполнять, а для человека есть существенная разница в том, как написана программа.
Конечный автомат — еще одна абстракция, которую целесообразно применять в программировании, которая может помочь взглянуть на задачу по-новому.
Журнал «Информационные технологии» об автоматном программировании
По материалам книги Ослэндера Д.М., Риджли Д.Р., Ринггенберга Д.Д. Управляющие программы для механических систем. Объектно-ориентированное проектирование систем реального времени. М.: БИНОМ. Лаборатория знаний. 2004. В США книга вышла в 2002 году.
В начале книги обосновывается важность применения микроконтроллеров, и сказано, что «более 99% (!!!) всех микропроцессоров, проданных в 1998 году, использовались во встраиваемых системах, а в 2000 году число микроконтроллеров в высококачественном автомобиле достигало 60».
Содержание этой книги основано на философии, что управление должно рассматриваться на уровне проекта, а не на уровне программного кода. Методология, которую они используют основана на детальном описании проекта с помощью машин с конечным числом состояний. Оказывается, существует методология, способная работать на уровне сложности, необходимом для рассматриваемого класса систем. Она имеет некоторые общие элементы с такими формальными методологиями типа использования языка UML, но значительно более простая.
Выбор методологии основан на ее способности описать поведение системы управления таким образом, чтобы оно было просто для понимания широким спектром заинтересованных лиц, а не только проектировщиками и программистами. Методология также позволяет легко даже вручную перейти к тексту программы почти на любом языке программирования или аппаратуре.
Отмечается, что программное обеспечение реального времени должно включать концепцию «продолжительности», которая не является частью обычного программного обеспечения. Продолжительность — важное понятие, оно является основой технической документации, используемой как основа методологии проектирования надежного программного обеспечения (ПО) систем управления. При этом разработка документации объединена с процедурой спецификации ПО.
Отмечается также, что сложность создания программного обеспечения для этого класса приводит к тому, что для рассматриваемого класса систем в 1997 году 80% всех проектов были вовремя не внедрены.
Для борьбы с этим авторы предлагают принять такую техническую политику, при которой не только написание кода (программирование) рассматривается как творческая деятельность! Это может быть обеспечено, если специалисты в предметной области будут детально описывать, как управляющее ПО должно себя вести, а программисты будут разрабатывать различные инструменты (включая, например, шаблоны) для преобразования таких описаний в программы на заданных языках программирования. Это делает собственно программирование значительно более рутинным, так как творческая часть в значительной мере переносится на этап проектирования и отдается другим людям.
Очень часто единственной детальной документацией на ПО систем реального времени является сама программа, но, по мнению авторов, документация должна существовать независимо от программы, причем технические и вычислительные особенности системы должны быть отделены друг от друга. При этом технические характеристики описывают, как система работает, а вычислительные — как она реализована.
Это при выборе надлежащего подхода для описания технической части, может позволить проводить намного более широкое обсуждение и экспертизу со специалистами, знакомыми с проблемой, а не с программированием.
Авторами предлагается каждый из аспектов (технический и вычислительный) разделить на два уровня.
Технический уровень делится на выделение задач и состояний, декомпозирующих задачи, а вычислительный — на организацию процессов и потоков.
Разбиение на задачи, а затем на состояния — субъективный процесс, требующий серьезного технического рассмотрения, который несомненно является творческим.
Разбиение на вычислительном уровне выполняется для того, чтобы использовать ресурсы вычислителя наиболее эффективно, и нет никакой теоретической потребности в таком разбиении Оно не зависит от проектирования задач-состояний в том смысле, что много разных конфигурации процессов потоков может быть разработано для одной и той же спецификации задач-состояний.
Лучший способ управлять стоимостью сопровождения ПО — аккуратное проектирование. Убогое проектирование и бесплановая реализация разду- вают затраты на обслуживание по экспоненте.
Проектирование на основе выделения задач/состояний, может быть, не самый быстрый путь к программе, но это — быстрый путь к надежно работающей программе.
P.S. Писал это не я, но пришел к тем же выводам и написал аналогичный текст значительно раньше, и поэтому готов подписаться под каждым приведенным выше словом. А. Шалыто
Интересно было бы узнать, как опытные разработчики реализуют логику управления для ПЛК. Какими средствами разработки пользуются? Как относятся к языкам стандарта МЭК 1131? Из моего опыта могу сказать, что на графических языках типа FBD логика управления реализуется довольно проблематично из-за нагромождения условных операторов. Можно использовать для этого триггеры и/или мультиплексоры для кодирования/декодирования состояний. Но это не выход. Для решения указанной задачи я использую SWITCH-технологию (http://is.ifmo.ru), поскольку она позволяет наглядно представить структуру программы, облегчает ее документирование. А специальные утилиты реализуют автоматическую генерацию кода, что ускоряет процесс разработки. И вообще документируют ли современные разработчики свой код? Или это опциональное требование, которые не выполняется по той простой причине, что разработчик хочет остаться незаменимым?
Основная суть технологии изложена в статье «Алгоритмизация и программирование для систем логического управления». Но для получения общего представления о данном подходе стоит прочитать статью, опубликованную в 8-м номере журнала Мир ПК за 2001 год. Она называется «Программирование с явным выделением состояний». Для меня вначале тоже многое было непонятно, потому что я никак не мог себе представить как же все это хозяйство реализуется на практике. На самом деле SWITCH-технология отражает совершенно новый подход к программированию. Теперь в разработке ПО появился новый этап — проектирование, о котором раньше как-то не было принято говорить. Все просто садились и писали. Причем какой-то целостного представления о выполняемой работе не было. Особенно это касается софта для ПЛК. Для начала пишется заглушка, отлаживается, потом постепенно наращивается функциональность. Обычно в виде набора модулей с некоторым множеством фунций в каждом. Взаимосвязи модулей через пару лет будут уже никому не понятны. Основное время разработчика будет занимать поиск глюков в процедурах, которые писались неизвестно кем неизвестно когда без какого-либо документирования. Думаю, для многих это до боли знакомая ситуация. В SWITCH-технологии используется совершенно иной подход, основным преимуществом которого является ясность (естественно для тех кто в ней разбирается). Большая заслуга г-на Шалыто в том, что он постепенно продвигает свое детище в массы, но преодолеть заскорузлость наших программистов не так уж и просто. Хорошо, что он работает преподавателем и несет эту идею с чистого листа в молодые умы, которые еще не привыкли к безответственности.
__________________
С уважением,
Владимир, ООО НПФ «ИНТЕК» http://forum.cta.ru/forum_posts.asp?TID=1023#top
Любопытно, что упоминаемая в статье switch-технология предложена российским ученым, представителем Гавриловской школы[Школа по теории дискретных устройств была организована членом-корреспондентом АН СССР Михаилом Александровичем Гавриловым в конце 1960-х годов] А. А. Шалыто. Она основана на применении в программировании идей теории систем управления. Автор первоначально предложил ее для алгоритмизации и программирования систем логического управления, в которых ввод входных воздействий выполняется по опросу как, например, в программируемых логических контроллерах и других подобных задачах).
В этой технологии базовым является понятие "состояние". Добавляя к нему понятие "входное воздействие", мы получаем "автомат без выхода". А дополнив технологию "выходным воздействием", мы получаем: автомат = состояния + входные воздействия + выходные воздействия. Соответствующий подход был назван "автоматным программированием".
В дальнейшем Шалыто и Н. И. Туккель развили этот подход для программирования более широкого класса задач. Авторы приводят пример применения switch-технологии при разработке системы управления дизель-генератором, реализуемой на промышленном компьютере с операционной системой QNX, в которой управляющая программа выполняется как один процесс, а программа, моделирующая объект, - как другой процесс. При этом был создан вариант switch-технологии для разработки программного обеспечения более широкого класса систем управления - "реактивных" (reactive), реагирующих на события. Такие системы обычно реализуются на промышленных компьютерах, работающих под управлением ОС реального времени. Рассмотренный подход является процедурным, а соответствующий стиль программирования был назван "программирование с явным выделением состояний"; существует и объектно-ориентированное программирование с явным выделением состояний.
Еще одна область применения автоматного программирования - классические алгоритмы, и в частности, построение визуализаторов алгоритмов.
У автоматных методов большое будущее, и хотя это научное направление все еще находится в стадии становления, switch-технология имеет все шансы занять достойное место в программировании.
Подробнее на эту тему можно прочитать в книге Шалыто А.А. Switch-технология. Алгоритмизация и программирование задач логического управления. - СПб.: Наука, 1998. Или на сайте http://is.ifmo.ru.