Сборка автомата (с примерами)

Программирование - Практика программирования

Посмотрим, нужен ли 1снику автомат, как его собрать и где это может пригодиться.

В этой статье поговорим про абстрактный автомат (надеюсь, все поняли правильно), а точнее, про одну из его разновидностей - детерминированный конечный автомат (ДКА) и о том, как его использовать в программировании

Чуть-чуть теории.

Конечные автоматы  принято определять как пятерку множеств A=(S, X, Y, δ, λ) : внутренние состояния, входной и выходной алфавит, функции переходов и выходов. Две ключевые  характеристики -  это  состояние S и входной алфавит X . Для ДКА это означает, что автомат работает дискретно и на каждом такте t, находясь в (одном) состоянии s(t) и в зависимости от входного воздействия x(t), переходит в (одно) состояние s(t+1) , генерируя при этом некоторое выходное воздействие y(t).

Для целей программирования удобно в качестве входных воздействий принимать результат вычисления некоторых логических выражений, а  выходным воздействиям сопоставить команды или процедуры.

Где  это  может пригодиться

Главный критерий, определяющий, стоит или нет применять автоматный подход в разработке программы — это сложность поведения той системы, которой необходимо управлять (объекта  управления). Конечно, можно написать автомат, складывающий 2+2, но особого смысла в этом нет).  Пожалуй, самый сложный и творческий этап в процессе конструирования - определить необходимый уровень абстракции. Число состояний автомата должно быть конечным и обозримым (простым для восприятия), в тоже время  содержать в себе всю логику объекта управления.  Основной   задачей   автоматных программ  является  отделение логики  программы от ее семантики и в этой связи  они  практически всегда сопровождаются поддерживающими диаграммами или таблицами.

Немного схем.

Как уже было сказано, ДКА принято изображать в одном из двух представлений: в виде таблицы переходов и выходов или в виде ориентированного графа состояний. Второй способ нагляднее, поэтому немного порисуем.

Примечание: Все схемы и примеры в этой статье будут очень простыми. Кроме того, они не соответствуют каким либо стандартам (если таковые имеются) и не являются единственно правильными. Любой автомат может быть построен разными способами , главное, чтобы он отвечал на вопрос «Что делает система».

 

1. Начнем с чего нибудь простого, например, с обычной лампочки. Наш автомат будет считывать положение тумблера и отображать состояния. Схема такого автомата будет выглядеть примерно так.

2. Теперь представим, что нас попросили сотворить маленькое чудо для детского новогоднего утренника. Когда дети будут кричать «Елочка, гори» - лампы на елочке должны загореться, а когда будут кричать «Елочка, не гори» - потухнуть. Допустим, устройство, которое умеет различать голосовые команды, запоминать состояния и включать/ выключать лампочки, у нас уже есть. Осталось только задать его логику.

На схеме видно, что помимо нескольких переменных X, задающих логику переходов, появились еще выходные воздействия Y. Если вы обратили внимание, петли на вершинах S1 и S3 не обозначены. В коде они просто пропускаются по умолчанию :

Если X1 Тогда ..
// ИначеЕсли  !X1

но подразумевается, что они есть, и автомат находится в некотором «устойчивом» состоянии.

 

3. Условия третьей задачи : Если кто-то балуется  со светом , а точнее  включает и выключает свет > 3 раз в течение 3 сек, программа должна среагировать и выдать предупреждающее сообщение. Задача несложная,  решается на раз и без всяких автоматов. Автоматная реализация в бесплатной обработке ниже (*см. комментарии) , пока будете скачивать, открывать и щелкать вкл/выкл, подумайте, как бы вы составили этот алгоритм.

 

4. И напоследок специально для тех, кто любит задачи из практики.

Недавно потребовался инструмент для удобного редактирования независимого регистра сведений. Регистр состоит из 4 измерений(Номенклатура,ПередаточноеЧисло,МощьностьЭД, Комплектующее) и одного ресурса (Количество). В итоге получилось вот это:

