Портал Python-программистов

Форумы сайта python.com.ua

Вы не зашли.

Объявление

Открыт официальный канал портала на pythonua@conference.jabber.ru читать подробности
  • > Python
  • > finite state machine на Питоне [RSS Feed]

#1 2007-05-28 17:13:53

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

finite state machine на Питоне

Возникла необходимость реализации.
Пока нашел только два достойных варианта:
fsm из panda3d и epsilon.modal из divmod.org команды. modal, кажется, куда лучше.
Может, еще что посоветуете?
Хоть тема в вебе и не нужна практически, но в standalone клиентах часто требуется


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

Неактивен

 

#2 2007-05-28 23:31:18

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

По своему опыту знаю, что под FSM часто понимают весьма разные вещи. Может уточните?

Названные вещи не видел.
Но видел рецепт в поваренной книге на сайте ActiveState. Очень просто и логично.
Плюс пытался пользоваться генератором SMС. Ну и гадость этот SMС скажу я вам. Хотя... на вкус и цвет...
Кажется еще в проекте WhatOS было что-то.

Посмотрю названные вами либы. Может пойму, что именно вам нужно.

Отредактированно bialix (2007-05-29 01:45:07)


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#3 2007-05-29 00:17:50

proDiva
Питонер
Откуда: Черкесск
Зарегистрирован: 2007-02-15
Сообщений: 111
Рейтинг :   
Профиль

Re: finite state machine на Питоне

Так интересно узнать новые термины (вернее не новые, но мне пока неизвестные). Расскажите, пожалуйста, на русском языке, что такое "finite state machine"? заранее благодарна


Ах вот ты какой, питончик аленький!))

Неактивен

 

#4 2007-05-29 01:17:18

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

По рюсски -- это конечные автоматы.

Вот здесь неплохое введение для чайников: http://softcraft.ru/design/ap/ap01.shtml

А здесь: http://softcraft.ru/auto.shtml
туча статей на эту тему, для более глубокого погружения.

Можно видеть, что автоматное движение имеет несколько основных направлений и идеологий: switch и КА.
Также неплохо почитать статью о состоянии дел за рубежом, искать по ключевому слову "синхронное программирование" (гугля с википедией рулят)
http://www.softcraft.ru/auto/switch/syn … ndex.shtml

Вот на википедии: http://ru.wikipedia.org/wiki/%D0%90%D0% … 0%B8%D0%B5

Вобщем для старта этого будет достаточно.

Отредактированно bialix (2007-05-29 01:22:21)


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#5 2007-05-29 01:42:27

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

bialix написал:

Посмотрю названные вами либы. Может пойму, что именно вам нужно.

Посмотрел. В общем понятно к чему вы стремитесь.
Хотя по-прежнему считаю, что FSM нужно описывать не программно, а через понятные человеку диаграммы или что-то типа специализированного DSL. А из этого понятного описания генерить код автоматом.

Имел очень приятный опыт общения с генератором IAR Visual State (для Си и за деньги).

Пробовал SMC. Остался разочарован.
http://smc.sourceforge.net/

Были мысли написать свой DSL для автоматов с питоно-подобным синтаксисом. Но пока мне лень.

А у divmod есть где-то дока на пакет Epsilon или Use the source, Luke?


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#6 2007-05-29 02:26:10

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

Re: finite state machine на Питоне

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

В epsilon введение состояний как внутренних классов с их последующей инструментацией мне понравилось. Хорошо разносит логику различных режимов.
IAR видел. Не прижился почему-то. Наверное, я тогда думал несколько по другому.
Для С++ есть statechart (официально включена в boost) и fsm - лежит в boost vault. Обе - вполне изящны.

У divmod традиционно туго с документацией. Но неплохо с тестами, а epsilon весьма невелика. Мне тестов (а потом и исходников) вполне хватило.

P.S. Питон вполне может заменить DSL - по моему глубокому убеждению.
Примерно как в nevow.tags - еще одном продукте от divmod:
a(href='url')['This is', b['bold'], 'and', i['italic'], 'text']

Отредактированно Андрей Светлов (2007-05-29 02:28:12)


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

Неактивен

 

#7 2007-05-29 03:07:15

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

Андрей Светлов написал:

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

У меня практически все сишные программы строятся на автоматах. Поэтому мне без них вобще обойтись сложно. А питон -- ИМХО -- слишком сложно или некрасиво там автоматы делать руками, поэтому я там не заморачиваюсь.

Андрей Светлов написал:

У divmod традиционно туго с документацией. Но неплохо с тестами, а epsilon весьма невелика. Мне тестов (а потом и исходников) вполне хватило.

Исходники-то я прочел и кажется понял как оно предполагается работать. Просто хотелось уточнить.

Андрей Светлов написал:

P.S. Питон вполне может заменить DSL - по моему глубокому убеждению.
Примерно как в nevow.tags - еще одном продукте от divmod:
a(href='url')['This is', b['bold'], 'and', i['italic'], 'text']

