今日は、単純な決定論的有限状態マシンの作成を試みます。 突然Perlで作成したかったのですが、特定のトリックを使用しないため、一般的な概念を他の命令型言語に移行することは難しくありません。
はじめに
理論については詳しく説明しません。これには、GoogleおよびWikipediaという特別な文献があります;）。 ベース自体を検討してください。 ステートマシンとは何かを見てみましょう。
電子機器やプログラミングでは、最も単純なケースでは、いわゆる「スイッチング機能」を扱っています。 これは、独自のメモリを持たない比較的原始的な抽象化です。入力に対して引数があり、出力に対して特定の値があります。 出力値は常に入力のみに依存します。
関数の次の値が前のものに依存する必要がある場合 いくつかの以前のものから？ ここで、私たちはすでに私たち自身の記憶を持つ特定の抽象化に来ています。 これがマシンになります。 マシンの出力値は、マシンの入力値と現在の状態によって異なります。
そのため、ステートマシンは内部状態の数が有限であるため、そのように呼び出されます。 そして、おそらく、最も単純な有限状態マシンは決定論的です。各入力信号に対して、マシンが現在の状態から移行できる状態は1つだけです。
したがって、マシンは以下によって決定されます。
- 初期条件;
- 入力アルファベット（可能な入力信号のセット）;
- 多くの条件;
- および変換表。
実際、機械の本質は最後の段落で決定されます。 遷移表（遷移図としても表示）は、入力信号（シンボル）、現在の状態、次の状態の3つの列で構成されています。 例によってすべてが明らかになります。
基本クラス
そのため、基本クラスを実装します。 初期状態、現在の状態、および遷移表が必要であるとすでに決めています。 入力文字のアルファベットはタスクによって決定されるため、入力を正規化（単純化）する必要もあります。 出力信号は、子孫クラスの実行可能メソッドによって実行されます。 私たちの生活を簡素化するために、アルファベットに人為的に記号「*」を追加します-その他の記号。
package FSM; use strict; use Carp; use vars qw($AUTOLOAD); # Create new object sub new { my $self = {}; my ($proto, $initial) = @_; my $class = ref($proto) || $proto; # Init ourselves $self->{INITIAL} = $initial; $self->{CURRENT} = $initial; $self->{STATES} = {}; bless ($self, $class); return $self; } sub setInitialState { my ($self, $initial) = @_; $self->{INITIAL} = $initial; return $self; } sub setCurrentState { my ($self, $current) = @_; $self->{CURRENT} = $current; return $self; } sub getCurrentState { my ($self, $current) = @_; return $self->{CURRENT}; } sub reset { my $self = shift; $self->{CURRENT} = $self->{INITIAL}; return $self; } sub addState { my $self = shift; my %args = @_; $self->{STATES}->{$args{STATE}}->{$args{SYMBOL}} = {NEXT => $args{NEXT}, ACTION => $args{ACTION}}; return $self; } sub removeState { my $self = shift; my %args = @_; if (exists $args{SYMBOL}) { delete $self->{STATES}->{$args{STATE}}->{$args{SYMBOL}}; } else { delete $self->{STATES}->{$args{STATE}}; } return $self; } # Be sure to override in child sub normalize { my ($self, $symbol) = @_; my $ret = {}; $ret->{SYMBOL} = $symbol; return $ret; } sub process { my ($self, $rawSymbol) = @_; my $state = $self->{STATES}->{$self->{CURRENT}}; $rawSymbol = $self->normalize($rawSymbol); my $symbol = $rawSymbol->{SYMBOL}; print STDERR "Current state " . $self->{CURRENT} . ", got symbol " . $symbol . "\n"; if (!exists $state->{$symbol} && exists $state->{'*'}) { print STDERR "Unrecognized symbol " . $symbol . ", using *\n"; $symbol = "*"; } # Do some action! $state->{$symbol}->{ACTION}($self, $rawSymbol) if ref $state->{$symbol}->{ACTION}; # Switch state if (exists $state->{$symbol}->{NEXT}) { $self->{CURRENT} = $state->{$symbol}->{NEXT}; } else { die "Don't know how to handle symbol " . $rawSymbol->{SYMBOL}; } return $self; } 1;
私はすべての方法の名前がそれ自体を物語っていると信じています。 おそらく、 正規化方法と処理方法について詳しく説明する価値があります。 1つ目は、入力文字列を、オートマトンのアルファベットに簡略化された入力シンボルを使用して、SYMBOLフィールドを含むハッシュに変換します。 そして、 プロセスは実際に状態間の遷移プロセスの「クロッキング」を実行し、次の信号を処理します。
これがどのように機能するかを簡単に確認します。 クラスの中心はSTATESブランチテーブルです。これはハッシュのハッシュのハッシュです:)。 ここでの考え方はシンプルです。最初のレベルでは、状態のリスト（STATE）とそれに関連付けられた属性があります。 遷移は入力シンボル（SYMBOL）のみによって決定されるため、これらの属性はこの状態で実際に有効な信号になります。 さて、シグナルにより、次の状態（NEXT）と、付属物ではアクション（ACTION）を既に決定できます。これはメソッドへの単なる参照です。
つまり プロセスでは、まず入力文字列から入力アルファベットの文字を取得し（ normalize ）、状態のリストから現在の状態を取得します。 着信文字が定義されているかどうかを確認します。 定義されていない場合、「*」が他の記号に飛んでいると見なされます。 次に、状態と信号のペアに対してアクションが定義されているかどうかを確認します。 定義されている場合、実行します。 定義されている場合は、次の状態に進みます（CURRENT変数を変更します）。 定義されていない場合、実際にはこれはマシンにとって致命的なエラーです。
教育目的のために、もちろん、マシンをSTDERRに切り替えることに関する情報を表示します。必要に応じて、デバッグなどのためにこの出力をログにラップすることは難しくないと思います。
例
何かを実装してみましょう。 ある種のチャットボットにしましょう。
以下のルールを基礎として使用します。
- コマンドを実行する前に、まず自己紹介する必要があります （ login ）
- memorizeコマンドでは 、ユーザーが入力したすべての内容を記憶し、 終了コマンドで終了します。
- コマンドNで 、記憶されたフレーズ番号Nを表示します
- セッションはexitコマンドで終了します
したがって、この例の変換テーブルを作成しましょう。
| 記号 | 状態 | 次の状態 | アクション |
|---|---|---|---|
| ログイン | 初期化 | セッション | セッションを開く |
| * | 初期化 | 初期化 | - |
| * | セッション | セッション | - |
| 言う | セッション | セッション | 行番号Nを印刷します |
| 終了 | セッション | 初期化 | - |
| 暗記する | セッション | 店舗 | - |
| * | 店舗 | 店舗 | 文字列をバッファに保存 |
| 終了 | 店舗 | セッション | - |
合計で、マシンのアルファベットは文字（ログイン、記憶、言う、終了、*）で構成され、マシンには3つの状態（INIT、SESSION、およびSTORE）があります。
さて、実装しましょう。 まず、必要に応じてコンストラクターにジャンプテーブルを設定します-呼び出されたメソッドへのリンクを追加します。 難なく:)
package ChatBot; use FSM; @ISA = ("FSM"); use strict; use Carp; use vars qw($AUTOLOAD); sub new { my $proto = shift; my $class = ref($proto) || $proto; my $self = $class->SUPER::new("INIT"); $self->addState(STATE => "INIT", SYMBOL => "*", NEXT => "INIT", ACTION => \&doIntroduce); $self->addState(STATE => "INIT", SYMBOL => "LOGIN", NEXT => "SESSION", ACTION => \&doLogin); $self->addState(STATE => "INIT", SYMBOL => "EXIT", NEXT => "INIT", ACTION => \&doQuit); $self->addState(STATE => "SESSION", SYMBOL => "*", NEXT => "SESSION"); $self->addState(STATE => "SESSION", SYMBOL => "EXIT", NEXT => "INIT"); $self->addState(STATE => "SESSION", SYMBOL => "SAY", NEXT => "SESSION", ACTION => \&doSay); $self->addState(STATE => "SESSION", SYMBOL => "MEMORIZE",NEXT => "STORE"); $self->addState(STATE => "STORE", SYMBOL => "*", NEXT => "STORE", ACTION => \&doRemember); $self->addState(STATE => "STORE", SYMBOL => "EXIT", NEXT => "SESSION"); $self->{SESSION} = {}; $self->{LOGIN} = ""; return $self; } sub normalize { my ($self, $symbol) = @_; my $ret = {}; if ($symbol =~ /^(\S+)(.*)$/) { $ret->{SYMBOL} = uc $1; $ret->{DATA} = $2; $ret->{RAW} = $symbol; } else { $ret->{SYMBOL} = "*"; $ret->{DATA} = $symbol; $ret->{RAW} = $symbol; } return $ret; } sub doIntroduce { my $self = shift; print "Please introduce yourself first!\n"; return $self; } sub doLogin { my ($self, $symbol) = @_; print "Welcome," . $symbol->{DATA} . "\n"; $self->{LOGIN} = $symbol->{DATA}; $self->{SESSION}->{$self->{LOGIN}} = () unless exists $self->{SESSION}->{$self->{LOGIN}}; return $self; } sub doSay { my ($self, $symbol) = @_; if (defined $self->{SESSION}->{$self->{LOGIN}}->[$symbol->{DATA}]) { print $self->{SESSION}->{$self->{LOGIN}}->[$symbol->{DATA}]; } else { print "No record\n"; } return $self; } sub doRemember { my ($self, $symbol) = @_; push @{ $self->{SESSION}->{$self->{LOGIN}} }, $symbol->{RAW}; return $self; } sub doQuit { my ($self, $symbol) = @_; print "Bye bye!\n"; exit; return $self; } 1;
遷移図は次のとおりです。
この場合の遷移表の形式は次のとおりです。
{ 'INIT' => { '*' => { 'ACTION' => \&doIntroduce, 'NEXT' => 'INIT' }, 'LOGIN' => { 'ACTION' => \&doLogin, 'NEXT' => 'SESSION' }, 'EXIT' => { 'ACTION' => \&doQuit, 'NEXT' => 'INIT' } }, 'STORE' => { '*' => { 'ACTION' => \&doRemember, 'NEXT' => 'STORE' }, 'EXIT' => { 'NEXT' => 'SESSION' } }, 'SESSION' => { 'SAY' => { 'ACTION' => \&doSay, 'NEXT' => 'SESSION' }, '*' => { 'NEXT' => 'SESSION' }, 'MEMORIZE' => { 'NEXT' => 'STORE' }, 'EXIT' => { 'NEXT' => 'INIT' } } }
これらのクラスを使用して最も簡単なプログラムを作成しましょう。
use ChatBot; $bot = ChatBot->new(); while(<>) { $bot->process($_); }
さて、簡単なチェック。 入力時に、次のシーケンスを与えます。
hello world! login %username% hello world! say 3 memorize hey, do you really remember everything i would say? let's check exit say 0 exit hello login %username% say 1 exit
私たちは何を逃げ出しますか？
Please introduce yourself first! Welcome, %username% No record hey, do you really remember everything i would say? Please introduce yourself first! Welcome, %username% let's check
一般的に、自分で試してみてください。
おわりに
したがって、最も単純な有限状態マシンを実装しました。 複雑なことは何もないようですか？ これはどこで役立ちますか？ さて、チャットボットではすべてが明確です。 同じことは、反対側に人ではなく鉄片がある場合にも起こります-コマンドを送信し、答えを聞くことで、たとえば、ルーターの設定を調整するボットを作成できます。 対話型コマンドインターフェイス？ はい、実際に実装しました！ ステートフルプロトコルを使用してサービスに接続したいですか？ これ以上簡単なことはありません！
私の記事が少なくとも誰かに役立つことを願っています。 はい、実装は原始的であり、非常に多くの既製のものがあります。 でも、ゼロから何かをやろうとするのは面白いですね。
どんなコメントでも喜んでいます。