Подробнее о том, как эта штуковина работает (с gif анимацией) можно посмотреть здесь

На выходе имеем отсортированную таблицу изменений, которую нужно построчно прочитать и сохранить в регистр. Казалось бы, все просто, но если вглядеться повнимательнее, видно, что некоторые записи нужно удалить, где-то изменить значения измерений или ресурса, а где-то добавить новые записи. Дело было в конце дня в пятницу и думать было лень, поэтому я стал рисовать на листочке бумаги схему.

Извините за каракули и корявый почерк.  Работает  так: в  каждой итерации читается  очередная строка таблицы и набор записей регистра (отбор по заполненным значениям ). Я установил 4 входящих события X1 – X4 и 5 команд : Y1- ничего не делать, Y2- удалить из регистра, Y3- изменить только измерения набора данных, Y4 - записать новый набор данных , Y5 изменить измерения и ресурс(Количество) . Двойной обводкой обозначены финальные состояния. Ну и сам код.

	Для Каждого СтрокаТЗ Из ТЗ Цикл
		НаборЗаписей=РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьНаборЗаписей();
		НовыеЗначенияИзмерений=Новый Структура;
		НовыеЗначенияИзмерений.Вставить("Номенклатура",Объект.Номенклатура);
		Отбор=НаборЗаписей.Отбор;
		Отбор.Номенклатура.Установить(Объект.Номенклатура);
		ВыбраноИзмерений=0;
		Для Каждого КолонкаТЗ Из ТЗ.Колонки Цикл
			Если Найти(КолонкаТЗ.Имя,"Удалить")>0
				ИЛИ Найти(КолонкаТЗ.Имя,"Количество")>0
				ИЛИ Прав(КолонкаТЗ.Имя,1)="N"Тогда 
				Продолжить;
			КонецЕсли;
			Если ЗначениеЗаполнено(СтрокаТЗ[КолонкаТЗ.Имя]) Тогда
				Отбор[КолонкаТЗ.Имя].Установить(СтрокаТЗ[КолонкаТЗ.Имя]);
				НовыеЗначенияИзмерений.Вставить(КолонкаТЗ.Имя,СтрокаТЗ[КолонкаТЗ.Имя+"N"]);
				ВыбраноИзмерений=ВыбраноИзмерений+1;
			КонецЕсли;	
		КонецЦикла; 
		НаборЗаписей.Прочитать();
		ЛокальныеПеременные=Новый Структура();
		ЛокальныеПеременные.Вставить("П1",НаборЗаписей.Количество()>0);
		ЛокальныеПеременные.Вставить("П2", СтрокаТЗ.Удалить);
		ЛокальныеПеременные.Вставить("П3",Не СтрокаТЗ.Удалить  И ВыбраноИзмерений=3 И НЕ СтрокаТЗ.КоличествоN=0);
		ЛокальныеПеременные.Вставить("П4", ВыбраноИзмерений=3);
		ЛокальныеПеременные.Вставить("П5", СтрокаТЗ.КоличествоN=0);
		ОбновитьРегистр(НаборЗаписей,СтрокаТЗ.КоличествоN,НовыеЗначенияИзмерений,ЛокальныеПеременные);
	КонецЦикла;