Не-а. По моему глубокому убеждению -- не может. Слишком нечитаемо получается, слишком много мусора.
Теже кавычки надо городить, см. ваш же пример.
DSL на то он и domain-specific language, чтобы кратко и изящно описывать некую предметную область.
Я использовал питон как DSL в нескольких проектах -- слишком много ненужных знаков пунктуации надо городить, чтобы соблюсти правильный питон-синтаксис.
Это плохо, если на таком DSL будет писать не питонщик. Это мой реальный опыт.
Тот же scons -- все вроде хорошо, кроме изврата с записью списка файлов.
Так что не согласен я с вами, но спорить долго и нудно не буду.


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#8 2007-05-29 03:11:59

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

вот кстати тот рецепт из поваренной книги, который я упоминал:
http://aspn.activestate.com/ASPN/Cookbo … ipe/146262

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

Отредактированно bialix (2007-05-29 03:13:05)


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#9 2007-05-29 11:45:50

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

Re: finite state machine на Питоне

По поводу DSL спорить точно бессмысленно. Это почти как религия, и каждый подход имеет свои достоинства и недостатки.
Посмотрел WhatOS и aspn coockbook.
WhatOS - интересно, но С специфика сильно проявляется. aspn - простенько до неудобства. У меня каждое состояние - довольно большая вещь, скорее не атом, а режим работы программы. Так удобнее. Иначе состояний появляется бесчетное множество и прописывать переходы между ними становится затруднительно.
Немного докрутил (были проблемы с  наследованием состояний), и доволен. Состояния можно разносить по отдельным модулям - удобно.
По сути наследник mode рассматривается как специфическая запись контейнера именованных функций, не более того. И экземпляр его не создается.
Занятная вещь получилась


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

Неактивен

 

#10 2007-05-29 18:10:52

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

Re: finite state machine на Питоне

Да, кстати, глупый вопрос.
Как связаться с ребятами из divmod.org?
То, что я доделал к их epsilon.modal у них же помечено как todo: fix this bug.
В процессе дальнейшей работы мы скорее всего еще несколько расширим функциональность (нам важны конечные автоматы, а у них почти-почти то).
Я не прочь отправить им патч к модулю и тесту - авось включат.
Кстати, их тест весь модуль не покрывал - была нестыковочка.
Вот только на их trac guest новый тикет создать не может. А почтового адреса, чтобы послать письмо, я так и не нашел.
Что делать?

Написал, и самому смешно.


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

Неактивен

 

#11 2007-05-29 20:13:37

j2a
Гуру
Откуда: Омск
Зарегистрирован: 2006-06-29
Сообщений: 369
Рейтинг :   26 
Профиль  Вебсайт

Re: finite state machine на Питоне

Андрей Светлов написал:

Как связаться с ребятами из divmod.org?
То, что я доделал к их epsilon.modal у них же помечено как todo: fix this bug.
В процессе дальнейшей работы мы скорее всего еще несколько расширим функциональность (нам важны конечные автоматы, а у них почти-почти то).
Я не прочь отправить им патч к модулю и тесту - авось включат.
Кстати, их тест весь модуль не покрывал - была нестыковочка.
Вот только на их trac guest новый тикет создать не может. А почтового адреса, чтобы послать письмо, я так и не нашел.
Что делать?

Хм. С полгода назад я регистрировался на их trac и открывал тикеты.

Если хочешь написать разработчикам - пиши Жан-Полю Кальдерону (exarkun at twistedmatrix.com), но он весьма... эээ... своеобразный человек, так что лучше открывай тикет, аттач патч и юнит-тест, ставь приоритет тикета highest, в ключевых словах указывай review.

P.S. Это ничего, что все ссылки на Twisted Matrix; в Divmod работают ровно те же люди, так что и email, и dev process у них одинаковы.

P.P.S. Ну или в IRC

Отредактированно j2a (2007-05-29 20:14:50)


Be easy, stay cool

Неактивен

 

#12 2007-05-30 00:57:08

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

Андрей Светлов написал:

aspn - простенько до неудобства. У меня каждое состояние - довольно большая вещь, скорее не атом, а режим работы программы. Так удобнее. Иначе состояний появляется бесчетное множество и прописывать переходы между ними становится затруднительно.

То, что aspn пример прост до безобразия -- я согласен и сразу говорил. Более того, он немного заточен под задачи парсинга.

Однако, не вижу противоречий между простым механизмом, обеспечивающим переходы и большими состояниями. Может я конечно что-то не понимаю, но поскольку у вас уже все работает -- то это ХОРОШО.
Спасибо вам, узнал новые готовые имплементации КА для питона. :-)


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#13 2007-05-31 07:04:33

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

Вот еще пара моментов, относящихся к автоматам.

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

