Pull to refresh
  • by relevance
  • by date
  • by rating

Implementing FSM

Website development *
В статье рассказывается о разработанной автором миниатюрной Java библиотеке, позволяющей коротко и наглядно определять конечные автоматы. Библиотека, назовем ее AkerFSM, доступна в Google Code.
В первой части статьи сформулированы предпосылки и требования к библиотеке. Во второй части приводится абстрактный пример использования библиотеки. В третьей части рассмотрены важные моменты устройства самой библиотеки. Четвертая часть посвящена рассмотрению упрощенного примера из реальной жизни, в котором с помощью конечного автомата задается поведение одного из контроллеров в GWT-приложении.

Читать дальше →
Total votes 25: ↑21 and ↓4 +17
Views 14K
Comments 31

Язык для работы с ActionScript событиями

Adobe Flash
image

В текущем билде RASE мы зарелизили язык для коллекций. Сейчас трудимся над языком, который точно взорвет мозг флэш-разработчиков. Можно будет создавать специальные методы с аннотацией «Flow», код в котором будет выполняться ассинхронно. То есть код будет «останавливаться» — ждать события (или группы событий) и выполняться дальше, когда событие произойдет.



Также можно прыгать по точкам в коде — state, jump. И можно дождаться выполнения других flow-методов — chain.

В общем полноценный язык для работы Finite State Machine.
Total votes 33: ↑29 and ↓4 +25
Views 860
Comments 9

Шаблоны проектирования в автоматном программировании

Programming *

Из теории алгоритмов и автоматов известно понятие конечного автомата, которое описывает поведение некоторой абстрактной модели в терминах конечного набора состояний и событий, инициализирующих переходы между этими состояниями. На основании этой теории была развита достаточно распространенная сейчас парадигма автоматного программирования, при использовании которой задача решается в терминах конечных автоматов — т.е. в терминах состояний и событий. В явном виде, данная парадигма широко применяется в языках программирования, при построении лексеров. Однако, можно найти огромное количество примеров программных систем, в некотором смысле реализованных на основе данной парадигмы.

В статье рассматриваются особенности применения шаблонов Visitor/Double Dispatch и State при реализации системы на основе конечного автомата. Кроме того, статью можно рассматривать как продолжение цикла публикаций о шаблонах проектирования на Хабрахабре.

Читать дальше →
Total votes 31: ↑26 and ↓5 +21
Views 16K
Comments 12

Практическая биоинформатика ч. 2