Процедура ОбновитьРегистр(НаборЗаписей,НовоеКоличество,НовыеЗначенияИзмерений,ЛокальныеПеременные)
	Состояние=0;
	Сч=0;
	Пока Сч<5 Цикл
		Если Состояние=0 Тогда
			Состояние=?(ЛокальныеПеременные.П1,1,2);
		ИначеЕсли Состояние=1 Тогда 
			Состояние=?(ЛокальныеПеременные.П2,4,3);
		ИначеЕсли Состояние=2 Тогда
			Состояние=?(ЛокальныеПеременные.П3,5,6);
		ИначеЕсли Состояние=3 Тогда
			Состояние=?(ЛокальныеПеременные.П4,8,7);
		ИначеЕсли Состояние=4 Тогда
			//удалить данные регистра
			НаборЗаписей.Очистить();
			НаборЗаписей.Записать();
			Прервать;
		ИначеЕсли Состояние=5 Тогда
			//Записать новые данные
			МенеджерЗаписи = РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьМенеджерЗаписи();
			Для Каждого Элемент Из НовыеЗначенияИзмерений Цикл
				МенеджерЗаписи[Элемент.Ключ]=Элемент.Значение;
				МенеджерЗаписи.Количество=НовоеКоличество;
			КонецЦикла;
			МенеджерЗаписи.Записать();
			Прервать;
		ИначеЕсли Состояние=6 Тогда
			// Ничего не делаем
			Прервать;
		ИначеЕсли Состояние=7 Тогда
			// изменить регистр только Измерения
				тДанные=НаборЗаписей.Выгрузить();
				НаборЗаписей.Очистить();
				НаборЗаписей.Записать();
				НовыйНабор=РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьНаборЗаписей();
				НовыйНабор.Отбор.Номенклатура.Установить(Объект.Номенклатура);
				Для Каждого Элемент Из НовыеЗначенияИзмерений Цикл
					НовыйНабор.Отбор[Элемент.Ключ].Установить(Элемент.Значение);
					тДанные.ЗаполнитьЗначения(Элемент.Значение,Элемент.Ключ);
				КонецЦикла;
				НовыйНабор.Загрузить(тДанные);
				НовыйНабор.Записать();
			Прервать;
		ИначеЕсли Состояние=8 Тогда
			// изменить регистр
			Если ЛокальныеПеременные.П5 Тогда
				Состояние=4;
			Иначе
				тДанные=НаборЗаписей.Выгрузить();
				НаборЗаписей.Очистить();
				НаборЗаписей.Записать();
				НовыйНабор=РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьНаборЗаписей();
				НовыйНабор.Отбор.Номенклатура.Установить(Объект.Номенклатура);
				Для Каждого Элемент Из НовыеЗначенияИзмерений Цикл
					НовыйНабор.Отбор[Элемент.Ключ].Установить(Элемент.Значение);
					тДанные.ЗаполнитьЗначения(Элемент.Значение,Элемент.Ключ);
				КонецЦикла;
				тДанные.ЗаполнитьЗначения(НовоеКоличество,"Количество");
				НовыйНабор.Загрузить(тДанные);
				НовыйНабор.Записать();
				Прервать;
			КонецЕсли;	
		КонецЕсли;
		//	Сообщить("=>"+Состояние);
		Сч=Сч+1;
	КонецЦикла;
КонецПроцедуры
Этот код, конечно, далек от совершенства в плане производительности,  но в данном случае  я   решил этим пренебречь в пользу простоты .  На этом примере  хорошо видно, что  само "тело"  автомата  строится  в виде  циклической  программы.  В справочной литературе, как правило,   приводятся примеры,   построенные  по  так называемой switch-case   технологии,  но, к сожалению,  в 1С такая конструкция недоступна, поэтому обходимся тем, что есть.

Вместо заключения

Вы можете спросить меня, зачем рисовать какие-то схемы, когда быстрее взять и написать код. В таком случае представьте себе, что  вместо 2-3 переменных, как-то влияющих на логику вашей системы, у вас их >10. Это как в шахматах - хорошие шахматисты могут думать на 4-5 хода вперед, гроссмейстеры на 6-8, гениальные на 9-10. Думаете, такого не бывает?. Бывает и еще как, особенно когда функционал наращивается постепенно, добавляются все новые и новые условия и система становится похожей на «тришкин кафтан», который после очередной перекройки  уже страшно трогать,  ибо может просто рассыпаться. В моей практике доходило до 12, но это уже тема совсем другой статьи из серии «личный опыт».

