Relevance
Finite state machines (fsm) are useful. They can be especially demanded in environments where, in principle, there is no developed multitasking (for example, in Octave, which is largely a free analogue of Matlab) or in programs for microcontrollers where RTOS is not used for some reason. Until recently, I was unable to succinctly describe the state machine, although I really wanted to do it. Laconic, i.e. without water, without creating unnecessary classes, data structures, etc. Now it seems to have worked out and I am in a hurry to share my find. I may have invented the bicycle, but it is also possible that someone will find such a bicycle useful.
Initial information
The state machine is given by:
- set of states
- set of events
- a transition table (i.e. in which state for which event what is being done and in which new state the transition is made)
The goal that stood before me
There is an imperative language, I will consider Octave, but it can be Matlab and C, for example. This language supports:
- functions
- function pointers
- what imperative languages usually support (loops, conditional statements, etc.)
I would like the basic concepts of the language (functions, data structures, arrays, or something else) to somehow elegantly correspond to what is needed when implementing an FSM. The profit is that:
- the code will be self-documenting
- Doxygen or other utilities for analyzing code and generating code documentation will provide additional benefits.
Description of the idea
- The behavior within the state must be described by a function. Therefore, a function is a good candidate for a name to match a state.
- The event must also be detected by a function, therefore, for event names, you can also use the functions
- The transition table can be specified either as a data structure or as switch / case expressions within states
What is the problem with defining the jump table as a data structure?
- The table can be quite large and complex. In this case, the data structure will cease to fit into the screen and the support of such a table will not be so convenient.
- The data structure requires some kind of object in memory. This is an additional inconvenience.
- The data structure requires its special construction (most likely step-by-step) - this makes the program structure more beautiful, but it will not be so convenient to analyze such a state machine later.
Therefore, here I will use a switch / case statement.
The only data structure will be a variable where the state of the machine will be stored.
The states themselves will be identified by the function handlers that will handle the behavior of the machine in that state. For example:
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
In this code, the whole idea, in fact, is described. In C, instead of a function handler, there will be a function pointer, everything else remains the same.
Real life example
As an example, I implemented the Life game by John Conway on Octave . If you configure it in 100 x 100 mode, then it will simulate the work of 10,000 state machines and at the same time it works quite efficiently. In its simplest form (no events), the code for the game looks like this:
% '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
If you want more self-documenting and an explicit definition of events, then 3 more functions responsible for events will be added to the two functions responsible for states:
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
The main script in this case will remain the same.
Here is an example of how the glider crawls from the upper left corner to the lower right: I
posted the sources on the github: https://github.com/tminnigaliev/octave_life
Upd .: Despite the fact that I stated that this idea can also be implemented by means C language, the implementation may not be so simple. If implemented in C, then the state will be represented by the data type T, which will be a pointer to a function that takes an array (or a pointer to an array) of elements of type T and returns a type T. This is easier to state than to write. Nevertheless, I will try to implement something like this later and write another article where I will describe the C implementation.