Relevancia
Las máquinas de estados finitos (fsm) son útiles. Pueden ser especialmente demandados en entornos donde, en principio, no hay multitarea desarrollada (por ejemplo, en Octave, que es en gran parte un análogo libre de Matlab) o en programas para microcontroladores donde RTOS no se usa por alguna razón. Hasta hace poco, no podía describir sucintamente la máquina de estados, aunque tenía muchas ganas de hacerlo. Lacónico, es decir sin agua, sin crear clases, estructuras de datos innecesarias, etc. Ahora parece haber funcionado y tengo prisa por compartir mi hallazgo. Puede que yo haya inventado la bicicleta, pero también es posible que alguien encuentre útil una bicicleta así.
Información inicial
La máquina de estado se especifica:
- conjunto de estados
- conjunto de eventos
- una tabla de transición (es decir, en qué estado para qué evento qué se está haciendo y en qué nuevo estado se realiza la transición)
La meta que estaba frente a mí
Hay un lenguaje imperativo, consideraré Octave, pero puede ser Matlab y C, por ejemplo. Este idioma admite:
- funciones
- punteros de función
- qué lenguajes imperativos suelen admitir (bucles, declaraciones condicionales, etc.)
Me gustaría que los conceptos básicos del lenguaje (funciones, estructuras de datos, matrices o algo más) se correspondan de alguna manera con elegancia con lo que se necesita al implementar un FSM. El beneficio es que:
- el código se autodocumentará
- Doxygen u otras utilidades para analizar código y generar documentación de código proporcionarán beneficios adicionales.
Descripción de la idea
- El comportamiento dentro del estado debe ser descrito por una función. Por lo tanto, una función es un buen candidato para que un nombre coincida con un estado.
- El evento también debe ser detectado por la función, por lo tanto, para los nombres de eventos, también puede usar las funciones
- La tabla de transición se puede especificar en forma de estructura de datos o en forma de expresiones de cambio / caso dentro de los estados
¿Cuál es el problema de definir la tabla de salto como una estructura de datos?
- La mesa puede ser bastante grande y compleja. En este caso, la estructura de datos dejará de encajar en la pantalla y el soporte de dicha tabla no será tan conveniente.
- La estructura de datos requiere algún tipo de objeto en la memoria. Este es un inconveniente adicional.
- La estructura de datos requiere su construcción especial (probablemente paso a paso); esto hace que la estructura del programa sea más hermosa, pero no será tan conveniente analizar dicha máquina de estado más adelante.
Por lo tanto, aquí usaré una declaración switch / case.
La única estructura de datos será una variable donde se almacenará el estado de la máquina.
Los estados mismos serán identificados por los manejadores de funciones que manejarán el comportamiento de la máquina en ese estado. Por ejemplo:
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
En este código, de hecho, se describe la idea completa. En C, en lugar de un controlador de función, habrá un puntero de función, todo lo demás permanece igual.
Ejemplo de la vida real
Como ejemplo, implementé el juego Life de John Conway en Octave . Si lo configura en modo 100 x 100, simulará el trabajo de 10,000 máquinas de estado y, al mismo tiempo, funcionará de manera bastante eficiente. En su forma más simple (sin eventos), el código del juego se ve así:
% '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
Si desea más autodocumentación y una definición explícita de eventos, se agregarán 3 funciones más responsables de eventos a las dos funciones responsables de los estados:
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
El guión principal en este caso seguirá siendo el mismo.
Aquí hay un ejemplo de cómo el planeador se arrastra desde la esquina superior izquierda a la inferior derecha:
Publiqué las fuentes en el github: https://github.com/tminnigaliev/octave_life
Upd.: A pesar de que dije que esto La idea también se puede implementar por medio del lenguaje C, la implementación puede no ser tan simple. Si se implementa en C, entonces el estado estará representado por el tipo de datos T, que será un puntero a una función que toma una matriz (o un puntero a una matriz) de elementos de tipo T y devuelve un tipo T. Esto es más fácil de expresar que de escribir. Sin embargo, intentaré implementar algo como esto más adelante y escribiré otro artículo donde describiré la implementación de C.