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

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
16-Июн-2021 20:32

Цитировать

Актуальность
Конечные автоматы (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

Основной скрипт в этом случае останется тем же самым.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_c, #_programmirovanie_mikrokontrollerov (Программирование микроконтроллеров), #_matlab, #_matlab, #_octave, #_c, #_fsm, #_automata, #_c, #_programmirovanie_mikrokontrollerov (
Программирование микроконтроллеров
), #_matlab

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 07:10
Часовой пояс: UTC + 5