Лаконичная реализация конечных автоматов в 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 конечных автоматов и при этом работает она достаточно эффективно. В простейшем варианте (без событий), код для игры выглядит следующим образом:

% функция описывает состояние 'alive', результирующее состояние зависит
% от состояний соседних клеток
% предполагается, что функция хранится в файле ./fsm_life/state_alive.m
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

% функция описывает состояние 'dead', результирующее состояние зависит
% от состояний соседних клеток
% предполагается, что функция хранится в файле ./fsm_life/state_dead.m
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


% главный скрипт.
% предполагается, что он хранится в файле ./life.m
addpath('fsm_life');   % добавляем путь к директории с нашим автоматом
debug_on_error(1);   % если будет какая-то ошибка - остановим выполнение и проанализируем её

% размеры поля 30 х 30
size_x = 30;
size_y = 30;

% если будет выбрано случайное заполнение, тогда живыми будут 30% всех клеток
init_alive_percentage = 30;

% выбор эксперимента (случайное заполнение/цикл/глайдер).
% initialization selection:
%init = 'random';
%init = 'cycle';
init = 'glider';

% наше поле - это cell-array, потому что function handlers нельзя хранить в
% обычном массиве в Октаве
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));

    % пауза нужна чтоб можно было остановить симуляцию по Ctrl+C
    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

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

Вот пример того, как глайдер ползёт из левого верхнего угла в правый нижний:


Исходники выложил на гитхаб: https://github.com/tminnigaliev/octave_life

Upd.1: Несмотря на то, что я заявил, что эта идея также может быть реализована средствами языка Си, реализация может оказаться не такой уж и простой. Если реализовывать на Си, то состояние будет представляться типом данных Т, который будет являться указателем на функцию, принимающую массив (или указатель на массив) элементов типа Т и возвращающую тип Т. Это проще заявить, чем написать. Тем не менее, я попробую что-нибудь такое реализовать позже и напишу другую статью, где опишу Си-шную реализацию.

Upd.2: Несмотря на то, что, что я обещал написать другую статью, где обещал описать Си-шную реализацию, я понял, что делать это нет большого смысла. Си знают многие, вряд ли я там что-то новое расскажу, поэтому я решил ограничиться ссылкой на online-gdb с Си-шной реализацией: https://onlinegdb.com/jsND-_7L4

Upd.3: Читателю, наверно, интересно не только читать текст, но и может быть интересно посмотреть результаты симуляции. Не у всех есть Octave, а тем более Matlab, поэтому я выложил этот проект в octave-online