2) Почему-то почти всегда подразумевается, что вся программа -- это один автомат, либо это совокупность параллельно работающих разных автоматов. И никогда не рассматривается случай (по крайней мере мне не попадалось) в явном виде: группа однотипных автоматов, работающих параллельно. Например, у меня игра с несколькими игроками. Есть автомат, отвечающий за логику игры, и группа автоматов, отвечающих за состояние игроков. В упоминавшемся IAR Visual State я не нашел способа создать массив однотипных автоматов. Это главная причина, почему я его не использую. А вообще, как с этим жить в других либах (например, в epsilon.modal)? Что вобще диктует на эту тему ваш здравый смысл?


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#14 2007-05-31 15:59:33

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

Re: finite state machine на Питоне

Алексанр, можно на "ты"? Мне так удобней.

epsilon.modal - всего лишь класс, описывающий автомат. Наследуйся от него и делай свои автоматы. Размножай их, вкладывай друг в друга - все можно. В терминах игры это будет: автомат логики игры, по автомату на игрока, по автомату на компьютерного персонажа (NPC) и т.д. (автоматы на персонажа так и стремятся к вложенности). Это обычные экземпляры классов с мутирующим поведением. Не за счет if/switch, а за счет изменения интерфейса.
Данные общие для всего экземпляра, а методы переключаются на лету при смене состояния. При этом, как ты заметил, есть __enter__, __exit__. И, что немаловажно для меня, набор методов тоже мутирует в зависимости от состояния. Имена этих методов - входные сигналы. При этом к каждому цепляется список параметров (для каждого метода разный). А если из состояния нет нужного перехода - нет и нужного метода. Хорошая трансляция из UML в код.

IAR рассчитан на embedded programming. Когда я писал под Atmel ATMega контроллеры (три года занимался) - постоянно делал простые конечные автоматы. Прописывал все руками, и совмещал несколько в параллельной работе (несколько таймеров, АЦП и входы, изменение сигнала на которых позволяло возбуждать прерывание сильно помогали). Но только при специфицеском кодировании. Выход из узких микропроцессорных рамок позволил применять подход гораздо шире.

Помимо gamedev автоматы очень полезны в internet клиентах . Сеть - ненадежная штука, сообщения приходят негарантированно (возможны отказы) и с непостоянной задержкой. А если ты при этом работаешь с несколькими серверыми (лицензий, биллинга, игровым)?
Без автоматов очень трудно.

Если нужно, готов выложить примеры


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

Неактивен

 

#15 2007-05-31 16:08:54

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

Андрей Светлов написал:

Алексанр, можно на "ты"? Мне так удобней.

Да, конечно.

Андрей Светлов написал:

epsilon.modal - всего лишь класс, описывающий автомат. Наследуйся от него и делай свои автоматы. Размножай их, вкладывай друг в друга - все можно. В терминах игры это будет: автомат логики игры, по автомату на игрока, по автомату на компьютерного персонажа (NPC) и т.д. (автоматы на персонажа так и стремятся к вложенности). Это обычные экземпляры классов с мутирующим поведением. Не за счет if/switch, а за счет изменения интерфейса.

Я как раз думал примерно в таком направлении.

Андрей Светлов написал:

Если нужно, готов выложить примеры

Может быть удастся немного пообщаться на семинаре (после)завтра.


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#16 2007-05-31 17:25:00

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

Re: finite state machine на Питоне

Буду рад. На прошлом так на тебя насели по вопросам о Bazaar, что было не подступиться


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

Неактивен

 

#17 2007-06-01 11:30:16

bialix
Команда
Откуда: Запорожье
Зарегистрирован: 2006-07-13
Сообщений: 409
Рейтинг :   14 
Профиль  Вебсайт

Re: finite state machine на Питоне

Андрей Светлов написал:

... Это обычные экземпляры классов с мутирующим поведением. Не за счет if/switch, а за счет изменения интерфейса.
Данные общие для всего экземпляра, а методы переключаются на лету при смене состояния. При этом, как ты заметил, есть __enter__, __exit__. И, что немаловажно для меня, набор методов тоже мутирует в зависимости от состояния. Имена этих методов - входные сигналы. При этом к каждому цепляется список параметров (для каждого метода разный). А если из состояния нет нужного перехода - нет и нужного метода. Хорошая трансляция из UML в код.

Перечитал еще раз внимательно. Все правильно. Вот эта фраза ключевая собственно:

Данные общие для всего экземпляра, а методы переключаются на лету при смене состояния

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

Есть еще несколько вопросов, хотелось бы обсудить.
/me Попробую сформулировать в следующем ответе.


--
В мире достаточно света для тех, кто хочет видеть, и достаточно мрака для тех, кто не хочет. (Блез Паскаль)

Неактивен

 

#18 2007-06-02 16:16:38

Андрей Светлов
Команда
Откуда: Киев
Зарегистрирован: 2007-05-15
Сообщений: 256
Рейтинг :   20 
Профиль

Re: finite state machine на Питоне

Да, ты хорошо уловил суть. И структура с указателями на функции - хорошее решение для С. В питоне это создается автоматически при генерации класса.
Если опишешь DSL, то написать генератор, кажется, не сложно и не долго.


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

Неактивен

 
  • > Python
  • finite state machine на Питоне [RSS Feed]

Board footer

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson

Linux coutner