Актуальность
Конечные автоматы (finite state machines, fsm) штука полезная. Особенно они могут быть востребованы в средах, где в принципе нет развитой многозадачности (например, в Octave, который является в значительной степени бесплатным аналогом Matlab) или в программах для микроконтроллеров, где не используется по каким-то причинам RTOS. До недавнего времени у меня не получалось лаконично описать конечный автомат, хотя и очень хотелось это сделать. Лаконично, т.е. без воды, без создания лишних классов, структур данных, и т.д. Сейчас это, кажется, получилось и я спешу поделиться своей находкой. Возможно, я изобрёл велосипед, но возможно также, что кому-нибудь такой велосипед окажется полезен.
Начальные сведения
Конечный автомат задаётся:
- набором состояний
- набором событий
- таблицей переходов (т.е. в каком состоянии по какому событию что делается и в какое новое состояние осуществляется переход)
Цель, которая стояла передо мной
Есть императивный язык, я буду рассматривать Octave, но это может быть и Matlab и C, например. Этот язык поддерживает:
- функции
- указатели на функции
- то, что обычно поддерживают императивные языки (циклы, условные операторы и т.д.)
Хочется, чтоб базовые понятия языка (функции, структуры данных, массивы или что-то ещё) каким-то элегантным образом соответствовали тому, что нужно при реализации FSM. Профит в том, что
- код будет самодокументированным
- Doxygen или другие утилиты для анализа кода и генерации документации по коду будут давать дополнительную пользу
Описание идеи
- Поведение внутри состояния должно описываться функцией. Поэтому функция хороший кандидат для того, чтоб её имя соответствовало состоянию.
- Событие должно детектироваться тоже функцией, поэтому и для названий событий тоже можно использовать функции
- Таблицу переходов можно задавать в либо в виде структуры данных, либо в виде switch/case-выражений внутри состояний
В чём проблема задания таблицы переходов в виде структуры данных?
- Таблица может быть достаточно большой и сложной. В этом случае структура данных перестанет влезать в экран и поддержка такой таблицы будет не такой уж и удобной.
- Структура данных требует какого-то объекта в памяти. Это дополнительное неудобство.
- Структура данных требует специального её конструирования (скорее всего пошагового) это делает структуру программы более красивой, но анализировать такую машину состояний потом будет не так-то удобно.
Поэтому здесь я буду использовать switch/case инструкцию.
Единственной структурой данных будет переменная, где будет храниться состояние автомата.
Сами состояния будут идентифицироваться хэндлерами функций (function handlers), которые будут обрабатывать поведение машины в этом состоянии. Например:
function [new_state data] = state_idle(data) if data.block_index == 10 new_state = @state_stop; else % do something data.block_index = data.block_index + 1; printf('block_index = %d\n', data.block_index); endendfunction [new_state data] = state_stop(data) % set break flag data.stop= 1;endfsm_state = @state_idle;data = struct();data.block_index = 0;data.stop = 0;while (1) [fsm_state data] = fsm_state(data) if data.stop break; endend
В этом коде вся идея, собственно, и описана. В Си, вместо хэндлера функции будет указатель на функцию, всё остальное останется так же.
Пример из жизни :)
В качестве примера я реализовал на Octave игру Life, Джона Конвея. Если сконфигурировать её в режиме 100 х 100, то она будет симулировать работу 10 000 конечных автоматов и при этом работает она достаточно эффективно. В простейшем варианте (без событий), код для игры выглядит следующим образом:
function [new_state] = state_alive(neighbours) alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours))); alive_count -= 1; if (alive_count == 2) || (alive_count == 3) new_state = @state_alive; else new_state = @state_dead; endendfunction [new_state] = state_dead(neighbours) alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours))); if (alive_count == 3) new_state = @state_alive; else new_state = @state_dead; endend% main scriptaddpath('fsm_life')debug_on_error(1)size_x = 30;size_y = 30;init_alive_percentage = 30;% initialization selection:%init = 'random';%init = 'cycle';init = 'glider';field = cell(size_y, size_x);[field{:}] = deal(@state_dead);switch (init)case 'random' init_alive_count = round((size_x * size_y) * init_alive_percentage / 100); for n=(1:init_alive_count) x = floor((size_x-0.0000001)*rand())+1; y = floor((size_y-0.0000001)*rand())+1; field{y,x} = @state_alive; endcase 'cycle' field{2,1} = @state_alive; field{2,2} = @state_alive; field{2,3} = @state_alive;case 'glider' field{1,3} = @state_alive; field{2,3} = @state_alive; field{3,3} = @state_alive; field{3,2} = @state_alive; field{2,1} = @state_alive;endprintf("Initial distribution:\n");cellfun(@(x)x == @state_alive, field)% simulationfor step = (1:100) field_new = cell(size(field)); for x=(1:size_x) for y=(1:size_y) x_min = max(x-1, 1); x_max = min(x+1, size_x); y_min = max(y-1, 1); y_max = min(y+1, size_y); neighbours = field(y_min:y_max, x_min:x_max); field_new{y,x} = field{y,x}(neighbours); end end field = field_new; printf('Distribution after step %d\n', step ); cellfun(@(x)x == @state_alive, field) figure(1); imagesc(cellfun(@(x)x == @state_alive, field)); pause(0.05);end
Если хочется больше самодокументируемости и явного определения событий, тогда к двум функциям, отвечающим за состояния, добавится ещё 3 функции, отвечающие за события:
function event = event_die(neighbours) alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours))); alive_count -= 1; if (alive_count == 2) || (alive_count == 3) event = ''; else event = 'die'; endendfunction event = event_spawn(neighbours) alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours))); if (alive_count == 3) event = 'spawn'; else event = ''; endendfunction event = event_survive(neighbours) alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours))); alive_count -= 1; if (alive_count == 2) || (alive_count == 3) event = 'survive'; else event = ''; endendfunction [new_state] = state_alive(neighbours) event = ''; event = [event, event_die(neighbours)]; event = [event, event_survive(neighbours)]; switch event case 'die' new_state = @state_dead; case 'survive' new_state = @state_alive; otherwise msg = sprintf('Unknown event: %s\n', event); error(msg); endendfunction [new_state] = state_dead(neighbours) event = event_spawn(neighbours); switch event case 'spawn' new_state = @state_alive; case '' new_state = @state_dead; otherwise msg = sprintf('Unknown event: %s\n', event); error(msg); endend
Основной скрипт в этом случае останется тем же самым.