Biotechnologies
    Эта статья расскажет о том, как обработать данные, полученные после pipeline, выходом которого будет sam/bam файл[1], создать несложный bed graph файл (http://genome.ucsc.edu/FAQ/FAQformat.html) и просмотреть его с помощью UCSC genome browser[2]. Очень сложно решиться, на чем писать программы, ибо уже есть огромное количество чужих наработок и совсем не хочется сочинять колесо там, где этот этап уже пройден. Долго мучаясь, я решил остановиться на C++, хотя Python и R рассматривались на равных. Также сохранилась идея, что может понадобиться графика, да ещё и под Linux, поэтому к С++ прибавилось Qt. Надеюсь, в этой статье я расскажу достаточно подробно о всем выше перечисленном, чтобы ответить на вопрос, заданный мне в начале пути и озвученный в первой части повествования.
Читать дальше →
Total votes 45: ↑40 and ↓5 +35
Views 2.6K
Comments 20

Асинхронный конечный автомат: идеология и технология

Designing and refactoring *Algorithms *
Sandbox

Вступление


Хорошо, когда твои подчиненные никогда не болеют, не умирают, всегда присутствуют на работе и выполняют твои распоряжения без предварительных приготовлений: «Вызвали — встань». Таковы, например, веб-сервисы, соблюдающие модель REST (которая, если отбросить специальную HTTP-терминологию, сводится к тому, что интерфейс сервиса фактически является интерфейсом контейнера данных).

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

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

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

Анатомия (объектная декомпозиция)


Модель конечного автомата включает следующие базовые сущности:
  1. Состояние — это режим функционирования управляемой системы, отличный от других по предоставляемым возможностям. Таким образом, снапшоты кешей и буферов, варианты циклов «от забора и до обеда» и другие акциденции управляемой системы в понятие «состояния» не входят. В норме состояний должны быть считанные единицы; если счет пошел на второй десяток — скорее всего, управляемую систему следует раздробить или иерархизировать.
  2. Условие — это логическое значение (true или false) на одном из «входов» системы. Суперпозиция состояний всех входов автомата однозначно определяет целевое состояние автомата. Таким образом, любой входной сигнал, значимый для состояния автомата, в конечном счете сводится к установке значения одного или нескольких условий.
  3. Реакция — это отклик автомата на отличие текущего состояния от целевого. Принципиально различных видов реакции мы насчитали два с половиной: прямой переход между состояниями, маршрут и стоп-маршрут («кирпич»). Прямой переход может быть и пустой операцией (NOP) — например, в случае, если изменение входов вызвано уведомлением о завершении асинхронной операции.
Читать дальше →
Total votes 23: ↑21 and ↓2 +19
Views 12K
Comments 2

Простые стейт-машины на службе у разработчика

Programming *C# *
Представьте на минутку обычного программиста. Допустим, его зовут Вася и ему нужно сделать анимированную менюшку на сайт/десктоп приложение/мобильный апп. Знаете, которые выезжают сверху вниз, как меню у окна Windows или меню с яблочком у OS X. Вот такое.

Начинает он с одного выпадающего окошка, тестирует анимацию, выставляет ease out 100% и наслаждается полученным результатом. Но вскоре он понимает, что для того, чтобы управлять менюшкой, хорошо бы знать закрыто оно сейчас или нет. Мы-то с вами тут программисты опытные, все понимаем, что нужно добавить флаг. Не вопрос, флаг есть.

var opened = false;

Вроде, работает. Но, если быстро кликать по кнопке, меню начинает моргать, открываясь и закрываясь не успев доанимироваться в конечное состояние. Вася добавляет флаг animating. Теперь код у нас такой:

var opened = false;
var animating = false;

function onClick(event) {
  if (animating) return;
  if (opened) close();
  else open();
}

Через какое-то время Васе говорят, что меню может быть полностью выключено и неактивно. Не вопрос! Мы-то с вами тут программисты опытные, все понимаем, что… нужно добавить ЕЩЕ ОДИН ФЛАГ! И, всего-то через пару дней разработки, код меню уже пестрит двустрочными IF-ами типа вот такого:

if (enabled && opened && !animating && !selected && finishedTransition && !endOfTheWorld && ...) { ... }

Вася начинает задаваться вопросами: как вообще может быть, что animating == true и enabled == false; почему у него время от времени все глючит; как тут вообще поймешь в каком состоянии находится меню. Ага! Состояния... О них дальше и пойдет речь.

Знакомьтесь, это Вася.


Читать дальше →
Total votes 114: ↑92 and ↓22 +70
Views 153K
Comments 96

Простой конечный автомат на Unity

Game development *C# *Unity3D *
Translation
При разработке нам понадобился простой конечный автомат, желательно уже реализованный. Из списка реализаций, который предложил гугл, выбрали этот, за простоту и компактность. Используем у себя, в целом FSM неплох. Далее под катом перевод оригинальной статьи автора из Греции Tasos Giannakopoulos. Я не переводчик, поэтому я старался передать смысл, иногда объясняя суть своими словами, за что извиняюсь перед перфекционистами.
Читать дальше →
Total votes 27: ↑19 and ↓8 +11
Views 45K
Comments 3

Убить всех человеков с помощью кота, или конечные автоматы на Akka.FSM

Programming *Scala *
Tutorial
Как я уже писал в своей первой статье, не так давно я перешел c С++ на Scala. И вместе с этим я начал изучать модель акторов в исполнении Akka. Наиболее яркое впечатление на меня произвела лекгость реализации и тестирования конечных автоматов (finite-state machines, FSM), которую предоставляет эта библиотека. Уж не знаю, почему именно так получилось, учитывая изобилие остальных прекрасных и полезных вещей в Akka. Но теперь в моем первом проекте на Scala я использую конечные автоматы при каждой выпадающей возможности, подкрепленной целесообразностью (как я искренне надеюсь). И вот я решил, что готов поделиться с сообществом теми знаниями об Akka.FSM, а также некоторыми хитростями и личными наработками, которые я успел накопить. Подобной темы на хабре я не нашел (да и вообще со статьями про Scala и Akka здесь как-то не густо), и решил, не затягивая, исправить положение и выговориться, пока кто-то не сказал всего раньше меня. А чтобы было не скучно — предлагаю вместе реализовать поведение самого настоящего электронного кота. Хотелось бы верить, что какая-то одинокая романтическая душа, вдохновившись моей статьей, доработает предлагаемый в ней функционал до полноценного «Тамакотчи», в качестве домашнего задания. Главное, чтобы такая душа не забыла после поделиться своими результатами с сообществом в комментариях. В идеальном варианте можно было бы создать проект на гитхабе с общим доступом, чтобы каждый желающий смог привнести свой личный вклад в развитие идей трансгуманизма. А теперь — в сторону шутки и фантазии, закатываем рукава. Начинать мы будем с самого нуля, а я для пущего 7D и эффекта присутствия я буду проделывать каждый шаг вместе с вами. TDD прилагается: с неоттестированным робокотом уж точно будет не до шуток.

Информация в статье предназначена для тех, кто уже хотя бы немного заком со Scala, и имеет хотя бы поверхностное представление о модели акторов. Для тех же, кто хотел бы познакомиться, но не знает, с чего начать, в качестве бонуса я написал небольшую стартовую инструкцию и скрыл ее под спойлер, чтоб остальным не мешала. В ней говорится о том, как без лишних усилий создать чистый проект на Scala со всеми нужными библиотеками.
Поехали!
Total votes 28: ↑24 and ↓4 +20
Views 23K
Comments 15

Пишем код для Node.js в стиле «машина состояний»

JavaScript *Node.JS *
Вы пишите сервер на Node.js, который принимает входящие TCP-соединения и ведёт с клиентами нетривиальный диалог по нестандартному протоколу? Возможно вам будет интересен пример, который я развиваю в своих проектах. Что я имею ввиду под нетривиальным диалогом?

Давайте сравним.
Читать дальше →
Total votes 14: ↑9 and ↓5 +4
Views 12K
Comments 29

Сдвиг фазы сигнала на VHDL

FPGA *
Sandbox
Данная статья продолжение серии топиков Элемент задержки на VHDL, Элемент задержки на VHDL. Другой взгляд о элементах задержки на VHDL реализованных в ПЛИС.

Акцент будет сделан на конкретный прикладной пример, который любой желающий может запустить в симуляторе или реальном железе. Пример создан для удобной симуляции в среде Xilinx ISE с использованием Modelsim SE и с минимальными изменениями реализован в полноценное IP Core.
Читать дальше →
Total votes 10: ↑9 and ↓1 +8
Views 7.9K
Comments 5

МКА (машина конечных автоматов) для чайников на примере класса «кнопка» в arduino

C++ *Programming microcontrollers *

Зачем всё это нужно?


Когда чайник, уперевшись в необходимость отойти от простой последовательности действий, задаёт на хабре вопрос типа "как сделать вот это?", ему с вероятностью 70% отвечают "погугли конечные автоматы" и 30% "используй finite state machine" в зависимости от страны работодателя профессионала. На следующий вопрос "а как?" отправляют в гугл. Идёт такой чайник, что только закончил мигать светодиодом и вытер пот со лба, что учил в школе немецкий и всю жизнь работал бульдозеристом в этот гугл и видит там статьи типа Википедия про конечные автоматы с формулами и в которых понятны только предлоги.


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

Читать дальше →
Total votes 18: ↑15 and ↓3 +12
Views 39K
Comments 28

FPGA для программиста, конечные автоматы (verilog)

FPGA *

Стиль описания конечного автомата как образ мышления


Когда нужно преодолеть врожденную параллельность FPGA, и появляется желание заставить схему работать последовательно, по алгоритму, на помощь приходят конечные автоматы, про которые написано не мало академических и практических трудов.

Например, очень популярной является работа: Clifford E. Cummings, The Fundamentals of Efficient Synthesizable Finite State Machine Design using NC-Verilog and BuildGates. Всякий раз, когда специалисты решают обсудить, как правильно писать конечные автоматы, кто-то обязательно достает эту публикацию.

Статья стала настолько авторитетной, что многие даже не стараются анализировать аргументы автора. В частности, бытует мнение, что профессионалы всегда используют двухчастный способ описания конечных автоматов, имеется ввиду, описание конечных автоматов в 2 always блока. Это утверждение продолжает вызывать жаркие споры, и я хочу пояснить различия в описаниях конечного автомата с разным количество always блоков.

В беседах с коллегами я понял, что споры о том, как надо писать конечные автоматы в 1 или 2, 3 always блока, связаны с разным представлением (осознанием) реализуемого алгоритма, разным типом мышления. Попробую показать это на примере.

Я полагаю, что эта статья не первая статья о FSM и Verilog в вашей жизни, поэтому я не буду объяснять ни что такое конечный автомат, ни как он описывается на Verilog, а перейду сразу к делу.
Читать дальше →
Total votes 31: ↑29 and ↓2 +27
Views 18K
Comments 27

Легковесное ядро конечного автомата с автогенератором дерева для embedded проектов

C++ *UML Design *
Tutorial
image

Введение


В моей практике часто возникали ситуации, когда применение конечного автомата являлось наиболее верным решением, однако от него приходилось отказываться ввиду срочности разработки, сложности поддержки, или же по каким-либо иным причинам. В этом посте мне хотелось бы поделиться с вами разработанным мною решением, позволяющим без труда встраивать в свои проекты конечные автоматы с возможностью наглядного отображения структуры дерева.
Читать дальше →
Total votes 7: ↑7 and ↓0 +7
Views 5.3K
Comments 7

Конечный автомат разума

Artificial Intelligence
Хочу поделиться своей теорией разума разложенной по модели конечного автомата. Строго прошу мою доморощенную теорию не критиковать. Конструктивная критика и идеи приветствуются. В связи с нулевой кармой не уверен, что смогу отвечать на комментарии к собственному посту, но это уже лирика.
Читать дальше →
Total votes 9: ↑4 and ↓5 -1
Views 3K
Comments 1

Стейт-машины на службе у MVP. Лекция Яндекса

Яндекс corporate blog Development of mobile applications *Development for Android *Mobile applications testing *
Модель конечного автомата (finite-state machine, FSM) находит применение в написании кода для самых разных платформ, включая Android. Она позволяет сделать код менее громоздким, неплохо укладывается в парадигму Model-View-Presenter (MVP) и поддаётся несложному тестированию. Разработчик Владислав Кузнецов рассказал на Droid Party, как эта модель помогает в развитии приложения Яндекс.Диск.


— Вначале поговорим по теорию. Думаю, каждый из вас слышал и про MVP, и про стейт-машину, но повторим.
Total votes 24: ↑23 and ↓1 +22
Views 14K
Comments 3

Behaviors — конечный автомат без головной боли

JavaScript *
Tutorial
Стандартный подход к описанию последовательности вводов пользователя и реакции на них (например при управлении персонажем в игре) — это конечный автомат (state machine). Он, однако, часто приводит к громоздким программам, понимание которых требует немалых усилий или даже зарисовок на бумаге. В этой статье я предлагаю небольшой сдвиг в описании, который позволяет экономить место на экране и мозговой ресурс.


image

Сдвиг в описании заключается в использовании техники сопрограмм. Для применения этой техники, необходимо представить, какое поведение мы ожидаем от компьютера в итоге. Поэтому я назвал небольшую библиотеку, которую создал под эту задачу — Behaviors.
Читать дальше →
Total votes 16: ↑11 and ↓5 +6
Views 4.2K
Comments 5

Реактивный конечный автомат

JavaScript *Functional Programming *TypeScript *
Sandbox
5 лет назад, после поиска годного решения в RxJs, Beacon, ...etc.js, и остановившись на flyd.js и написал 4-6 проектов используя только три фичи из либы stream, on, combine. Остальное оказалось не у дел, хотелось легкости бандла. Так появился alak, первые версии до 0.3 были всего 20-30 строк и полностью заменили flyd.

Год спустя появилась версия 0.4 уже на 72 строки с паттерн матчингом и mix (аналог combine из flyd или computed из vue). Спустя три года и десятки проектов — появилось ощущение годности делится опытом и релизить 1.0.


Читать дальше →
Total votes 13: ↑12 and ↓1 +11
Views 5.1K
Comments 22

Как мы выбирали себе ServiceDesk. Часть 1

Service Desk *
Sandbox

Введение


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

Стоит сразу отметить, что с момента решения «нам нужно автоматизировать процессы» до момента реализации задуманного у нас ушло 2 месяца. И мы считаем, что мы справились довольно быстро. Большая часть времени ушла на то, чтобы разобраться в работе и функционале предложенных на рынке вариантов. Еще столько же на внедрение выбранного решения в бизнес и окончательный «переезд» на работу в нём. Сэкономим время читателя и расскажем про наш сравнительный анализ рынка систем автоматизации сервисного бизнеса.
Читать дальше →
Total votes 29: ↑26 and ↓3 +23
Views 7.6K
Comments 17

Как мы выбирали себе ServiceDesk. Часть 2

Service Desk *
Продолжаем писать о нашем выборе системы для оцифровки бизнеса. Как все начиналось, читайте здесь

Напомню: мы — сервисная компания, которая решила найти волшебную таблетку для своего бизнеса, благодаря которой «вжух» — и все бизнес-процессы пойдут складно и без перебоев.
Читать дальше →
Total votes 16: ↑12 and ↓4 +8
Views 2.8K
Comments 2

Как мы выбирали себе ServiceDesk. Часть 3

Service Desk *
Наши “хождения по мукам” подходят к концу. Эта статья завершает цикл нашего выбора оптимальной системы для оцифровки бизнеса.

Всем привет! Напомню, что мы — установщики кондиционеров, которые решили найти для себя оптимальный ServiceDesk.

Ранее работали в совместных календарях, мессенджерах и других сервисах, но задолбались. Однажды приняли решение — завести себе Service Desk.
Читать дальше →
Total votes 14: ↑11 and ↓3 +8
Views 8.6K
Comments 7
1