Relevansi
Mesin negara hingga (fsm) berguna. Mereka dapat diminta secara khusus di lingkungan di mana, pada prinsipnya, tidak ada multitasking yang dikembangkan (misalnya, dalam Oktaf, yang sebagian besar merupakan analog gratis Matlab) atau dalam program untuk mikrokontroler di mana RTOS tidak digunakan karena alasan tertentu. Sampai saat ini, saya tidak dapat menggambarkan mesin negara secara ringkas, meskipun saya benar-benar ingin melakukannya. Singkat, yaitu tanpa air, tanpa membuat kelas yang tidak perlu, struktur data, dll. Sekarang tampaknya berhasil dan saya sedang terburu-buru untuk membagikan temuan saya. Saya mungkin telah menemukan sepeda, tetapi mungkin juga seseorang akan menganggap sepeda seperti itu berguna.
Informasi awal
Mesin negara ditentukan:
- himpunan negara bagian
- rangkaian acara
- tabel transisi (yaitu di mana keadaan untuk peristiwa apa yang sedang dilakukan dan di mana keadaan baru transisi dibuat)
Tujuan yang berdiri di depanku
Ada bahasa imperatif, saya akan mempertimbangkan Oktaf, tetapi bisa Matlab dan C, misalnya. Bahasa ini mendukung:
- fungsi
- penunjuk fungsi
- bahasa imperatif apa yang biasanya didukung (loop, pernyataan bersyarat, dll.)
Saya ingin konsep dasar bahasa (fungsi, struktur data, array, atau yang lainnya) entah bagaimana secara elegan sesuai dengan apa yang dibutuhkan saat mengimplementasikan FSM. Keuntungannya adalah:
- kode akan mendokumentasikan diri sendiri
- Doxygen atau utilitas lain untuk menganalisis kode dan menghasilkan dokumentasi kode akan memberikan manfaat tambahan.
Deskripsi ide
- Perilaku dalam keadaan harus dijelaskan oleh suatu fungsi. Oleh karena itu, suatu fungsi adalah kandidat yang baik untuk nama yang cocok dengan keadaan.
- Acara juga harus dideteksi oleh fungsi, oleh karena itu, untuk nama acara, Anda juga dapat menggunakan fungsi
- Tabel transisi dapat ditentukan baik dalam bentuk struktur data atau dalam bentuk ekspresi switch / case dalam keadaan
Apa masalahnya dengan mendefinisikan tabel lompatan sebagai struktur data?
- Tabelnya bisa sangat besar dan rumit. Dalam hal ini, struktur data akan berhenti masuk ke layar dan dukungan tabel seperti itu tidak akan begitu nyaman.
- Struktur data membutuhkan beberapa jenis objek dalam memori. Ini adalah ketidaknyamanan tambahan.
- Struktur data memerlukan konstruksi khusus (kemungkinan besar langkah demi langkah) - ini membuat struktur program lebih indah, tetapi tidak akan begitu nyaman untuk menganalisis mesin keadaan seperti itu nanti.
Oleh karena itu, disini saya akan menggunakan pernyataan switch/case.
Satu-satunya struktur data akan menjadi variabel di mana keadaan mesin akan disimpan.
Status itu sendiri akan diidentifikasi oleh penangan fungsi yang akan menangani perilaku mesin dalam status itu. Sebagai contoh:
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
Dalam kode ini, seluruh ide, sebenarnya, dijelaskan. Di C, alih-alih pengendali fungsi, akan ada penunjuk fungsi, yang lainnya tetap sama.
Contoh kehidupan nyata
Sebagai contoh, saya mengimplementasikan game Life oleh John Conway di Octave . Jika Anda mengonfigurasinya dalam mode 100 x 100, maka itu akan mensimulasikan pekerjaan 10.000 mesin negara dan pada saat yang sama bekerja dengan cukup efisien. Dalam bentuknya yang paling sederhana (tidak ada acara), kode untuk permainan terlihat seperti ini:
% '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
Jika Anda ingin lebih banyak mendokumentasikan diri dan definisi acara yang eksplisit, maka 3 fungsi lainnya yang bertanggung jawab untuk acara akan ditambahkan ke dua fungsi yang bertanggung jawab atas status:
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
Skrip utama dalam hal ini akan tetap sama.
Berikut adalah contoh bagaimana glider merangkak dari sudut kiri atas ke kanan bawah: Saya
memposting sumber di github: https://github.com/tminnigaliev/octave_life
Upd .: Terlepas dari kenyataan bahwa saya menyatakan bahwa ini ide juga dapat diimplementasikan dengan menggunakan bahasa C, implementasinya mungkin tidak sesederhana itu. Jika diimplementasikan dalam C, maka state akan diwakili oleh tipe data T, yang akan menjadi pointer ke fungsi yang mengambil array (atau pointer ke array) elemen tipe T dan mengembalikan tipe T. Ini adalah lebih mudah untuk menyatakan daripada menulis. Namun demikian, saya akan mencoba menerapkan sesuatu seperti ini nanti dan menulis artikel lain di mana saya akan menjelaskan implementasi C.