Automata

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

Конечные автоматы (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

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