Лаконичная реализация конечных автоматов в 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

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