УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Конечный автомат многим не друг

Шестого мая мой ученик Виталий Клебан (сейчас один авторов одного из стандартов на «Интернет вещей» – на спецификацию LoRaWAN: (https://lora-alliance.org/sites/default/files/2018-04/lorawantm_specification_-v1.1.pdf) сообщил мне, что не один я являюсь фанатом применения автоматов в программировании. При этом он написал, он написал, что 25, 26 мая «Российские интернет-технологии» проводят по адресу https://ritfest.ru/2020/abstracts/6425 профессиональный онлайн-фестиваль для тех, кто создает Интернет.

В программу в разделе «Новинки (!) и хайпы» включен доклад Романа Омельницкого из «Яндекса» на тему: «Стэйт-менеджмент на конечных автоматах» (https://ritfest.ru/2020/authors/13013). В тезисах доклада автор пишет: «Когда приложение растет и интерфейсы усложняются, классический подход к стейт-менеджменту показывает себя не так хорошо. В докладе я расскажу, что такое конечные автоматы и стейтчарты, и как они могут помочь нам писать более предсказуемую и прозрачную логику. Покажу, как их применять и какие готовые решения существуют».

Сначала я не понял что такое «стэйт-менеджмент». Оказалось все очень просто: «стэйт» – это русская транскрипция английского слова «state» – «состояние», а потом очень удивился, что доклад попал в раздел конференции «Новинки», так как если в названии чего-то есть понятие «состояние» и число состояний не громадно (управляющих состояний, в отличие от вычислительных, много практически никогда не бывает), то что же еще использовать, как не «конечные автоматы»?

После того, как я посмотрел несколько лекций 2019 г. на YouTube, оказалось, что я неправ. Первое, что меня удивило в их названии, что состояние там используется в единственном числе, ну а далее удивление не покидало меня, так авторы шести (!) лекций с названием «Управление состоянием» (https://www.youtube.com/watch?v=lwec8maPrrI) и лекции «Проблемы стэйт-менеджмента, и их решение с Effector.js» продолжительностью в один час шесть минут (https://www.youtube.com/watch?v=48XSmEIqbkI) ни разу (!) не упомянули про конечные автоматы! При этом они не догадывались, что, видимо, многие из указанных в лекциях проблем возникают именно потому, что они не используют автоматы, и хорошо, что Омельницкий, наконец, это понял и расскажет «народу», как их решать. .

Я пишу о применении конечных автоматов в программировании уже почти тридцать лет – с 1991 г. (http://is.ifmo.ru/), и каждый раз, как мальчишка, удивляюсь, когда узнаю, что кто-то в очевидной, как в данном случае, ситуации для применения автоматов, не использует их.

Первый раз шок по этому поводу я испытал через пятнадцать (!) лет с начала «моей писанины» на эту тему, когда в 2007 г. увидел на сайте корпорации IBM (!), что их сотрудник Эдвард Принг «разразился»серией из трех статей на тему «Конечные автоматы на JavaScript». Первая из них называлась «Разрабатываем виджет» (https://www.ibm.com/developerworks/ru/library/wa-finitemach1/index.html), вторая – «Реализация виджета» (https://www.ibm.com/developerworks/ru/library/wa-finitemach2/wa-finitemac_ru.html) и, наконец, третья – «Тестируем виджет (исходники)» (http://www.interface.ru/home.asp?artId=7867).

Интересно, что при поиске в Google непосредственно после второй статьи Принга выдается информация о моем большом тексте 2008 г. «Автоматное программирование» (http://window.edu.ru/catalog/pdf2txt/806/58806/28668?p_page=1), про который написано «читать бесплатно онлайн». Кстати, этот текст (http://is.ifmo.ru/works/_2010_09_08_automata_progr.pdf) вошел в число победителей (http://archive.vn/http://www.ict.edu.ru/itkonkurs2008/2224/) второго этапа Всероссийского конкурсного отбора обзорно-аналитических статей по приоритетному направлению «Информационно-телекоммуникационные системы», введенному в «Перечень приоритетных направлений развития науки, технологий и техники в РФ», указом Президента РФ от 21.05.2006 г. № 843.

История с Прингом произошла уже после выхода книги Салмре И. Программирование мобильных устройств на платформе .Net Compact Framework. М.: Вильямс. 2006 (На английском языке – в 2005 г.), в которой пятая глава называется «Наш друг конечный автомат» (http://is.ifmo.ru/automata/mobdev/), и, по моему мнению, является гимном применения автоматов в мобильных устройствах. Однако оказывается, гимн гимну рознь: если Гимн СССР исполняли по радио каждое утро, и поэтому его узнавали все граждане нашей страны и не только ее, то указанный «гимн», как оказалось, не стал узнаваемым даже в области мобильных устройств, не говоря уже, о создании программного обеспечения (ПО) в других предметных областях.

Как мы видим, не только 2007 г., но и 2005 г. не стал переломным в рассматриваемом вопросе, но история этого вопроса в новое время идет еще глубже. До этого времени сотрудники кафедры мехатроники Калифорнийского университета в Беркли Ослэндер Д.М., Риджли Д.Р., Ринггенберг Д.Д. в книге «Управляющие программы для механических систем. Объектно-ориентированное проектирование систем реального времени. М.: БИНОМ. Лаборатория знаний. 2004) написали: «Для систем реального времени в 1997 г. 80% всех проектов не были вовремя внедрены из-за плохого качества ПО». Они считают, что для повышения качества ПО необходимо «принять такую техническую политику, при которой не только написание кода (программирование) рассматривается как творческая деятельность!» (формулировка, сильно смягченная мною, А. Ш.).

Это может быть обеспечено, если специалисты в предметной области будут детально описывать, используя графы переходов конечных автоматов, как управляющая часть ПО должна себя вести, а программисты – разрабатывать различные инструменты (включая, например, шаблоны) для преобразования таких описаний в программы на заданных языках программирования. Это, правда, делает собственно программирование значительно более рутинным, так как творческая часть в значительной мере переносится на этап проектирования и отдается на откуп другим людям.

При этом, однако, сам процесс создания ПО становится существенно более упорядоченным, и резко уменьшается число ошибок в нем. При таком подходе описание поведения программ выполняется достаточно просто и становится понятным широкому кругу заинтересованных лиц, а не только программистам, что также способствует повышению качества ПО. Кстати, в автоматном программировании, которое было предложено значительно раньше, чем была написана эта книга (на английском – в 2002 г.), я высказывал те же самые мысли, «кощунственные» для традиционного программирования.

В связи с изложенным, казалось бы, автоматы сам Бог велел применять при программировании ПЛК (программируемых логических контроллеров), однако в стандарте IEC 1131-3, который потом стал именоваться IEC 61131-3, в описании языков программирования автоматы даже не упоминались, и это при том, что стандартизованные методы программирования на этих языках отсутствовали. Поэтому мне пришлось разрабатывать эти методы, основанные на применении конечных автоматов, и описывать их в одной из глав книги «SWITCH-технология. Алгоритмизация и программирование задач логического управления». СПб.: Наука, 1998. 628 с. (http://is.ifmo.ru/books/switch/1). Мои «походы» в представительства компаний Schneider Electric и Siemens в Санкт-Петербурге по этому вопросу ни к чему не приводили – да и что можно взять с «продавцов», которые единственное что и хотели взять, то это деньги с продаж. При этом всем было наплевать на простоту и удобство программирования, особенно программистам-пользователям ПЛК, так как чем программирование сложнее и непонятнее, тем выше их зарплата – и так везде в программировании.

Через какое-то время при разработке международного стандарта на сети распределенных ПЛК IEC 61499 его авторы, видимо, внезапно поумнели и рекомендовали при программировании ПЛК в таких сетях для описания поведения управляющих устройств использовать конечные автоматы. Это, в частности, сподвигло Валерия Вяткина – профессора университетов Аалто (Финляндия) и Лулео (Швеция), одного из авторов книги «Distributed Control Application: Guidelines, Design Patterns, and Application Examples with the IEC 61499 (Industrial Information Technology)» (https://www.amazon.com/Distributed-Control-Applications-Application-Information/dp/1482259052), в 2014 г. позвонить мне и предложить сотрудничество в рамках применения конечных автоматов при программировании промышленных систем управления, я согласился и ... «понеслось».

В результате Валерий стал профессором-исследователем в Университете ИТМО и соруководителем нашей международной научной лаборатории «Компьютерные технологии». Фотографии (http://is.ifmo.ru/photo/2014-05-15-Vyatkin/) запечатлели Валерия момент появления у нас. Через некоторое время он переоделся, и в Японии уже был одет правильно – в майку Университета ИТМО :-) (http://is.ifmo.ru/photo/2016-04-Vyatkin/index.html).

Из наших совместных публикаций укажу две: Chivilikhin D., Ulyantsev V., Shalyto A., Vyatkin V. Function Block Finite-State Model Identification Using SAT and CSP Solvers // IEEE Transactions on Industrial Informatics. 2019. № 8, pp. 4558-4568. IF: 5.43, SR: 1.6. https://ieeexplore.ieee.org/document/8606098 и Mukhutdinov D., Filchenkov A., Vyatkin V., Shalyto A. Multi-Agent Deep Learning for Simultaneous Optimization for Time and Energy in Distributed Routing System // Future Generation Computer Systems. 2019. Vol. 94, May, pp. 587-600. IF: 4.639, SJR: 1.151. (https://www.sciencedirect.com/science/article/abs/pii/S0167739X18309087).

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

Хотя и это часто не помогает. Например давно известно, но, видимо, не всем, что существует расширение всемирно известного пакета MatLab – инструментальное средство Stateflow (http://www.mathworks.com/products/stateflow/). Оно позволяет строить автоматы (в том числе, вложенные), моделировать их работу в разных режимах и выполнять кодогенерацию на языке C и не только.

Так, в частности, на его основе можно не только создавать автоматные программы в их традиционном понимании, но программировать аппаратуру – программируемые логические интегральные схемы (ПЛИС). Об этом можно прочесть здесь: Янкин Ю.Ю., Шалыто А.А. Автоматное программирование ПЛИС в задачах управления электроприводом // Информационно-управляющие системы. 2011. № 1, 50-56. http://is.ifmo.ru/works/_automata_plis.pdf).

Надеюсь, что Вы не думаете, что все, кто применяет ПЛИС, используют это замечательное средство, программируя с использованием языка сверхвысокого уровня – графов переходов, так как многих хлебом не корми – дай покодить на С, а еще лучше – на ассемблере VHDL, и все это либо из-за безграмотности, либо из-за желания показать свою крутизну, либо для того, что кормиться не только хлебом, но и еще чем-то, так как отказавшись от применения автоматов в этих случаях, программист в некотором смысле становится незаменимым.

Я, конечно понимаю, что Stateflow весьма дорогой пакет, но это не исключает того, что если Вы «крутой» программист, как думают о себе многие, то реализуйте аналог этого инструментального средства сами (как в свое время сделали мои ученики В. Гуров и М. Мазин, создав инструментальное средство UniMod – http://unimod.sourceforge.net/intro.html), или, по крайней мере, будете проектировать, а не писать, программы вручную, но не так, как Вам хочется , а идеологически так, как это сделано в указанном пакете!

При этом отмечу, что в 2012 г., когда мы практически перестали поддерживать этим средство, стало известно, что оно используется при бакалаврской подготовке в Италии. Предполагается его применение также, и при магистерской подготовке и при обучении аспирантов: Ricca F., Leotta M., Reggio G., Tiso A., Guerrini G., Torchiano M. Using UniMod for Maintenance Tasks: An Experimental Assessment in the Context of Model Driven Development (http://softeng.disi.unige.it/publications/2012-ricca-MiSE.pdf).

И в заключение сообщаю, что уже давно существует наша книга – Поликарпова Н., Шалыто А. Автоматное программирование. СПб.: Питер, 2008. 176 с., http://is.ifmo.ru/books/_book.pdf, которая, если у Вас найдется 58 рублей, «придет» к Вам на компьютер сама (https://www.ozon.ru/context/detail/id/28260411/).

У меня по этому вопросу пока все, но что это совсем все – не надейтесь :-).

07.05.2020