Автоматное программирование. Обзорная статья.

Автоматное программирование. Обзорная статья.

На эту тему я пишу с 1991 г., а с конца 2002 г. существует «Сайт по автоматному программированию и мотивации к творчеству», на котором, в частности, выложено большое число автоматно-спроектированных программ (http://is.ifmo.ru/projects/ и http://is.ifmo.ru/unimod-projects/).

В 1995 г. я впервые выступил на указанную тему на конференции за рубежом (Shalyto A.A. Cognitive Properties of Hierarchical Representations of Complex Logical Structures / Рroceeding of the 1995 International Symposium on Intelligent Control (ISIC). Workshop. 1995. Monterey. California, p. 391.

Здесь, в частности, я искал финансирование на издание написанной мною книги о программной реализации алгоритмов логического управления, которая базировалась на опыте работы по этой тематике в НПО «Аврора». Участвовавшие в работе конференции Дмитрий Александрович Поспелов, с которым я был знаком до этого, и Вадим Николаевич Вагин, посоветовали мне подать заявку на издательский грант в Российский фонд фундаментальных исследований (РФФИ), что я и сделал.

В результате в 1995 г. я выиграл большой грант РФФИ (проект № 96-01-14066) на издание книги объёмом в 40 печатных листов и тиражом 1000 экземпляров, что по тем временам, да и сегодня, большая редкость. На его основе я заключил договор с издательством «Наука» на издание книги с названием, которое указал в заявке: «SWITCH-технология. Алгоритмизация и программирование задач логического управления». Книга была опубликована в 1998 г., её выход совпал с моим пятидесятилетием. Таким образом, термин «SWITCH-технология» существует с 1995 г., а с 1998 г. он используется и не только мною.

Термин «автоматное программирование», чтобы не говорили недоброжелатели о том, что он был «всегда», родился в результате моей беседы с Поспеловым на конференции по мультиагентным системам, проходившей в 1997 г. в посёлке Ольгино под Санкт-Петербургом. Эта история описана в книге, посвящённой 20-летию кафедры «Компьютерные технологии» Университета ИТМО.

Приведу некоторые детали этой встречи. После моего рассказа о том, как я предлагаю программировать, по крайней мере системы логического управления, Дмитрий Александрович сказал: «Очень здоровый подход – крепко стоит на земле. Назови его автоматным программированием. Смотришь – привьётся...». Вот я и назвал!

Вряд ли кто-то в то время в стране лучше его понимал, что такое автоматы и как их применять, но изложенная технология программирования его удивила, и он помог мне опубликовать статью Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Известия РАН. Теория и системы управления. 2000. № 6, с. 63-81. В этом журнале Дмитрий Александрович в то время был заместителем главного редактора. Вот что написано в аннотации к этой статье: «Описываемая технология может быть названа автоматной технологией, а соответствующая область программирования – автоматным программированием».

Естественно, что и до моих работ в программировании использовались автоматы, но ни парадигмы автоматного программирования, ни такого термина, как «Автоматное программирование», ни на русском языке, ни на английском (Automata-based programming) не было.

Из рассмотрения этих работ следует, что термин «Автоматное программирование» был предложен мною в 2000 г., термин «Automata-based programming» – в 2003 г., а термин «Парадигма автоматного программирования» – в 2008 г.

Уже много лет как в Википедии на английском языке есть статья «Automata-based programming (Shalyto`s approah)».

Статья в этой энциклопедии под названием «Automata-based programming» исходно была написано мной, потом началась свара, которая закончилась тем, что статью полностью переписали, несмотря на то, что в ней ссылки на работы, в названиях которых используется этот термин, кроме моих статей и статей и моих учеников, отсутствуют! На русском языке ситуация с переписыванием статьи аналогична.

Моя последняя англоязычная статья на эту тему вышла в 2017 г., и она называется «Why Design Programs: Anatoly Shalyto on Automata-Based Programming». Её название на русском: «Программа как инженерный проект, или зачем заказчику понимать структуру ПО изнутри». Этот текст начинается так: «В газете «КоммерсантЪ» была опубликована статья «В «Росатоме» нашли проблемы с ядром. Сотрудники госкорпорации пожаловались на установленный на АЭС софт». В ней рассматривается вопрос о легитимности используемого на атомных электростанциях ПО. Там, в частности, написано, что имеющееся ПО не позволяет понимать, как программа будет себя вести в тех или иных случаях, как именно и какие в неё вносили изменения. Более того, в тексте статьи сказано, что на этот софт нет никакой документации. И это при том, что объект автоматизации – атомный реактор, а почти никто, кроме, возможно, разработчика, которого, естественно, нет на объекте, а то уже и в живых, не понимает, как работает управляющая программа. И такой бардак с ПО творится почти везде в мире. Нормально ли это?».

Возможно, что применение автоматного программирования может стать «серебряной» пулей в этом вопросе, о которой в 1975 г. Ф. Брукс, говорил, что при создании ПО её не существует, а через 25 лет – в 2010 г. с учетом работ Д. Харела, в её отсутствии он уже был не так уверен. Вот основная работа Харела: Harel D. Statechart: A Visual Formalism for Complex Systems // Science of Computer Programming. 1987. № 8, pp. 231-274.

Основным понятием автоматного программирования является понятие «состояние». А.Дж. Перлис в 1966 г. (Перлис А.Дж. Синтез алгоритмических систем / Лекции лауреатов премии Тьюринга за первые двадцать лет 1966-1985. – М.: Мир, 1993) предложил в описания языка, среды и правил вычислений включать состояния, которые могут подвергаться мониторингу во время исполнения, позволяя диагностировать программы, не нарушая их целостности. В этом же году Э. Дейкстра (Дейкстра Э. Взаимодействие последовательных процессов / Языки программирования. – М.: Мир, 1972) предложил ввести так называемые переменные состояния, с помощью которых можно описывать состояния системы в любой момент времени. Он (как и я) использовал для этих целей целочисленные переменные. При этом им были поставлены вопросы о том, какие состояния должны вводиться, как много значений должны иметь переменные состояния, и что эти значения должны означать. Он предложил сначала определять набор подходящих состояний (и я тоже), а лишь затем строить программу.

По мнению Дейкстры, диаграммы переходов между состояниями могут оказаться мощным средством для проверки программ. Это обеспечивает поддержку его идеи о том, что программы должны быть с самого начала составлены правильно, а не отлаживаться до тех пор, пока они не станут правильными». Не появление ли автоматного программирования он предвещал?

А ещё всегда надо помнить: «то, что не специфицировано формально, не может быть проверено, а то, что не может быть проверено, не может быть безошибочным».

Приведу ряд «активностей» (в основном моих) в области автоматного программирования

1. Введение в автоматное программирование

1.1. Зачем нужны автоматы?

1.2. Программирование за ... одну минуту.

1.3. Скромное обаяние автоматного программирования.

1.4. Парадигма автоматного программирования.

1.5. Применение автоматов при программировании мобильных устройств («Мой друг – конечный автомат»).

1.6. Лекция по автоматному программированию. Вот один из комментариев к ней: «Написал пару скриптов по этой технологии на Python. Скрипты просто железно работают». Потом появился ещё один не менее интересный комментарий: «Вот уж действительно – гениальное просто. Пример с пятью и тридцати двумя состояниями при пяти двоичных флагах очень доступен для понимания. Спасибо, огромное. Теперь только автоматы :-)».

1.7. Презентации по автоматному программированию (http://is.ifmo.ru/present/_2.ppt, http://is.ifmo.ru/present/_1.ppt).

1.8. Что плохого в неавтоматном подходе к программированию контроллеров.

1.9. Верификация автоматных программ (http://is.ifmo.ru/present/_verification_moscow.ppt)

2. Книги по автоматному программированию

2.1. Шалыто А.А. Switch-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. 1998. 628 с.

2.2. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. Учебно-методическое пособие. СПбГУ ИТМО, 2007.

Здесь впервые были сформулированы парадигма и миссия автоматного программирования: «Парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления», а вот, как была определена его миссия: «Нахождение компромисса между сложностью автомата и сложностью операций объекта управления, примирение тьюрингова программирования с традиционным – это и есть «миссия» автоматного подхода в мире разработки программного обеспечения».

2.3. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. СПб.: Питер, 2008, 2009 (http://is.ifmo.ru/automata/shalytobook/), 2010, 2011 (https://www.piter.com/product/avtomatnoe-programmirovanie-2-e-izd). Потом книга стала «вечной», так как превратилась в цифровой товар (https://www.ozon.ru/context/detail/id/28260411/).

3. Обзорные статьи по автоматному программированию

3.1. Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Известия РАН. Теория и системы управления. 2000. № 6, с. 63-81.

3.2. Шалыто А.А. Алгоритмизация и программирование для систем логического управления и «реактивных» систем //Автоматика и телемеханика. 2001. № 1, с. 3-39. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=1715&option_lang=rus.

3.3. Шалыто А.А. Автоматное программирование // Известия Уральского государственного университета. 2006. № 43. Компьютерные науки и информационные технологии. Вып.1, с.181-190.

3.4. Шалыто А.А. Парадигма автоматного программирования // Научно-технический вестник СПбГУ ИТМО. 2008. Выпуск 53. Автоматное программирование, с. 3-24.

3.5. Шалыто А.А. Автоматное программирование. Всероссийский конкурс обзорно-аналитических статей по приоритетному направлению «Информационно-телекоммуникационные системы». http://archive.vn/r8jlj.

3.6. Шалыто А.А. Автоматное программирование / Труды конференции «Технические и программные средства систем управления, контроля и измерения» М.: ИПУ РАН. 2010, c. 1213-1224.

3.7. Шалыто А.А. Автоматное программирование / Виртуальный компьютерный музей.

4. Статьи, в название которых входит термин «Automata-based programming». Эти статьи из Scholar articles for Automata-based programming

4.1. Shalyto A. Technology of Automata-Based Programming // PC World/Russia. 2003. № 10. http://is.ifmo.ru/automata_en/_tech_aut_prog.pdf.

4.2. Yartsev B., Korneev G., Kotov V., Shalyto A. Automata-Based Programming of the Reactive Multi-Agent Control Systems / 2005 International Conference on Integration of Knowledge Intensive Multi-Agent Systems: Modeling, Exploration and Engineering (KIMAS-05). Boston: IEEE Boston Section. 2005, pp. 449-453. http://swan.kgeorgiy.info/papers/Yartsev_B__Korneev_G__Shalyto_A__Kotov_V_--_Automata-Based_Programming.pdf.

4.3. Paraschenko D., Shalyto A., Tsarev F. Modeling Technology for One Class of Multi-Agent Systems with Automata Based Programming / Proceedings of 2006 IEEE International Conference on Computational Intelligence for Measurement Systems and Applications (CIMSA-2006). La Coruna. Spain. 2006,  pp.15-20. https://www.academia.edu/31854706/Modeling_Technology_for_One_Class_of_Multi-Agent_Systems_with_Automata_Based_Programming.

4.4.  Gurov V.S., Mazin M.A., Narvsky A.S., Shalyto A.A. Tools for Support of Automata-Based Programming // Programming and Computer Software. 2007. Vol. 33. No. 6, pp. 343-355. https://www.academia.edu/31854647/Tools_for_support_of_automata-based_programming.

4.5. Kurbatsky E. Verification of automata-based programs / Proceedings of the Second Spring Young Researchers Colloquium on Software Engineering. SPb.: SPbSU.2008. (мой ученик). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.517.3692&rep=rep1&type=pdf.

4.6. Klebanov A. Automata-Based Programming Technology Extension for Generation of JML Annotated Java Card Code / Proceedings of the Second Spring Young Researchers Colloquium on Software Engineering. SPb.: SPbSU.2008. (мой ученик).

4.7. Kochelaev D.,  Khasanzyanov B., Yaminov B., Shalyto A. Instrumental Tool for Automata Based Software Development UniMod-2 /Proceedings of the Second Spring Young Researchers Colloquium on Software Engineering. SPb.: SPbSU.2008. https://cyberleninka.ru/article/n/instrumental-tool-for-automata-based-software-development-unimod-2.

4.8. Shalyto A.A. Automata-Based Programming and Automata-Based Control. 2009. http://is.ifmo.ru/articles_en/_2009_10_07_automata_based_programming.pdf.

4.9.   Zakonov A.,  Stepanov O., Shalyto A. A GA-based approach for Test Generation for Automata-Based Programs / Proceedings of the Second Spring Young Researchers Colloquium on Software Engineering. SPb.: SPbSU. 2010. https://cyberleninka.ru/article/n/a-ga-based-approach-for-test-generation-for-automata-based-programs.

4.10. Klebanov A. On the Formal Specification of Automata-Based Programs via Specification Pattern / Proceedings of the Second Spring Young Researchers Colloquium on Software Engineering. SPb.: SPbSU.2010. https://cyberleninka.ru/article/n/on-the-formal-specification-of-automatabased-programs-via-specification-patterns.

4.11. Ulyantsev V., Tsarev F. Extended Finite-State Machine Induction Using SAT-Solver / 14th IFAC Symposium on Information Control Problems in Manufacturing (INCOM-2012). Bucharest, Romania, 2012, pp. 512-517. Термин «Automata-Based Programming» используется в тексте  https://www.sciencedirect.com/science/article/pii/S1474667016331561. (Мои ученики).

4.12. Chivilikhin D., Ulyantsev V. Inferring Automata-Based Programs from Specification With Mutation-Based Ant Colony Optimization / Proceedings of the Sixteenth Genetic and Evolutionary Computation Conference Companion (GECCO 2014). ACM. NY, pp. 67, 68. https://dl.acm.org/doi/10.1145/2598394.2598446. (Мои ученики).

4.13. Koumboulis F., Fragkoulis F., Kouvakas N. Automata-Based Programming for the Development of a Web based Application: A Case Study. https://dl.acm.org/doi/abs/10.1145/2984393.2984402. Первая не наша работа, в которой встречается термин Automata-Based Programming. Она вышла в 2016 г. В ней ссылаются на нас.

5. Tutorial on Automata-Based Programming

В июне 2006 г. мы провели Tutorial on Automata-Based Programming в рамках первой международной конференции International Computer Symposium in Russia (CSR 2006) (ПОМИ им. В.А. Стеклова), в котором было заслушано 24 доклада по этой тематике (https://logic.pdmi.ras.ru/~csr2006/workshops.htmlhttp://unimod.sourceforge.net/).

Одним из докладчиков был G. Berry (Estrel Technology), который участвовал в разработке программного обеспечения для Airbus (http://is.ifmo.ru/present/_berry-wabp.pdf). В семинаре принял участие и мой старинный знакомый Михаил Кишиневский, в то время работавший в корпорации Intel, который совместно с G.Berry разработал текcтово-графический автоматный язык Estrelv 7. Вот перечень заслушанных докладов (https://web.archive.org/web/20090412002353/http://unimod.sourceforge.net/wiki/index.php/CSR2006_ABP_WORKSHOP):

  1. Gurov V.S. (eVelopers) Automata Based Programming Workshop organization.

  2. Shalyto A.A. (SPbSU ITMO) Automata Based Programming. 

  3. Berry G. (Esterel Technologies) Synchronous Programming Techniques for Embedded Systems;

  4. Nepeyvoda N.N. (Udmurtia State University) Automata Based Programming and its Role in Common Informatics Structure (http://is.ifmo.ru/present/_berry-wabp.pdf).

  5. Gurov V.S., Mazin M.A., Narvskiy A.S. (eVelopers), Shalyto A.A. UniMod – a CASE tool for Automata Based Programming.

  6. Gurov V.S., Mazine M.A. (eVelopers) Automata-based design of applications for mobile devices.

  7. Kuzmin E.V., Sokolov V.A. (State University of Yaroslavl) Modeling, Specification and Verification of «Automata» Programs.

  8. Vasiljeva K.A., Kouzmin E.V., Sokolov V.A. (State University of Yaroslavl) LTL-based Verification of «Automata» Programs.

  9. Lubchenko V.S. On physics of automata-based concurrent programming.

  10. Shopyrin D.G. (ZAO Tranzas Technologies) Graphical notation for automata objects inheritance.

  11. Shamgunov N.N. (Microsoft), Korneev G.A. (SPbSU ITMO) State Machine design pattern.

  12. Vavilov K.V. Programmable logic controller and automata-based programming.

  13. Kazakov M.A. (Flextronics) Discrete mathematics algorithms visualizers design with automata-based programming. 

  14. Korneev G.A. (SPbSU ITMO) Automatized approach to visualizers design with finite state machines.

  15. Babaev А. Automata-based UI.

  16. Korotkov M.A., Loukianova A.P. (eVelopers) Automata-based design of WEB-applications.

  17. Polikarpova N.I (SPbSU ITMO) A Notion of Subtyping for Types with State Dependent Behavior.

  18. Stepanov O.G. (JetBrains) Automata Based Programming Using Dynamic Programming Languages. 

  19. Astafurov A.A. (DataArt) Automata Objects Nesting and Inheritance Using Meta Information in Object Oriented Languages. 

  20. Yartsev B.M. (SPbSU ITMO) Automata-based desing of the real-time systems.

  21. Tsarev F.N., Paraschenko D.A. (SPbSU ITMO) Modeling Technology of One Class of Multi-Agent Systems with Automata-based Programming.

  22. Rudnev A.D. (SPbSU ITMO) Using automata-based design in developing driver for floppy disk controller.

  23. Kanzhelev S.Y. (AVIcode) Automatic automata's code generation.

  24. Naumov A.S. (SPbSU ITMO) Virtual Machine for Automata Based Programming.

6. Как правильно строить схемы алгоритмов

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

Этот подход описан в моей статье «Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления I, II // Автоматика и телемеханика. 1996. № 6,7».

7. Автоматное программирование и язык ДРАКОН

Почти через 25 лет после опубликования этой статьи появилась работа Митькина С.Б. Автоматное программирование на языке ДРАКОН // Программная инженерия. 2019. №1, c. 3-13, в которой он ссылается на две мои книги, указанные выше, но не обращает внимания на два важных момента: во-первых,  на главу 13 в одной из этих книг, опубликованной в 1998 г., которая базируется на указанной выше статье, а во-вторых, на то, что в этой книге приводятся примеры применения автоматного программирования в базисе различных языков программирования, в том числе и по стандарту IEC 1131-3. Естественно, что для этой цели могут использоваться и многие другие языки, например ДРАКОН, что и было сделано Митькиным.

Как бы там ни было, после опубликования статьи Митькина появился раздел «9. Автоматное программирование на языке ДРАКОН» в статье в Википедии об этом языке. Это произошло не ранее 2019 г. До этого я читал книги создателя ДРАКОНА В.Д. Паранджонова и ссылался на него, а он на меня – нет. Я ему даже безответно писал. В его работах не использовалось понятие «состояние», и в этом было принципиальное отличие автоматного программирования от его ДРАКОНА. У него правильно построенные граф-схемы – это всякое разное, а не граф-схемы, построенные изоморфно конструкции Switch, начиная с дешифратора состояний, как отмечено выше.

И ещё один момент, на который Митькин не обратил внимание: графы переходов более обозримы, чем любые граф-схемы – хоть, с использованием ДРАКОНА, хоть построенные иначе.

До этого Митькин писал: «До недавнего времени у меня в голове был смысловой разрыв между иконами реального времени языка ДРАКОН (Вставка, Ввод) и конечными автоматами. И то, и другое моделирует динамику взаимодействия, но по-разному», а потом у него произошло ... «озарение»: «Взаимодействующие процессы весьма удобно реализовывать в виде конечных автоматов. ДРАКОН-схема преобразуется в конечный автомат, причём для каждой иконы «Вставка» и «Ввод» создаётся отдельное состояние. Выполнение процесса происходит в виде работы конечного автомата, который движется от одного состояния к другому» (https://forum.drakon.su/viewtopic.php?f=142&t=6631). Потом он пишет: «Конечные автоматы на ДРАКОНе – это бомба. Жаль, что земляне этого не понимают». Я согласен с этим утверждением, но только без использования двух лишних слов: «Конечные автоматы – это бомба. Жаль, что земляне этого не понимают». По моему мнению, иконы целесообразно применять для другой цели, а в программирование следует использовать графы переходов.

Потом я узнал, что на сайте «Визуальный язык ДРАКОН» в перечне форумов есть и такой: «Теоретические основы языка ДРАКОН», а в нём – обсуждение на тему «Язык ДРАКОН и конечные автоматы», на котором существуют страницы, где обсуждается вопросы, связанные с автоматным программированием и мною.

На странице «Язык ДРАКОН. Метод Шалыто и важное предложение Игоря Мазницы» мой старинный знакомый Игорь Мазница в 2016 г. обратил внимание автора языка на то, что я не доволен тем, что он не ссылается на меня. На это Паронджанов ответил: «Анатолий Шалыто прав. Отсутствие ссылок на его работы по автоматному программированию, Switch-технологии – большое упущение. В следующей книге я постараюсь обязательно устранить этот недостаток». Он, видимо, постарался, но у него не получилось: в его книге «Алгоритмы и жизненные ритмы на языке  ДРАКОН. Разработка алгоритмов», датированной 2019 г., нет ни слова ни обо мне, ни об автоматном программировании, ни о Switch-технологии.

В 2017 г. Мазница сообщил драконовцам о существовании записи моей лекции про автоматное программирование, и на их сайте появилась страница «Лекция Анатолия Шалыто про автоматное программирование». О ней Степан Митькин написал «Отличная лекция. Просто, понятно, а главное – с душой». А ещё им было сказано: «На днях я учинил у нас в офисе зачёт по автоматам. Опросил нескольких программистов. Итог: все слышали это слово, но никто точно не знает, что это (хорошо в этой ситуации применять в программировании автоматы, что некоторые считают очевидным, А.Ш.). Похоже, автоматы – это какое-то тайное знание, доступное только элите и аннукам (божествам, А.Ш.)».

В 2018 г. у драконовцев всплыла упомянутая выше моя статья о правильном построении граф-схем. Пообсуждали...

В том же году на странице «А. Шалыто. Проектный подход при обучении разработке программ» Паронджановым приведена половина (?) моей статьи «Проектный подход при обучении разработке программ», которая была опубликована в журнале  Компьютерные инструменты в образовании. 2009. № 4, с. 32-38 (http://ipo.spb.ru/journal/content/1074/Проектный подход обучении разработке программ.pdf). Этот текст на указанной странице никак не обсуждался...

В 2019 г. лекцию про автоматное программирование я выложил на YouTube в лучшем качестве, чем она была опубликована ранее (https://www.youtube.com/watch?v=PPWTxceMutk&t=2821s).

На странице «Язык ДРАКОН, метод Шалыто, метод Ашкрофта-Манны» Паронджанов пишет: «Анатолий Абрамович Шалыто в статье 1996 г. сравнивает свой метод с методом Ашкрофта-Манны и делает вывод, что его метод удобнее. Он не сравнивает свой метод с языком ДРАКОН, так как этот язык тогда был практически неизвестен». Как говорится: «Когда знаешь, как правильно, зачем делать иначе?» – ниже будет показано, что уже в 1991 г. при создании судовых систем управления мы успешно использовали автоматное программирование.

8. Сборники работ по автоматному программированию

8.1. В 2008 г. был издан первый в мире сборник по автоматному программированию: Научно-технический вестник СПбГУ ИТМО. 2008. Вып. 53. Автоматное программирование. Он содержит 28 наших статей по этой теме.

8.2. В 2011 г. был издан Научно-технический вестник СПбГУ ИТМО. 2011. Вып. 2 (72).(http://is.ifmo.ru/works/). Он содержит 17 наших статей и имел подзаголовок «Технологии автоматного программирования и искусственного интеллекта».

9. Автоматное программирование против классиков

9.1. Как надо строить калькулятор. Не делать, как предлагает Страуструп – почётный доктор Университета ИТМО.

9.2. Как надо программировать лифт (http://is.ifmo.ru/projects/lift2/http://is.ifmo.ru/works/lift2.pdf). Не делать, как предлагает Кнут.

9.3. Как надо программировать систему сбора данных. Не делать, как предлагает Буч.

10. Инструментальные средства поддержки автоматного программирования

10.1. Конвертор Visio2Switch (http://is.ifmo.ru/automata/visio2switch/).

10.2. Автоматическая генерация программного кода. Подход описан в статье: Канжелев С.Ю., Шалыто А.А. Автоматическая генерация автоматного кода // Информационно-управляющие системы. 2006. № 6, с. 35-42.

10.3. Инструментальное средство для объектно-ориентированного подхода. Оно описано в статье: Гуров В.С., Мазин М.А., Нарвский А.С., Шалыто А.А. Инструментальное средство для поддержки автоматного программирования // Программирование. 2007. № 6, с. 65-80).

10.4. Использование UniMod в учебном процессе в Италии. https://sepl.dibris.unige.it/publications/2012-ricca-MiSE.pdf.

10.5. Мне кажется, что лучшее инструментальное средство для поддержки автоматного программирования – пакет Stateflow, который в последние годы активно использует мой аспирант в АО Концерн «НПО «Аврора» Ю.Ю. Янкин при программировании ПЛИС для управления шаговыми двигателями.

10.6. Для обеспечения импортозамещения другой мой аспирант в АО Концерн «НПО «Аврора» А.В. Калачинский разработал и активно использует инструментальное средство для поддержки автоматного программирования. Один из аспектов его применения описан здесь: Калачинский А.В., Ященко И.Н. Генерация описания работы автоматных программ в документ формата PDF // Системы управления и обработки информации. 2019. Вып. 44, с. 93-98 (https://www.avrorasystems.com/upload/iblock/cf3/cf3801161b1ca1a2fa7ba969079c45ec.pdf).

11. Учебные автоматные проекты

11.1. Курсовые проекты по автоматному программированию при использовании процедурного подхода, включающие проектную документацию, размещены здесь: http://is.ifmo.ru/projects/.

11.2. Курсовые проекты по автоматному программированию при использовании объектно-ориентированного подхода, включающие проектную документацию, размещены здесь: http://is.ifmo.ru/unimod-projects/. Применяемое инструментальное средство – разработанный нами UniMod. В качестве примера рекомендую посмотреть проект, расположенный по адресу: http://is.ifmo.ru/unimod-projects/camera/.

12. Генерация конечных автоматов для моделей самолётов

12.1. Поликарпова Н.И., Точилин В.Н., Шалыто А.А. Метод сокращенных таблиц для генерации автоматов с большим числом входных переменных на основе генетического программирования // Известия РАН. Теория и системы управления. 2010. № 2, с. 100-117. http://is.ifmo.ru/works/_polikarpova_samolet.pdf.

12.2. Александров А.В., Казаков С.В., Сергушичев А.А., Царев Ф.Н., Шалыто А.А. Применение эволюционного программирования на основе обучающих примеров для генерации конечных автоматов, управляющих объектами со сложным поведением // Известия РАН. Теория и системы управления. 2013. № 3, с. 85-100. http://is.ifmo.ru/works/2013/alexandrov_samolet.pdf.

13. Программирование логических контроллеров

Программируемые логические контроллеры (ПЛК) программировались и программируются в настоящее время в соответствии со стандартом IEC 1131-3, в котором описаны пять языков программирования. Говорят, что наиболее используемым из этих языков является язык «функциональных блоков». Однако, по-моему мнению, он обычно применяется не эффективно. А как надо?

Эффективное программирование в этом случае происходит, если набор функциональных блоков содержит блок «цифровой мультиплексор» – аналог конструкции switch в языках программирования. Тогда граф переходов изморфно реализуется с использованием такого мультиплексора. Реализация описана здесь: (http://is.ifmo.ru/books/switch_pdf/_switch4.pdf). Более 30 лет назад такие блоки уже входили в наборы блоков для программирования аппаратуры, например, аппаратуры Selma-2 фирмы ABB Stromberg (Финляндия).

Впервые этот подход мы использовали в 1991 г. при создании системы управления дизель-генератором ДГР-2А 500*500 судна проекта 15640 на базе аппаратуры Selma-2. Программирование выполнялось в НПО «Аврора» на языке функциональных блоков с использованием цифровых мультиплексоров.

При этом по графам переходов строились изоморфные им функциональные схемы, что до тех пор не делалось (Project 15640. AS21. DG21. Control. АМИЕ. 95564.12М. St. Petersburg. ASS «Avrora», 1991). Это позволило нашему немолодому сотруднику, который не умел программировать, успешно сдать указанную систему на судне, и закрыть построечное удостоверение раньше проектировщиков других систем комплекса, которые умели программировать, но делали это иначе... Этот сотрудник с моей помощью создал графы переходов и научился, как от них изоморфно переходить к текстам программ – к функциональным схемам, ядром которых были цифровые мультиплексоры. Незначительные изменения в программе, созданной таким образом, необходимость внесения которых возникла на судне, этот специалист смог успешно произвести. Аналогичная работа была выполнена нами и для судна проекта 15967.

Первый текст про автоматное программирование также появился в 1991 г.:  Шалыто А.А. Программная реализация управляющих автоматов // Судостроительная промышленность. Серия «Автоматика и телемеханика». 1991. Вып. 13, с. 41, 42.

В последние годы в мире начинает использоваться стандарт IEC 61499, определяющий построение распределённых сетей на ПЛК, в соответствии с которым поведение функциональных блоков предлагается описывать графами переходов непосредственно! (Pang C., Patil S., Yang C., Vyatkin V., Shalyto A. A Portability Study of IEC 61499: Semantic and Tools / 12th IEEE International Conference on Industrial Informatics (INDIN 2014). 2014. Port Alegre, Brazil, pp. 440-445.

14. Другие примеры применения автоматного программирования в промышленности

14.1. В 1993 г. использование графов переходов позволило при создании системы управления дизель-генератором  ДГР-2А 500*500 для судна проекта 15760 найти общий язык при взаимодействии с сотрудниками фирмы Norcontrol (Норвегия), для которых, как и для нас, английский язык не является родным. При этом мы научили наших партнёров программировать на языке ПЛ/М графы переходов, которые нами выдавались им в качестве технического задания. Применение графов переходов резко упростило наше взаимодействие с представителями фирмы, и они включили представленные нами графы переходов в документацию на систему, что до этого никогда не делали (Functional Description. Warm-up & Prelubrication Logic. Generation Control Unit. Severnaya Hull no. 431. Norcontrol, 1993. Использование формализации при выдаче технического задания позволило разделить работу, а главное, ответственность между нашими организациями. Это также позволило проводить корректировку алгоритмов и программ не в терминах судовых устройств, как это делалось до сих пор, а в терминах автоматов, что для программистов значительно проще и понятнее.

14.2. В 1999 г. графы переходов использовались при создании комплексной системы управления техническими средствами для судна проекта 17310 на базе ПЛК Autolog. Программирование было выполнено НПО «Аврора» на языке инструкций ALPro, который совместим c ассемблером микроконтроллеров Intel 8051. Для общесудовых систем оно выполнялось вручную, а для систем управления вспомогательными механизмами главного двигателя – с использованием транслятора «Ядро языка Си – язык ALPro», который был создан в НПО «Аврора» Б.П. Кузнецовым при участии автора. Во втором случае алгоритмы управления описывались графами переходов, после чего они изомофно реализовывались программой на языке Си, которая, в свою очередь, транслировалась в программу на языке ALPro.

14.3. Туккель Н.И., Шалыто А.А. Проектирование программного обеспечения системы управления дизель-генераторами на основе автоматного подхода // Системы управления и обработки информации. 2002. вып. 5, с. 66-82.

14.4. Туккель Н.И., Шалыто А.А. Система управления дизель-генератором (фрагмент). Программирование с явным выделением состояний. Проектная документация. 2002.

14.5. Системы управления для водоканала:

14.5.1. Вавилов В.К. Программируемые логические контроллеры SIMATIC S7-200 (SIEMENS). Методика алгоритмизации и программирования задач логического управления. 2005.

14.5.2. Вавилов В.К. Контроллеры SIMATIC S7-300 (SIEMENS). Организация взаимодействия независимых локальных систем управления на основе автоматного подхода и функционального разделения автоматов управления. 2005.

14.5.3. Вавилов В.К. LabVIEW и SWITCH-технология. Методика алгоритмизации и программирования задач логического управления. 2005.

В своё время автор этих работ спросил у своих сотрудников, как они относятся к автоматному программированию. Их ответ был аналогичен ответу Черчилля о демократии: «Это наихудшая форма правления, если не считать всех остальных опробованных».

15. Что такое автоматное программирование?

На онлайн-конференции по языку Оберон в 2020 г. Валерий Викторович Лаптев из Астраханского государственного технического университета при обсуждении моего доклада сформулировал утверждение: «Автоматное программирование – это программирование для непрограммистов».

С этим утверждением не согласился участник той же конференции главный эксперт АО «Русатом – Автоматизированные системы управления» (РАСУ) Дмитрий Викторович Дагаев: «Можно точно сказать: «Автоматное программирование – это программирование, объяснимое и для специалистов-непрограммистов. И, в отличие от других подходов, визуализируемое и масштабируемое». Меня такое несогласие вполне устроило!

16. Применение автоматов при программировании мобильных устройств

16.1. Клебан В.О., Шалыто А.А. Использование автоматного программирования для построения систем управления мобильными роботами (http://is.ifmo.ru/present/_kleban_shalyto.ppt).

16.2. Клебан В.О., Шалыто А.А. Использование автоматного программирования во встраиваемых системах (http://is.ifmo.ru/present/_kleban.ppt).

16.3. Клебан В.О., Шалыто А.А. Разработка системы управления малоразмерным вертолетом.

16.4. Kleban V. Fully autonomous helicopter flight (http://www.youtube.com/watch?v=-LuVLH4cV0U). (Более 10 000 просмотров).

16.5. Алексеев С.А., Калиниченко А.И., Клебан В.О., Шалыто А.А. Автоматический синтез системы управления мобильным роботом для решения задачи «Кегельринг».

17. Визуализация на автоматах

17.1. Программирование виджетов (Часть 1 –  https://www.ibm.com/developerworks/ru/library/wa-finitemach1/index.html. Часть 2 – https://www.ibm.com/developerworks/ru/library/wa-finitemach2/wa-finitemac_ru.html. Часть 3 –  http://www.interface.ru/home.asp?artId=7867).

17.2. Программирование визуализаторов алгоритмов (http://is.ifmo.ru/works/vis/http://is.ifmo.ru/works/art_vis.pdfhttp://is.ifmo.ru/works/visanim.pdf).

18. Программирование сложной игры

18.1. Озеров А.А. Четыре танкиста и компьютер (ещё раз об игре Robocode) // Магия ПК. 2002. № 11.

18.2. Туккель Н.И., Шалыто А.А. Система управления танком для игры Robocode. Объектно-ориентированное программирование с явным выделением состояний. Проектная документация 2001.

18.3. Кузнецов Д.В., Шалыто А.А. Система управления танком для игры Robocode. Вариант 2. 2003.

19. Протоколы

19.1. SMTP (http://is.ifmo.ru/projects/smtp/).

19.2. ТСР (http://is.ifmo.ru/download/red4.pdf).

20. Верификация

20.1. О сложности верификации простых программ.

20.2. Моделирование, спецификация и верификация «автоматных» программ (http://is.ifmo.ru/download/2008-03-12_verification.pdf).

20.3. NASA: миссия надежна.

20.4. Вельдер С.Э., Лукин М.А., Шалыто А.А., Яминов Б.Р. Верификация автоматных программ СПб.: Наука, 2014. 244 с.

21. Возможность обеспечения горячего резервирования

В ответственных системах для того, что избежать аварий, подобных описанной в https://habr.com/ru/post/448154/, необходимо применять горячее резервирование. Автоматы, особенно с многозначным кодированием состояний (переменных, кодирующих состояния, столько, сколько автоматов в системе), идеально подходят для этой цели, позволяя строить дублированные системы с синхронизацией состояний резервного и основного каналов.

22. Автоматное программирование при использовании ПЛИС

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

22.1. Статьи (http://is.ifmo.ru/works/_automata_plis.pdfhttp://is.ifmo.ru/works/2014/yankin-control-block.pdf).

22.2. Видео (http://is.ifmo.ru/present/2012/Yankin-Shalyto-PLIS.exe).

23. Применение автоматов для обеспечения верификации Smart Contracts

Наши выпускники Максим Коротков и чемпион мира по программирования 2004 г. Сергей Оршанский, которые в своё время прошли через мой проект по автоматному программированию, предложили подход к применению конечных автоматов для Ethereum Smart Contract в Blockchain (https://maximk.com/files/fa-draft.pdf). Контракты отличный объект для применения автоматов с целью обеспечения верификации, так как их код обычно небольшой и измеряется сотнями строк, а риски при традиционном написании контрактов очень велики.

Большинство контрактов пишется сейчас на тьюринг-полном языке Solidity. Авторы предполагали разработать язык автоматного программирования для Ethereum с названием Etherel, так как в нем должен быть синтаксис, похожий на используемый в языке Esterel. Код на таком языке может компилироваться в Vyper/Solidity и поддаваться формальной верификации.

В некотором смысле продолжение изложенного – «Ещё об автоматном программировании» – опубликовано здесь: https://vk.com/@1077823-esche-ob-avtomatnom-programmirovanii. При этом отмечу, что в конце этого текста приведено «несколько слов» об автоматах, нейронных сетях и, возможно, о будущем программирования.

16.02.2021 г.

Об авторе: докт. техн. наук, профессор, Университет ИТМО
Помещена в музей с разрешения автора 9 июля 2021