Литература:

  1. Поликарпова Н. И., Шалыто А. А. Автоматное программирование. 2008. СПб.

  2. Б.П.Кузнецов Психология автоматного программирования BYTE/Россия, 2000, №11 (ссылка)

Скачать файлы

Наименование Файл Версия Размер
Лампа
.epf 98,41Kb
19.09.17
23
.epf 98,41Kb 23 Скачать

См. также

Комментарии
2. Василий Зайцев (vasiliy_b) 273 19.09.17 14:47 Сейчас в теме
Спасибо. вспомнил институт. Ну и на практике так же приходилось стоить небольшие автоматы разборах xml
3. Игорь Пашутин (Alien_job) 128 19.09.17 14:49 Сейчас в теме
Этот код плох не тем что "далек от совершенства в плане производительности" а тем что его бесполезно читать без соответствующего листочка.
4. p m (pm74) 35 19.09.17 15:07 Сейчас в теме
(3) у меня на столе давно вместо листочков толстая тетрадь в клеточку .
мне кажется наоборот упрощается чтение собственного кода написанного давным давно ,
5. Призрак (davdykin) 17 19.09.17 19:04 Сейчас в теме
Не, читать такой код без графа потом просто жесть, но вообще технология интересная. Спасибо!
8. p m (pm74) 35 19.09.17 19:58 Сейчас в теме
(5) как я говорил решение использовать или нет зависит от сложности , для таких примеров как в статье пожалуй не стоит , а в случае сложных систем наоборот упростит понимание логики
9. p m (pm74) 35 19.09.17 20:08 Сейчас в теме
(5)(6) есть еще один немаловажный плюс о котором забыл упомянуть в статье.
т.к. программа фактически сводится к выполнению простых действий,то ( при условии если автомат правильно построен) отладка практически не требуется
10. Yan Tsys (YanTsys) 9 19.09.17 20:31 Сейчас в теме
(9) При условии если программа правильно построена отладка вообще никогда не нужна :)))
11. p m (pm74) 35 19.09.17 20:35 Сейчас в теме
(10) разница в том , что для автомата вам нужно протестировать модель , а не готовый прототип
12. Yan Tsys (YanTsys) 9 19.09.17 20:47 Сейчас в теме
(11) Тестирование модели - это такое новое название для отладки? :))) не заморачивайтесь, я не спорил, это вроде как шутка была :)
14. p m (pm74) 35 19.09.17 20:56 Сейчас в теме
(12) точно в конце дня уже заговариваться стал ))
13. Yan Tsys (YanTsys) 9 19.09.17 20:55 Сейчас в теме
(11) а если серьезно то для вашего автомата можно было бы продумать промежуточные функции сборщики поступающих данных и результата выполнения, может быть даже отправку статистики автору :) получился бы универсальный блок автоматического тестирования.

Автоматическое тестирование собственного кода считается одним из признаков настоящего профессионализма в программировании.
15. p m (pm74) 35 19.09.17 21:03 Сейчас в теме
(13) здесь специально старался сделать код как можно доступнее и понятнее
16. Yan Tsys (YanTsys) 9 19.09.17 21:09 Сейчас в теме
(15) и правильно сделали, очень понравилось, если будет продолжение с удовольствием почитаем
17. p m (pm74) 35 19.09.17 21:10 Сейчас в теме
18. Yan Tsys (YanTsys) 9 19.09.17 21:29 Сейчас в теме
(17) Интересно насколько ваша статья с таким заголовком да еще и с вступлением
Посмотрим, нужен ли 1снику автомат, как его собрать и где это может пригодиться.

