Лаконичная реализация конечных автоматов в Matlab, Octave, C

Актуальность

Конечные автоматы (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);     end end  function [new_state data] = state_stop(data)     % set break flag     data.stop= 1; end fsm_state = @state_idle; data = struct(); data.block_index = 0; data.stop = 0;  while (1)     [fsm_state data] = fsm_state(data)     if data.stop         break;     end end 

В этом коде вся идея, собственно, и описана. В Си, вместо хэндлера функции будет указатель на функцию, всё остальное останется так же.

Пример из жизни 🙂

В качестве примера я реализовал на 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;     end end  function [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;     end end  % main script  addpath('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;     end case '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; end  printf("Initial distribution:\n"); cellfun(@(x)x == @state_alive, field)  % simulation for 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';     end end  function event = event_spawn(neighbours)     alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours)));     if (alive_count == 3)         event = 'spawn';     else         event = '';     end end  function 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 = '';     end end  function [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);     end end  function [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);     end end 

Основной скрипт в этом случае останется тем же самым.