В рунете лежит великолепная, но трудная для начинающих статья Б. П. Кузнецова «Психология автоматного программирования». Для специалистов не секрет, что знание принципов автоматного программирования дает возможность почти бездумно (и безошибочно), «пальцами» писать программы высочайшего уровня сложности. Редакция от 10.05.2021.
Создан 29.05.2005 9:49:02
Несколько абстрактное изложение Б. П. Кузнецова побудило автора настоящей статьи «навести мосты» к теории конечных автоматов от практики, от конкретных исходных модулей, для тех, кто о теории конечных автоматов и слыхом не слыхивал. Ибо текст программы для многих более «нагляден» по сравнению с «произвольным циклическим алгоритмом, представленным в виде графа переходов конечного автомата». Из статьи Б. П. Кузнецова:
Теорию автоматов преподают не везде. В технических ВУЗах преподают эту теорию применительно к синтезу цифровой аппаратуры, но не применительно к программированию (Такие выводы сделаны моим коллегой Шалыто А. А. для ведущих Питерских ВУЗов).
Автор прав. К сожалению, теория конечных автоматов и формальных языков читалась далеко и не в каждом московском ВУЗе. Автору настоящей статьи, выпускнику факультета электронной техники МЭИ, теория сия не читалась тоже. О существовании теории конечных автоматов было вскользь упомянуто в курсе цифровой схемотехники.
Жизнь - штука тонкая. Многим, кто окончил технические ВУЗы в начале (середине) восьмидесятых, пришлось не единожды менять область деятельности. Схемотехник вдруг начинал заниматься тонкопленочной технологией производства интегральных схем, специалист по электровакуумным приборам «вклинивался» в микропроцессорную схемотехнику. Выручало полученное в советских ВУЗах «широкое» образование, «ничего обо всем». Спасибо дорогому Леониду Ильичу за наше счастливое детство 😉
Автора настоящей статьи, как и «других похожих», жизнь (году в 1994-ом) вынудила забросить любимое «паяло» и погрузиться в разработку программ. По мере усложнения задач логики, здравого смысла, ВУЗовских знаний и навыков программирования, полученных самостоятельно, стало не хватать. Нехватка особенно сказывалась при разработке «коммуникационных» программ, реализации протоколов обмена данными. Организация взаимодействия пары модемов, обменивающихся данными по телефонной линии, казалась (в те времена) автору задачей почти неразрешимой.
Помощь подоспела вовремя со стороны старших товарищей, выпускников ВМиК МГУ, посвятивших автора настоящей статьи в основы теории конечных автоматов и показавших примеры реализации указанной теории на практике (одним из них - по странному стечению обстоятельств - был тоже Кузнецов, но другой). Достаточно сложный протокол обмена данными, работающий «поверх» протоколов физического и вышележащих уровней (транспортного, сетевого, сеансового, прикладного - перечислите для самопроверки в правильном порядке 😗), был быстро и безошибочно реализован.
Сейчас автору приходится программировать «раз в год по-обещанию», когда «припрет». Но навыки автоматного программирования выручают по сей день, позволяя решать сложные задачи быстро, бездумно, и (почти) без ошибок, т.е. без отладки.
Автор настоящей статьи твердо убежден, что ни один из тех, кто читает ее в настоящий момент времени, не думает, поднося ко рту ложку борща, бутерброд с икрой или стакан водки (рюмку коньяку - каждому свое). Все это получается само собой, рефлекторно. И читатель никогда не «промахнется», не пронесет вожделенное мимо рта. Так почему же нельзя также рефлекторно программировать?
Статья доктора наук Б. П. Кузнецова, изложенная «академически сдержанно», - крик души.
Однако после его [автоматного программирования] освоения возникает вопрос: как я мог программировать иначе? Автоматное программирование позволяет решать практически любые сложные циклические задачи с минимальными затратами на отладку.
Так и есть. Иные технологии программирования стоит рекомендовать лишь тем, кто склонен к садомазохизму.
Актуальность автоматного программирования
Почему же приемы автоматного программирования особенно актуальны сейчас? Имеют место две проблемы:
- непредсказуемое поведение кода программы, разработанной средствами RAD;
- угасание «культуры программирования».
Непредсказуемое поведение кода программы, разработанной средствами RAD
В начале девяностых появились средства быстрой разработки приложений (RAD - Rapid Application Development), к которым относятся, в частности, такие известные продукты от Borland, как Delphi и C++. Перечисленные системы программирования позволяют не только программировать в привычном смысле слова, но и фактически рисовать программы, перестаскивая в оконные формы визуальные компоненты из VCL.
Любой визуальный объект VCL характеризуется рядом свойств, методов и событий. Казалось бы, простой манипуляцией перечисленными атрибутами возможно заставлять разрабатываемую программу делать то, что требует от нее программист-разработчик. Не тут-то было.
Чарлз Калверт во вводной главе «Визуальное программирование - это RAD» своей книги «Delphi 2. Энциклопедия пользователя» честно признается:
Одна из ироничных сторон сред, подобных Delphi, заключается в том, что она представляет собой огромное благо для начинающих, но иногда путает опытных программистов... Так, VCL имеет тенденцию скрывать точную реализацию определенных объектов, тем самым не давая посторонним менять умалчиваемое поведение кода,
что в переводе с буржуйского на русский означает непредсказуемость маршрута выполнения программы или функциональных объектов.
Поведение программы, нарисованной с помощью средств RAD, не всегда очевидно даже для опытного программиста, не говоря уж о начинающем. Автор статьи неоднократно убеждался в этом лично, пользуясь средствами пошаговой отладки Delphi. Программа, несмотря на «очевидность» авторского кода, всегда стремится пойти своим путем, попадая в такие замысловатые обработчики событий, о существовании которых можно даже и не догадываться.
Таким образом, ироничная сторона и огромное благо кое-кому выходят боком, ибо умалчиваемое поведение кода - коварство и тайная подлось средств RAD. Классический пример непредсказуемого поведения кода наглядно продемонстрировал поэт, «основоположник» объектно-ориентированного программирования. Поэт, который для нас - «всё» 😇
Примечание от 10.06.2014 г. - На днях поэту исполнилось бы 215 лет, но Яндекс из каких-то своих соображений отмечал 30-летие тетриса.
Смотрите: |
«Мой дядя - самых честных правил
Когда не в шутку занемог,
Он уважать себя заставил
И лучше выдумать не мог...»
Что представляет собой «дядя Пушкина» с позиции объектно-ориентированного программирования:
Каково же поведение TUncle? Как только значение свойства Health было изменено кодом программы (на целочисленное «занемог» 😇, «выстрелила» функция Respect («уважать себя заставил»). А должна ли была? Необязательно, поскольку имеется функция Think, посредством которой дядя мог бы выдумать что-нибудь и получше 😇 Возможно, интерпретация не вполне корректна, зато наглядна.
Культура программирования
О культуре программирования можно сказать лишь то, что она, культура, медленно, но верно угасает. (Программисты-профессионалы советской школы смахнули, наверное, скупую мужскую слезу) 😇 Сейчас все больше кодировщики, отличающиеся от программистов-разработчиков тем, что неспособны как поставить задачу, так и описать ее в программных документах.
Выводы
Выводы:
- поведение кода программы, разработанной исключительно средствами RAD, изначально непредсказуемо;
- чтобы поведение кода программы стало предсказуемым, следует научиться управлять поведением кода.
Как научиться управлять поведением кода программы?
Очень просто - приемом автоматного программирования - расстановкой «контрольных точек» с использованием оператора case - программной реализацией конечного автомата.
Реализация конечного автомата
В качестве примера реализации конечного автомата, наглядно иллюстрирующего смысл расстановки контрольных точек, используем лыжный кросс, сдавать который, с обязательным требованием уложиться в нормативы времени, приходилось каждому.
Смотрите: |
Лыжный кросс - расстановка контрольных точек
На рисунке выше изображена лыжная трасса. Точка 0 - старт и финиш, точки 1-7 - контрольные. В контрольных точках находятся судьи, фиксирующие время прохода и нагрудный номер лыжника.
При подобной организации сдачи норматива по лыжному кроссу лыжник оказывается «зажатым» контрольными точками в траекторию лыжной трассы. Если на финише выясняется, что лыжник не прошел хотя бы одну из контрольных точек - пересдача неминуема. А если «срезать углы» между контрольными точками?
Однажды жизнь поставила перед выбором: либо километров десять по кривой, разбитой, но асфальтированной дороге, либо «срезать» и пройти напрямую, через лесок, километра три. Три километра «по прямой» оказались топью (дело было в Белоруссии) и были преодолены часа за четыре. Жизнь опровергла утверждение, что «кратчайшим расстоянием между двумя точками является прямая», и подтвердила иное - «суха теория, мой друг, но древо жизни пышно зеленеет».
Попытка «срезать углы» между контрольными точками по «красной» траектории либо не даст существенного выигрыша во времени, либо приведет к существенной потере оного. Не уложился в норматив - пересдача.
Программно реализовать «сдачу норматива по лыжному кроссу» несложно в виде конечного автомата.
Программная реализация конечного автомата
При реализации конечного автомата алгоритм был слегка усложнен. Лыжник должен нестись со скоростью звука, время пробега от предыдущей к следующей контрольной точке ограничено пятью секундами.
Конечный автомат реализован с помощью Delphi 7. На форму сброшены 8 кнопок, 0 именуется btnStart, остальные - cp1-cp7 (cp - control point). Нажатие кнопки эквивалентно проходу лыжником контрольной точки. Обработчиком событий OnClick всем восьми кнопкам назначена единая, заранее подготовленная процедура Release.
Метки Label1-3 подсказывают лыжнику-пользователю, какую кнопку придется нажимать следующей, показывают остаток времени до нажатия и результат. Фрагменты текста программы конечного автомата приведены ниже.
Текст программы конечного автомата
Как работает конечный автомат
Программа сразу после своего запуска отобразит сообщение пользователю - «Жми кнопку 0». Каковы могут быть ответные действия:
- пользователь с шаловливыми ручонками будет жать все, что угодно, кроме кнопки 0;
- послушный пользователь нажмет кнопку 0.
Реакция конечного автомата на шаловливые ручонки
Следует отметить, что непослушный пользователь может жать кнопки до скончания света, но ничего у него не выйдет. Нажатие любой из кнопок cp1-cp7 до нажатия кнопки btnStart конечный автомат попросту проигнорирует, поскольку в процедуре Release имеются строчки:
Во фрагменте кода конечного автомата отсутствует «ловушка» для переменной mode, равной 0. Код, расположенный внутри оператора case, выполняться не будет. Программа просто его обойдет. Указатель текущей строки кода в режиме отладчика (просто указатель) будет упрямо возвращаться к началу процедуры.
Реакция конечного автомата на послушного пользователя
Как только пользователь нажмет кнопку 0 (btnStart), переменные режима mode и s_mode примут значения 1 и 0 соответственно. Указатель «провалится» в процедуру прохода «контрольной точки» и окажется внутри ветки 0 case s_mode of.
Кнопка btnStart станет недоступна и, вот она, фишка (!!!), s_mode примет значение 1. Сие означает, что автомату присвоено следующее состояние. Весь остальной код, размещенный между begin-end, - шелуха, вернее, тот самый код, управлять выполнением которого призван конечный автомат. В первую очередь, сразу после begin, необходимо перевести автомат в следующее состояние. То, что автор сначала вставил код btnStart.Enabled:=True; - наглядный пример разгильдяйства и отсутствия культуры программирования 😇
Далее, после выполнения кода
конечный автомат будет ожидать события OnClick кнопки cp1, которой и соответствует состояние s_mode=1. Никакими уговорами пользователь не сможет заставить конечный автомат отреагировать на нажатие любой другой кнопки, кроме cp1, поскольку при неравенстве переменных o_mode («ожидаемой» кнопки) и s_mode (реально нажатой кнопки) указатель будет тупо возвращаться к началу процедуры - ждать события OnClick именно кнопки cp1.
Более того, указанный выше код конечного автомата запускает таймер. Таймер тихо отсчитывает пять секунд и останавливает «лыжный кросс», если пользователь так и не нажал кнопку cp1.
Указанным способом особенно удобно «строить» коммуникационные программы, реализующие протоколы обмена. Допустим, конечный автомат А из состояния 1 отправил байтовую последовательность (1) конечному автомату В, перешел в следующее состояние (2) и ждет четкого ответа (2) от автомата В. Автомат В может слать в линию все, что угодно (в течение пяти секунд). Но, если в течение пяти секунд автомат А не получит ожидаемого ответа (2) от автомата В - все, трындец. Таймер оповещает, что ожидаемый ответ от автомата В в заданном интервале времени не получен. Пользователь четко видит, где, на каком шаге конечного автомата произошел сбой при обмене данными. И принимает командирское решение.
Поскольку разъяснять словами все то, что «вытворяет» конечный автомат, довольно сложно, автор настоятельно рекомендует «погонять» конечный автомат в режиме пошаговой отладки. В режиме отладки следует закомментировать строку пуска таймера (Timer1.Enabled:=True;).
Модификация конечного автомата
Можно «поиграть» кодом конечного автомата: закомментировать часть кодов, поставить метку 1: напротив case s_mode of и добавить во все ветки, кроме крайней, goto 1.
Оператор goto, выполняющий безусловный переход к метке 1, многие программеры готовы «порвать, как Тузик тряпку» (искоренить из всех существующих языков программирования). Во многом они правы, но как быть без goto в конечном автомате? Может, кто знает, и готов поделиться соображениями? Уж лучше искоренили бы условный оператор if. Именно в операторе if (then, else) автор статьи видит причины всех программерских проблем, бед и неудач.
При внесенных в код изменениях конечный автомат последовательно «прогонит» указатель по веткам программы и остановится, ожидая очередного нажатия кнопки 0. Иными словами, конечный автомат после «пинка» пользователя самостоятельно пройдет все ветки программы, все контрольные точки, которые явно указал программист и, как все нормальные автоматы, вернется в свое исходное состояние.
Аналогия с автоматом для газированной воды. Скормили автомату три копейки, нацедил он стакан газировки с грушевым сиропом и вернулся в исходное состояние - ждать, когда кто-нибудь скормит ему очередную монетку.
Такой прогон удобно смотреть средствами отладки.
Примечание - После end; {7:} в программу стоит добавить оператор else, который позволит обрабатывать тупиковые ситуации.
Выводы
Выводы следующие.
Конечный автомат работает по принципу «шаг в сторону - расстрел» (пересдача нормативов по лыжному кроссу). «Увильнуть» или «схитрить» конечный автомат не даст ни пользователю (исходный вариант кода), ни самой программе (модифицированный вариант кода). Автомат вынудит и того, и другого пройти «контрольные точки» именно так, как расписал программист.
Код конечного автомата изобилует ветвлениями, но ветвлений - логических структур «выбор» - в явном виде как будто бы и нет. Оператор case делает текст программы настолько «прозрачным», что на вопрос «а что будет, если» любой ткнет пальцем и попадет в самую точку. А насколько «прозрачна» конструкция if a>0 then b:=0 else if a<0 then b:=a else if a<>b then (и так далее...)? Это к вопросу о культуре программирования - написанию легко читаемого кода.
Код конечного автомата взаимно-ортогонален. При модификации кода, при добавлении в код новых case-фрагментов изменять исходный код не потребуется. Программа не «поползет» - снижается вероятность ошибок при кодировании.
Заключение
Коль скоро было упомянуто о Пушкине, грех не вспомнить о Маяковском, предвосхитившем «рождение» оператора case (но без его фирменной «лесенки»).
«От вороны карапуз
убежал, заохав.
Мальчик этот просто трус.
Это очень плохо.
Этот, хоть и сам с вершок,
спорит с грозной птицей.
Храбрый мальчик, хорошо,
в жизни пригодится».
_________________________________________________________________
Вот, что получается:
case мальчик of
трус: мальчик.характеристика:='плохо';
храбрый: мальчик.характеристика:='хорошо';
end;
Теперь, когда из примеров стало ясно, как конечный автомат управляет поведением кода программы, можно смело приступать к чтению статей профессора Б. П. Кузнецова и к разбору «произвольных циклических алгоритмов, представленных в виде графа переходов конечного автомата» 😅 Удачи!
