Печальная история о применении конечных автоматов в программировании
Соискатель бакалаврской степени написал выпускную квалификационную работу по построению программ с использованием стандарта IEC 61499 – открытого стандарта для построения распределенных систем управления и автоматизации https://vt.pnzgu.ru/files/vt.pnzgu.ru/sotrudniki/dubinin/dlya_rezyume/monografiya/fb_monography.pdf). В стандарте для описания поведения программ используются блоки, по сути являющиеся графами переходов конечных автоматов.
На защите молодой человек высказал следующую «мысль»: он в работе построил сверлильный станок. Это вызвало у меня большое сомнение, а вслух я предположил, что он на самом деле написал программу, управляющую станком. Молодой человек подтвердил мое предположение. После этого я спросил, построил ли он хотя бы один граф переходов, и получил утвердительный ответ.
Потом я поинтересовался у соискателя на каких языках он пишет программы на работе. Оказалось, что на Kotlin и Java. После этого я задал ему еще один вопрос: применял ли он графы переходов при написании (очень хотелось написать словосочетание «при проектировании», но я решил не пугать молодого человека) программ на указанных языках, за исключением каких-либо особых случаев, как, например, при поиске подстроки с помощью алгоритма Ахо-Корасик (https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Ахо-Корасик), который рассказывается в рамках курса «Алгоритмы и структуры данных» во всех университетах мира, где этот курс читается. Молодой человек уверенно ответил: «Нет».
Потом я спросил, а слышал ли он что-либо про автоматное программирование? И снова молодой человек произнес уверенное «Нет». Сказать, что в этот момент мне стало немного обидно – это, значит, ничего не сказать. Это связано с тем, что молодой человек заканчивает бакалавриат кафедры, на которой я уже 25 лет развиваю этот подход к программированию (https://is.ifmo.ru/). И это при том, что за указанное время по этой тематике было выполнено «немереное» число курсовых (https://is.ifmo.ru/projects/) и выпускных (https://is.ifmo.ru/diploma-theses/) работ, а также было защищено почти полтора десятка кандидатских диссертаций (https://is.ifmo.ru/disser/).
Конечно, я уже несколько лет не читаю этот курс, но отсюда не следует, что никто из других преподавателей кафедры и руководитель соискателя не могли хотя бы упомянуть про указанный подход, который относят к одной из парадигм программирования (https://znanierussia.ru/articles/Парадигмы_программирования), тем более, что я помню, что один из их основных преподавателей нынешних студентов был моим аспирантом и защищал диссертацию по этой тематике, не говоря уже о том, что некоторые из остальных преподавателей делали под моим руководством курсовики по автоматному программированию. Да и сам молодой человек, если бы не был лохом, мог бы в Интернете что-нибудь посмотреть (https://www.youtube.com/watch?v=PPWTxceMutk&t=149s) и почитать (https://is.ifmo.ru/books/_book.pdf) по этому вопросу. Однако, есть нюанс: для этого надо знать какой сделать запрос, а он об указанном термине даже не слышал…
Я утерся и задал молодому человеку следующий вопрос: «Не показалось ли Вам странным, что в стандарте, описывающем будущее промышленной автоматики, автоматы являются единственным средством описания поведения программ, а Вы в своей практической деятельности никогда не применяли автоматы? И не надо говорить, что управлением в промышленности Вы не занимаетесь…». Молодой человек честно ответил, что он об этом даже не думал – самому в голову не пришло, а из преподавателей никто его не «подтолкнул» в этом направлении.
Для того, что приобщиться к автоматному программированию, я предложил защищающемуся в магистерской диссертации переписать на автоматах одну или несколько программ, написанных им на работе с использованием флагов, и сравнить полученные программы.
Помню, что еще в августе 2002 г. появилась статья об использовании предложенного мной автоматного подхода к программированию в весьма странном месте: Вавилов К. Программирование за… 1 (одну) минуту... // Компьютер Price. 2002. № 31 (http://is.ifmo.ru/automata/1minute/). Константин однажды услышал мою лекцию, и понеслось…
После того, как я опубликовал тексты «Автоматное программирование» (https://vk.com/@1077823-vtomatnoe-programmirovanie) и «Еще об автоматном программировании» (https://vk.com/id1077823?z=article_edit1077823_62364), Костя написал мне: «Лично для меня это Великая история и несомненное применение в различных разработках алгоритмов и ПО. На любую критику есть конкретные примеры – реально работающие на объектах Петербурга и России, эффективные, задокументированные, понятные программы (http://is.ifmo.ru/automata/_metod065.pdf; http://is.ifmo.ru/automata/_s7300.pdf; http://is.ifmo.ru/automata/_vavilov2.pdf.zip). После этого я спросил Костю: «И сейчас применяешь?». Он ответил: «Да. По-другому уже не получается мыслить...».
У меня есть и другие подобные примеры, и хочется, чтобы и указанный выше молодой человек понял, что человечество не зря собирается строить свое будущее в промышленной автоматике на автоматах (https://vk.com/@1077823-pochemu-v-epohu-neironnyh-setei-dlya-upravleniya-otvetstvenn).
С этой надеждой я и заканчиваю писать этот текст, но меня не покидает ощущение, что нечто подобное мне придется говорить и писать неоднократно…
21.06.2023. https://d-russia.ru/pechalnaja-istorija-o-primenenii-konechnyh-avtomatov-v-programmirovanii.html
P.S. 1. Этот текст был прокомментирован так: «Согласен с Костей: «При проектировании ПО, если ты хоть раз попробовал автоматный метод проектирования, то по-другому уже и не хочется проектировать :)». Спасибо Вам, Анатолий Абрамович, опираясь на Ваши труды, я смог внедрить данный подход у нас на предприятии и проектировать качественное и надежное ПО. Этот подход и в настоящее время мы активно применяем и продвигаем» (С. Августанович, закончил кафедру «Системы управления» факультета «Компьютерные технологии, управление и радиоэлектроника» Южно-Уральского государственного университета, https://vk.com/avgustanovich_s).
2. На сайте онлайн-школы «Хекслет» среди курсов по обучению программированию на JavaScript я обнаружил курс «Автоматное программирование», который после 23.08.2020 г. еще раз был обновлен 23.09.2023 г. (https://ru.hexlet.io/courses/js-abp). В обращении к слушателям сказано, что в результате изучения курса «Вы научитесь: видеть автоматы в происходящих вокруг процессах; применять автоматное программирование для решения типовых задач, использовать шаблоны проектирования State и State Machine.
3. Особенно меня порадовало и удивило изучение второго паттерна, так как его разработали мы: Шамгунов Н.Н., Корнеев Г.А., Шалыто А.А. State Machine. Новый паттерн объектно-ориентированного проектирования // Информационно-управляющие системы. 2004. № 5, с. 13-25 (http://is.ifmo.ru/works/pattern/); Шамгунов Н.Н., Корнеев Г.А., Шалыто А.А. Паттерн State Machine. Внедрение. Сравнение с другими подходами (http://is.ifmo.ru/works/patterninc/); Шамгунов Н.Н., Корнеев Г.А., Шалыто А.А. State Machine – расширение языка Java для эффективной реализации автоматов // Информационно-управляющие системы. 2005. № 1, с. 16-24 (http://is.ifmo.ru/works/sm_language); Shalyto A., Shamgunov N., Korneev G. State Machine Design Pattern //.NET Technologies 2006. Shot communication papers conference proceedings. 4-th International Conference in Central Europe on .NET Technologies. University of West Bohemia. 2006, pp. 51-58. http://is.ifmo.ru/articles_en/2006/shalyto-shamgunov-korneev-2006.pdf.
4. После этого я написал «достаточно открытое» :-) письмо Георгию Александровичу Корнееву: «Дорогой Гоша! Люди за изучение паттерна State Machine, предложенного нами совместно с Шамгуновым платят деньги, а у нас автоматное программирование в курсах лекций по программирование даже не упоминают. Вот так... Настоящий тик-ток получается!».
Гоша ответил: «Уважаемый, Анатолий Абрамович! Если, по сути, то в этом (и даже большем) объеме рассказывается в курсе Андрея Станкевича. А если рассказывать основательно и обо всем, то, как Вы знаете, это отдельный курс получается. Так и живем».
Естественно, что он без моего ответа не остался: «Дорогой Гоша, не держи меня за ... В курсе Андрея рассказывается об автоматах, как в любых университетских курсах по этому вопросу, а совсем не об автоматном программировании, как его понимаю я и ты с Матвеем Казаковым на примере визуализаторов».
5. Второго ноября 2023 г. сооснователь онлайн-школы «Хекслет»
Кирилл Мокевнин опубликовал видео на тему «Конечные автоматы как способ значительно упростить логику и понимание кода» (https://www.youtube.com/watch?v=knoVv2ncwVI), в начале которой он сказал: «Это очень важная тема. Она одна из самых важных в программировании. Эта лекция не о техниках, а о мышлении. Поняв эту тему, Вы будете видеть все системы через призму конечных автоматов».
В этом ролике на засечке 12.35 появляется обложка моей с Надей Поликарповой книги «Автоматное программирование» (https://is.ifmo.ru/books/_book.pdf), но ни слова ни о ней, ни о нас не говорится. После этого я заинтересовался тем, что еще Мокевнин рассказывает свои слушателям про автоматы.
6. В сети обнаружил еще пять видео, в которых он мог обсуждать автоматное программирование. При этом четыре из них посвящены ментальному программированию, названному так Мокевниным: первый (https://www.youtube.com/watch?v=eEEHWQNuCLQ) был записан в 2013 г., второй (https://www.youtube.com/watch?v=JnURhIf194s) – в 2014 г., третий (https://www.youtube.com/watch?v=vkUTX1hruF8) – в 2018 г., а четвертый (https://www.youtube.com/watch?v=JnURhIf194s) – в 2021 г. Пятый ролик, опубликованный в 2015 г., называется так: «Почему трудно программировать UI», и первый слайд в нем говорит сам за себя: «UI. State Маchine». Никаких откровений про автоматы по сравнению с изложенным ниже этот ролик не содержит.
7. В первом из четырех роликов Кирилл пояснил, что такое ментальные модели (https://rightrack.ru/109mental_models?ysclid=lok210unjo117131164). Он поведал, что в психологии ментальной моделью называют трудно формализуемую совокупность эмпирических знаний, которые формируется в сознании человека при взаимодействии с объектом. Проще говоря, это о том, как мы представляем себе некий объект.
При этом под ментальным программированием он понимает такое написание программ, при котором для каждой из них по ее тексту можно понять не то, как она работает, а то, что программа делает – как решает задачу, для которой создавалась. Ментально построенная программа, с одной стороны, работает и читается так, как о ней говорил Заказчик, а с другой – все программисты, участвующие в ее разработке и использовании , смогут единообразно понять, что реализует программа.
После этого Кирилл привел основные положения философии языка Python, которым должны соответствовать и ментальные программы, написанные не только на этом языке: 1. Явное лучше неявного; 2. Красивое лучше уродливого; 3. Простое лучше сложного; 4. Сложное лучше запутанного; 5. Плоское лучше вложенного; 6. Сложно объяснимая реализация – плоха; 7. Особые случаи не настолько особые, чтобы нарушать правила.
Казалось бы, уже первое положение толкает для обеспечения ментальности к применению автоматного программирования, которое я назвал также «программирование с явным выделением состояний». Однако время использования автоматов для построения ментальных программ в сознании, о котором Кирилл говорит выше, тогда еще у него не наступило – на этой лекции про автоматное программирование не было сказано ни слова.
8. И это несмотря то, что книга Поликарпова Н.И., Шалыто А.А. Автоматное программирование. СПб.: 176 c. к тому времени уже была опубликована трижды – в 2009 г. (с издательскими неточностями) и корректно в 2010 и 2011 годах (о «куче» статей и двух других толстых книгах на эту тему, опубликованных мною к этому времени, я не говорю). При этом отмечу, что в Интернете эта книга опубликована в авторской редакции: https://is.ifmo.ru/books/_book.pdf. В 2014 г. эта книга стала «вечной» – в продаже появилось ее электронная копия (https://www.piter.com/product/avtomatnoe-programmirovanie).
Она была и на «Литрес» (https://www.litres.ru/book/anatoliy-shalyto/avtomatnoe-programmirovanie-585075/). Приведу некоторые комментариев оттуда: «Мой первый опыт программирования в данном стиле был связан с разработкой ПО под микроконтроллер STM32 для задачи управления несколькими двигателями с учетом показаний датчиков. Коллега порекомендовал почитать книгу «Автоматное программирование» и воспользоваться методами, указанными в ней. Результат превзошел мои ожидания: объем кода удалось сократить раза в два, а читаемость улучшилась. Примеры в книге понятны, язык доступен. Автоматное программирование оказало существенное влияние на мой стиль разработки ПО не только для микроконтроллеров, но и десктопных систем» (AlexisVaBel, 12 лайков), «По-моему, это очень глубокая книга, и при этом краткая. Автоматное программирование – один из подходов, который должен помочь решить основное противоречие современного IT: чрезвычайная сложность и частая изменчивость логики программ при одновременном требовании к их высочайшей надежности (предсказуемость, однозначность поведения и корректная обработка исключительных ситуаций)» (autoreg, девять лайков), «Автоматное программирование позволяет единообразно осуществлять разработку программного обеспечения, предназначенного для управления логическими контроллерами. Очень хорошо, что Шалыто настойчиво продвигает свою идею и хорошо, что это отечественное ноу-хау» (dastini, четыре лайка).
9. На второй лекции, которая прошла через год, Моковнин про автоматное программирование не сказал ни слова. Видимо, еще не знал о существовании автоматного программирования – ну, что делать?
10. На третьей лекции, состоявшейся еще через четыре года, за 10 минут до ее окончания (засечка 1.00.12) Кирилл вдруг стал отчаянно хвалить применение конечных автоматов и автоматного программирования применительно к построению ментальных программ. Он сказал, что автоматы применимы, если имеется процесс с дискретными состояниями. Поэтому автоматы могут использоваться практически везде: модель компьютера – совокупность автоматов, User Interface – то же самое, объект в объектно-ориентированном программировании – конечный автомат, в котором надо различать управляющие и вычислительные состояния (на их различие в свое время обратил внимание я) и т. д.
11. Как выглядит код без выделенных автоматов? Он похож на лапшу из условных переходов, в которой очень трудно разобраться и внести изменения. Когда такую программу переписывают с использованием автоматов, то по ней сразу видно, что она делает. Автомат отражает реальность. На самом деле переходы происходят именно так, как они описаны в автомате. Вместо набора переменных (флагов), косвенно реализующих состояния, при использовании автоматного программирования они с самого начала должны быть выделены явно, потом они также явно будут отражены в коде. Конечными автоматами, как отмечено выше, описывается практически все, с чем мы работаем.
Их достоинство состоит в том, что, по мнению Кирилла, при использовании автоматов не надо разрабатывать никакую документацию – просто открываете код и видите автомат, а этого достаточно, чтобы понять, что происходит. При таком подходе к программированию сам процесс как бы отделяется от кода, который его реализует. Автомат описывает поведение декларативно – как его описываете его поведение, он так и работает. Автоматы легко верифицировать (по этому вопросу много лет назад с моим участием в издательстве «Наука» была опубликована книга, https://is.ifmo.ru/verification/velder_verification_posobie_nauka.pdf).
По смыслу автоматы близки к ментальному программированию, и остается только понять, как их использовать в коде. Автоматное программирование, которое также называют программированием с явно выделением состояний (кстати, оба эти термина предложил я), является одной из главнейших парадигм программирования (автоматный подход к написанию программ я свое время назвал автоматной парадигмой программирования). «Это, действительно, фундаментальная вещь, относительно которой никто не спорит», – сказал Кирилл.
Последний слайд этой лекции назывался «Автоматно программирование». «Кто еще не использует автоматы, прочтите соответствующую книжку и начните их использовать», – в заключение сказал лектор.
12. Я в основном согласен с изложенным, тем более что в первом же комментарии к этому ролику, имевшему 33 лайка, была указана книга, на которую человек, призвавший все делать явно, сослался неявно.
Приведу этот комментарий: «Очень интересно и познавательно! Книга по программированию с использованием конечных автоматов, которую на лекции упомянул Кирилл – это Поликарпова Н.И., Шалыто А.А. Автоматное программирование». По моему мнению, этот комментарий было написать нетрудно, так как другой книги по этой тематике, по крайней мере на русском языке, нет!
После этого я прокомментировал утверждение Кирилла, с которым, якобы, никто не спорит: «О фундаментальности автоматного программирования никто не спорит только потому, что о нем практически никто даже не слышал, так как оно как парадигма программирования практически нигде не преподается, а даже там где оно преподавалось, последующие поколения студентов о нем тоже не слышали, хотя я 25 лет постоянно пишу и говорю о нем в русскоязычном Интернете. Но для того, чтобы автоматное программирование в нем обнаружить нужно, по крайней мере, сделать соответствующий запрос в поисковике, что практически никому даже в голову не приходит!».
А еще я не согласен с Кириллом в том, что при использовании автоматного программирования не нужна документация, так как она в этом случае из программной становится проектной, причем достаточно высокого качества (https://is.ifmo.ru/projects/).
13. К четвертой лекции про ментальное программирование, состоявшейся еще через три года, Кирилл, видимо, уже забыл о существовании автоматного программирования.
14. В этом уже, ставшем весьма длинным тексте, только в самом его начале были упомянуты графы переходов, которые в части поведения могут быть не только языком спецификации, но и языком программирования. При этом драйверы, реализующие входные и выходные переменные, обычно реализуются на другом языке.
О других особенностях автоматного программирования можно прочитать здесь: https://vk.com/@1077823-pochemu-v-epohu-neironnyh-setei-dlya-upravleniya-otvetstvenn
05.11.2023.