применима к теме
https://forum.infostart.ru/forum1/topic176445/
21. p m (pm74) 35 20.09.17 07:02 Сейчас в теме
(18) это просто шутка . Мыже с вами программисты а не милитаристы. Давайте собирать а-т Мили вместо Калашникова
6. Yan Tsys (YanTsys) 9 19.09.17 19:44 Сейчас в теме
Интересное решение
Недавно в аналогичной ситуации применил рекурсивную функцию с накоплением данных в соответствии которое являлось параметром функции...
7. p m (pm74) 35 19.09.17 19:54 Сейчас в теме
(6) решение не новое , книг по автоматному программированию довольно много
19. Призрак (davdykin) 17 20.09.17 06:30 Сейчас в теме
Блин, как не хватает гитхаба для 1С, все-таки коллективная доработка таких "самописных" инструментов мне кажется могла бы очень многое изменить. Форкнул, доработал то, что нужно, скинул автору - автор слил.
20. Mary noskova (user826590) 20.09.17 06:48 Сейчас в теме
(19)
Блин, как не хватает гитхаба для 1С, все-таки коллективная доработка таких "самописных" инструментов мне кажется могла бы очень многое изменить. Форкнул, доработал то, что нужно, скинул автору - автор слил.


это интересное предложение, может быть разработчики 1С примут его к сведению
22. Игорь Пашутин (Alien_job) 128 20.09.17 09:38 Сейчас в теме
(19) Для 1с подходит обычный гитхаб
23. Призрак (davdykin) 17 20.09.17 10:24 Сейчас в теме
(22) Как -то я это слабо вижу, git сравнивает файлы по содержимому, т.к. в большинстве языков программирования это обычный текст, а у 1С это бинарные файлы, поэтому как вы планируете делать слияние двух веток - для меня большая загадка.
24. борян петров (TODD22) 16 20.09.17 10:26 Сейчас в теме
(23)Всё уже давно придумано. Есть софт который разбирает файлы на код и отправляет в гит.
27. Ivan Khorkov (vano-ekt) 944 22.09.17 08:06 Сейчас в теме
25. Валентин Бомбин (so-quest) 127 20.09.17 11:32 Сейчас в теме
Тема КА - безусловно очень интересна и наверное неисчерпаема. Что бы не мучаться с листочком и не хранить эти каракули - смотри в сторону ragel или smc. Код КА не надо писать. Он должен генерироваться.
30. p m (pm74) 35 24.09.17 20:56 Сейчас в теме
(25) Вы безусловно правы. Более того можно написать движок автомата скажем в виде рекурсивной функции которая будет принимать в качестве параметров данные некоторых хранимых таблиц. Пока же мне интересно определить области применимости автоматного программирования в 1с как альтернативы традиционному процедурному подходу. Например можно ли рассмотреть управляемую форму как некий объект "реактивного" типа с "внешним" управлением? Вобщем пока в стадии экспериментов.
26. Игорь Пашутин (Alien_job) 128 20.09.17 13:47 Сейчас в теме
(23)
Конфигурация - Выгрузить конфигурацию в файлы
Внешняя обработка - Выгрузить в файлы
28. Andrey Erastov (tailer2) 22.09.17 10:18 Сейчас в теме
29. Александр Крынецкий (echo77) 744 23.09.17 17:40 Сейчас в теме
Так и не понял зачем это нужно
31. p m (pm74) 35 24.09.17 21:11 Сейчас в теме
(29) может и не нужно , каждый решает для себя.
вкратце для систем со сложным поведением предлагается предварительно построить автоматную модель управления
напр. аналог в UML - это диаграммы состояний
32. Александр Цуканов (tsukanov) 37 25.09.17 14:53 Сейчас в теме
Состояния, имхо, лучше строками обозначать со смыслом, а не числами.
Тогда и комментарии станут лишними
33. Владимир Крючков (ivanov660) 409 25.09.17 16:38 Сейчас в теме
На самом деле графическое представление схемы автомата можно нормально редактировать в виде таблицы переходов.
График красив, кода состояний не более 10. А если увеличим, тогда становится совсем уж не наглядно, и придется львиную долю уделять "красивости/понятности".
Оставьте свое сообщение