オートマトンベースプログラミング

オートマトンベースプログラミングは、プログラムまたはその一部を有限状態機械（FSM）またはその他の（多くの場合、より複雑な）形式的オートマトン（オートマトン理論を参照）のモデルとして考えるプログラミングパラダイムです。場合によっては、潜在的に無限の状態集合が導入され、そのような集合は単なる列挙ではなく複雑な構造を持つことがあります

有限状態マシンベースのプログラミングは一般的に同じですが、正式に言えば、FSM は有限状態マシンの略であり、オートマトンベースのプログラミングでは厳密な意味で FSM が必ずしも採用されないため、すべての可能なバリエーションをカバーしているわけではありません。

次のプロパティは、オートマトンベースのプログラミングの重要な指標です。

プログラムの実行時間は、オートマトンの各ステップに明確に分割されています。各ステップは、実質的に単一のエントリポイントを持つコードセクション（すべてのステップで同じ）の実行です。このセクションは、異なる状態に応じて実行されるサブセクションに分割される場合がありますが、これは必須ではありません。
オートマトンの各ステップ間の通信は、オートマトン状態と呼ばれる明示的に示された変数群を介してのみ可能です。任意の2つのステップ間では、プログラムはローカル変数の値、戻りアドレス、現在の命令ポインタなど、状態を表す暗黙的な要素を持つことはできません。つまり、オートマトンの各ステップに入る任意の2つの時点におけるプログラム全体の状態は、オートマトン状態として扱われる変数の値のみが異なる可能性があります。

オートマトンベースのコード全体の実行は、オートマトンステップの サイクルです。

オートマトンベースプログラミングの概念を使用するもう 1 つの理由は、この手法におけるプログラマーのプログラムに対する考え方が、チューリングマシンやマルコフアルゴリズムなどを使用して数学的なタスクを解決する際に使用される考え方と非常に似ていることです。

例

タスク

標準入力からテキストを1行ずつ読み取り、各行の最初の単語を標準出力に書き込むタスクを考えてみましょう。まず、先頭の空白文字があればすべてスキップします。次に、最初の単語のすべての文字を出力します。最後に、改行文字に遭遇するまで、末尾の文字をすべてスキップします。ストリームの先頭以外で改行文字のシーケンスに遭遇した場合は、最初の改行文字のみを出力し、残りの改行文字をスキップします。それ以外の場合は、すべてをスキップします。次に、次の行からプロセスを再開します。ファイルの終了条件に遭遇すると（ステージに関係なく）、停止します

伝統的なプログラム

上記のタスクを実行する従来のCプログラムは次のようになります。

#include <ctype.h> #include <stdio.h>int main ( void ) { int c ;実行{実行{ c = getchar (); } while ( isspace ( c ));while ( ! isspace ( c ) && c != EOF ) { putchar ( c ); c = getchar (); } while ( c != '\n' && c != EOF ) { c = getchar (); } if ( c == '\n' ) { putchar ( c ); } } while ( c != EOF );0を返す; }

たとえば、次の入力で上記のプログラムをコンパイルして実行すると、

$ clang project.c && ( printf "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge" | ./a.out )

結果:

foo qux

オートマトンベースのプログラム

手続き型

同じタスクは、有限状態機械（）で考えることで解決できます。行の解析には3つの段階があります。先頭の空白文字をスキップする、最初の単語の文字を出力する、そして末尾の文字をスキップする、というものです。これらの状態はBEFORE、、INSIDE、と呼ばれますAFTER。このプログラムをオートマトンベースで記述すると、次のようになります。

#include <ctype.h> #include <stdio.h>列挙型状態{ BEFORE 、INSIDE 、AFTER };int main ( void ) { int c ; enum State s = BEFORE ;while (( c = getchar ()) != EOF ) { switch ( s ) { case BEFORE : if ( ! isspace ( c )) { putchar ( c ); s = INSIDE ; } break ; case INSIDE : if ( c == '\n' ) { putchar ( c ); s = BEFORE ; } else if ( isspace ( c )) { s = AFTER ; } else { putchar ( c ); } break ; case AFTER : if ( c == '\n' ) { putchar ( c ); s = BEFORE ; } break ; } }0を返す; }

プログラムは長く見えるかもしれませんが、少なくとも1つの大きな利点があります。それは、関数の呼び出し命令（つまり、読み込み命令）が1つgetcharしかないことです。さらに、ループも従来のバージョンでは4つありましたが、今回は1つだけです。ループ本体はオートマトンステップwhileであり、ループ自体はオートマトンステップのサイクルです。このプログラムは、状態図に示されている有限状態機械の動作を実装しています。

このプログラムの最も重要な特性は、オートマトンステップのコードセクションが明確にローカライズされていることです。step自動化ステップに明示的な関数を付与することで、この特性はより明確に示されます。

#include <ctype.h> #include <stdio.h>列挙型状態{ BEFORE 、INSIDE 、AFTER };void step ( enum State * const s , int const c ) { switch ( * s ) { case BEFORE : if ( ! isspace ( c )) { putchar ( c ); * s = INSIDE ; } break ; case INSIDE : if ( c == '\n' ) { putchar ( c ); * s = BEFORE ; } else if ( isspace ( c )) { * s = AFTER ; } else { putchar ( c ); } break ; case AFTER : if ( c == '\n' ) { putchar ( c ); * s = BEFORE ; } break ; } }int main ( void ) { int c ; enum State s = BEFORE ;while (( c = getchar ()) != EOF ) { step ( & s , c ); }0を返す; }

このプログラムは、オートマトンベースのコードにおける基本的な特性を明確に示しています。

オートマトンステップ実行の期間は重複できません。
前のステップから次のステップに渡される情報は、明示的に指定されたオートマトンの状態のみです。

有限オートマトンは現在の状態、列が入力、セルが次の状態と実行するアクションを表す状態遷移テーブルによって定義できます。

状態遷移表
入力現在の状態	改行	空白	その他
前	前	前	内側/印刷
内側	印刷前/印刷後	印刷後	内側/印刷
印刷後	印刷前/印刷後	印刷後	印刷後

**状態図**
入力ストリームの各行の最初のワードを出力する有限状態機械の状態図。機械は、現在の状態と検出された文字に応じて、各ステップで正確に1つの遷移を実行します。遷移に伴うアクションは、何もしないか、検出された文字を出力するかのいずれかです。これはprintで示されます。

transitions一般的に言えば、オートマトンベースのプログラムではこのアプローチを自然に使用できます。状態遷移表として明示的な2次元配列を指定すると、プログラムはこのアプローチを使用します。

#include <ctype.h> #include <stdio.h>列挙型状態{ BEFORE 、INSIDE 、AFTER };void nop ( int const c ) {}void print ( int const c ) { putchar ( c ); }構造体Branch { enum State const next_state ; void ( * action )( int ); };struct Branch const transitions [ 3 ][ 3 ] = { // 改行 空白 その他の入力/状態{{ BEFORE 、& nop }, { BEFORE 、& nop }, { INSIDE 、& print }}, // 前{{ BEFORE 、& print }, { AFTER 、& nop }, { INSIDE 、& print }}, // 内部{{ BEFORE 、& print }, { AFTER 、& nop }, { AFTER 、& nop }} // 後};void step ( enum State * const s , int const c ) { int const row = ( * s == BEFORE ) ? 0 : ( * s == INSIDE ) ? 1 : 2 ; int const column = ( c == '\n' ) ? 0 : isspace ( c ) ? 1 : 2 ; struct Branch const * const b = & transitions [ row ][ column ]; * s = b -> next_state ; b -> action ( c ); }int main ( void ) { int c ; enum State s = BEFORE ;while (( c = getchar ()) != EOF ) { step ( & s , c ); }0を返す; }

オブジェクト指向

実装言語がオブジェクト指向プログラミングをサポートしている場合、プログラムの簡単なリファクタリングは、オートマトンをオブジェクトにカプセル化し、実装の詳細を隠すことです。オブジェクト指向スタイルを使用した C++のプログラムは次のようになります

#include <ctype.h> #include <stdio.h>列挙型状態{ BEFORE 、INSIDE 、AFTER };構造体Branch { enum State const next_state ; void ( * action )( int ); };クラスStateMachine { public : StateMachine (); void feedChar ( int );保護: static void nop ( int ); static void print ( int );private : enum State _state ; static struct Branch const _transitions [ 3 ][ 3 ]; };ステートマシン::ステートマシン() : _state ( BEFORE ) {}void StateMachine :: feedChar ( int const c ) { int const row = ( _state == BEFORE ) ? 0 : ( _state == INSIDE ) ? 1 : 2 ; int const column = ( c == '\n' ) ? 0 : isspace ( c ) ? 1 : 2 ; struct Branch const * const b = & _transitions [ row ][ column ]; _state = b -> next_state ; b -> action ( c ); }voidステートマシン:: nop ( int const c ) {}void StateMachine :: print ( intconstc ) { putchar ( c ) ; }struct Branch const StateMachine :: _transitions [ 3 ][ 3 ] = { // 改行 空白 その他の入力/状態{{ BEFORE 、& nop }, { BEFORE 、& nop }, { INSIDE 、& print }}, // 前{{ BEFORE 、& print }, { AFTER 、& nop }, { INSIDE 、& print }}, // 内部{{ BEFORE 、& print }, { AFTER 、& nop }, { AFTER 、& nop }} // 後};int main () { int c ;ステートマシンm ;while (( c = getchar ()) != EOF ) { m . feedChar ( c ); }0を返す; }

記事の主題に直接関係のない変更を最小限に抑えるために、Cの標準ライブラリの入出力getcharと関数が使用されています。 putchar

状態設計パターンは、オブジェクトが内部状態に応じて実行時に動作を変更する方法です。仮想関数呼び出しにより、大規模な条件文やテーブル参照に頼る必要はありません。大規模な条件文を使用するコードと比較した場合の主な利点は、状態固有のコードがモノリシックなブロックに局所化されるのではなく、複数のオブジェクトに分散されるため、保守性が向上することです。状態遷移テーブルを使用するコードと比較した場合の主な利点は、仮想関数呼び出しはテーブル参照よりも効率的であることが多いこと、状態遷移の基準が表形式よりも明確であること、状態遷移に伴うアクションの追加が容易なことです。ただし、クラスの数が多いため、他のアプローチよりもコードがコンパクトではなくなるという新たな問題も発生します。状態設計パターンを使用したプログラムは次のようになります。

#include <ctype.h> #include <stdio.h>クラスStateMachine ;クラスState { public : virtual void feedChar ( StateMachine * 、int ) const = 0 ; };クラスBefore : public State { public : static State const * instantiate (); virtual void feedChar ( StateMachine * , int ) const override ;保護: Before () = default ;プライベート:静的State const * _instance ; };クラス内部: public State { public : static State const * instantiate (); virtual void feedChar ( StateMachine * , int ) const override ;保護:内部() =デフォルト;プライベート:静的State const * _instance ; };クラスAfter : public State { public : static State const * instantiate (); virtual void feedChar ( StateMachine * , int ) const override ;保護: After () =デフォルト;プライベート:静的State const * _instance ; };クラスStateMachine { public : StateMachine (); void feedChar ( int );保護: void setState ( State const * );private : State const * _state ;フレンドクラスBefore ;フレンドクラスInside ;フレンドクラスAfter ; };状態const * Before :: instantiate () { if ( ! _instance ) { _instance = new Before ; }_instanceを返します; }void Before :: feedChar ( StateMachine * const m , int const c ) const { if ( ! isspace ( c )) { putchar ( c ); m -> setState ( Inside :: instantiate ()); } }状態const * Before :: _instance = nullptr ;状態const *内部:: instantiate () { if ( ! _instance ) { _instance = new内部; }_instanceを返します; }void内部:: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( Before :: instantiate ()); } else if ( isspace ( c )) { m -> setState ( After :: instantiate ()); } else { putchar ( c ); } }状態const *内部:: _instance = nullptr ;状態const * After :: instantiate () { if ( ! _instance ) { _instance = new After ; }_instanceを返します; }void After :: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( Before :: instantiate ()); } }状態const *後:: _instance = nullptr ;StateMachine :: StateMachine () : _state ( Before :: instantiate ()) {}void StateMachine :: feedChar ( int const c ) { _state -> feedChar ( this 、c ); }void StateMachine :: setState ( Stateconst * consts ) { _state = s ; }int main () { int c ;ステートマシンm ;while (( c = getchar ()) != EOF ) { m . feedChar ( c ); }0を返す; }

自動化とオートマトン

オートマトンベースのプログラミングは、自動化分野におけるプログラミングのニーズに非常によく合致しています

生産サイクルは一般的に次のようにモデル化されます。

入力データ（キャプチャから）に応じて段階的に進む一連のステージ。
現在のステージに応じて実行される一連のアクション。

さまざまな専用プログラミング言語を使用すると、このようなモデルを多かれ少なかれ洗練された方法で表現できます。

自動化プログラム

上記の例は、この観点から次の擬似コードのように表現できます（「set」は論理変数をアクティブにし、「reset」は論理変数を非アクティブにし、「:」は変数を割り当て、「=」は等価性をテストします）。

改行: '\n' 空白: ('\t', '\n', '\v', '\f', '\r', ' ') 状態: (前、中、後) setState(c) { もし前であり、かつ(c != 改行かつc が空白でない)ならば、内側に設定する 内側にある場合は（c が空白の場合は後に設定し、c が改行の場合は前に設定します） after かつ c = 改行の場合は before を設定する } doAction(c) { before かつ (c != 改行 かつ c が空白文字ではない) の場合、write(c) 内側にあり、cが空白でない場合はwrite(c) after かつ c = 改行の場合、write(c) を実行します。 } サイクル { 前に設定 (c: readCharacter) = EOL { までループ setState(c) アクションを実行する(c) } }

一方でサイクルの進行を表すルーチンと、他方で実際のアクション（入力と出力の一致）を表現するルーチンを分離することで、より明確でシンプルなコードが可能になります

イベント

自動化の分野では、ステップからステップへの進行は、機械自体から送られる入力データに依存します。これはプログラムではテキストから文字を読み取ることで表現されます。実際には、これらのデータは機械の重要な部品の位置、速度、温度などに関する情報を提供します。

GUIプログラミングと同様に、マシンの状態変化は、ある状態から別の状態へと遷移し、最終的にある状態に到達するまでのイベントと見なすことができます。起こり得る状態の組み合わせによって多様なイベントが生成され、より複雑な生産サイクルが定義されます。結果として、サイクルは通常、単純な線形シーケンスとは程遠いものになります。一般的に、複数の分岐が並行して実行され、異なるイベントに応じて複数の選択肢が選択されます。これらは以下の図に模式的に示されています。

 s:ステージ c:状態 s1 | |-c2 | s2 | ---------- | | |-c31 |-c32 | | s31 s32 | | |-c41 |-c42 | | ---------- | s4

応用

オートマトンベースのプログラミングは、語彙解析や統語解析に広く使用されています。^{[ 1 ]}

それに加えて、並列プロセスやスレッドを使用する唯一の代替手段として、イベント駆動型プログラミングでは、オートマトンの観点から考えること（つまり、実行プロセスをオートマトンの各ステップに分割し、明示的なオートマトンの状態を通じてステップからステップへと情報を渡すこと）が必要です。

状態とステートマシンの概念は、形式仕様の分野でよく用いられます。例えば、UMLベースのソフトウェアアーキテクチャ開発では、プログラムの動作を記述するために状態図が用いられます。また、様々な通信プロトコルも、明示的な状態の概念を用いて記述されることがよくあります（例：RFC 793）。

オートマトン（ステップと状態）の観点から考えることは、一部のプログラミング言語のセマンティクスを記述するためにも使用できます。例えば、Refal言語で書かれたプログラムの実行は、いわゆる抽象Refalマシンの一連のステップとして記述されます。マシンの状態はビュー（変数のない任意のRefal式）です。

Scheme言語における継続は、ステップと状態という観点から考える必要がありますが、Scheme自体はオートマトンとは全く関係がありません（再帰的です）。call /cc機能を動作させるには、実装において実行中のプログラムの状態全体を捕捉できる必要がありますが、これは状態に暗黙的な部分がない場合に限り可能です。このように捕捉された状態こそが継続と呼ばれ、（比較的複雑な）オートマトンの状態と考えることができます。オートマトンにおけるステップとは、前の継続から次の継続を推論することであり、実行プロセスはそのようなステップのサイクルです。

アレクサンダー・オロングレンは著書^{[ 2 ]}の中で、形式オートマトンに完全に基づいたプログラミング言語の意味記述のいわゆるウィーン方式について説明しています。

STATシステム[1]はオートマトンベースのアプローチを使用する良い例です。このシステムには、他の機能に加えて、純粋にオートマトン指向の STATLと呼ばれる組み込み言語が含まれています。

歴史

オートマトンに基づく技術は、形式言語解析など、オートマトン理論に基づくアルゴリズムが存在する分野で広く使用されていました。^{[ 1 ]}

これに関する初期の論文の一つは、ジョンソンらによる1968年の論文である。^{[ 3 ]}

オートマタベースのプログラミングが一般的な手法として最初に言及されたのは、 1963年のピーター・ナウアの論文です。 ^{[ 4 ]}著者はこの手法をチューリングマシンアプローチと呼んでいますが、論文では実際のチューリングマシンは示されておらず、代わりにステップと状態に基づく手法が説明されています。

命令型プログラミングと手続き型プログラミングの比較

状態の概念はオートマトンベースのプログラミングに特有のものではない。^{[ 5 ]} 一般的に言えば、状態（またはプログラム状態）は、あらゆるコンピュータプログラムの実行中に、実行中に変化し得るすべての情報の組み合わせとして現れる。例えば、伝統的な命令型プログラムの状態は、

すべての変数の値と動的メモリ内に保存される情報。
レジスタに格納された値。
スタックの内容（ローカル変数の値と戻りアドレスを含む）
命令ポインタの現在の値。

これらは、明示的な部分 (変数に格納される値など) と暗黙的な部分 (戻りアドレスや命令ポインター) に分けられます。

とはいえ、オートマトンベースのプログラムは、命令型プログラムの特殊なケースと見なすことができ、暗黙的な状態が最小限に抑えられます。ステップコードセクションに入る2つの異なる瞬間におけるプログラム全体の状態は、オートマトンの状態のみで異なる可能性があります。これにより、プログラムの解析が簡素化されます。

オブジェクト指向プログラミングの関係

オブジェクト指向プログラミングの理論では、オブジェクトは内部状態を持ち、メッセージを受信し、それに応答し、他のオブジェクトにメッセージを送信し、メッセージ処理中に内部状態を変更することができます。より実用的な用語では、オブジェクトのメソッドを呼び出すことは、 オブジェクトにメッセージを送信することと同じと見なされます

したがって、オブジェクト指向プログラミングのオブジェクトは、状態がプライベートフィールドの組み合わせであり、1つ以上のメソッドがステップとして扱われるオートマトン（またはオートマトンモデル）と見なすことができます。これらのメソッドは、直接的にも間接的にも、互いに、あるいは自身を呼び出してはいけません。そうでなければ、オブジェクトはオートマトンベースの方法で実装されているとは見なされません。

一方、オブジェクトはオートマトンモデルの実装に適しています。オブジェクト指向言語においてオートマトンベースのアプローチを用いる場合、オートマトンモデルは通常クラスによって実装され、状態はクラスのプライベートフィールドで表現され、ステップはメソッドとして実装されます。このようなメソッドは通常、クラス内で唯一の非定数パブリックメソッド（コンストラクタとデストラクタを除く）です。他のパブリックメソッドは状態を照会することはできますが、変更することはできません。すべてのセカンダリメソッド（特定の状態ハンドラなど）は、通常、クラスのプライベート部分内に隠蔽されます。

参照

セルオートマトン
非決定性プログラミング
状態パターン
Esterel、オートマトンベースの言語
Umple、Java と C++ にオートマトンを追加するツール

参考文献

^ ^a ^bアルフレッド・V・アホ、ジェフリー・D・ウルマン（1973年）。構文解析、翻訳、コンパイルの理論。第1巻。ニュージャージー州エングルウッド・クリフス：プレンティス・ホール。ISBN 0-13-914564-8。
^オロングレン、アレクサンダー (1974). 『オートマトン解釈によるプログラミング言語の定義』ロンドン: アカデミック・プレス. ISBN 0-12-525750-3。
^ Johnson, WL; Porter, JH; Ackley, SI; Ross, DT (1968). 「有限状態技術を用いた効率的な語彙プロセッサの自動生成」 . Comm ACM . 11 (12): 805– 813. doi : 10.1145/364175.364185 . S2CID 17253809 .
^ Naur, Peter (1963年9月). 「GIER ALGOLコンパイラの設計パートII」. BIT Numerical Mathematics . 3 (3): 145– 166. doi : 10.1007/BF01939983 . S2CID 189785656 .
^ 「オートマトンベースプログラミング」（PDF） .情報技術、機械、光学に関する科学技術ジャーナル（53）. 2008年.

外部リンク

JV Noble. «Finite State Machines in Forth» — Forthによるオートマトンベースのプログラミング
Harel, David (1987). 「ステートチャート：複雑系のための視覚的形式主義」(PDF) .科学・コンピュータ・プログラミング. 8 (3): 231– 274. doi : 10.1016/0167-6423(87)90035-9 .
Harel, David; Drusinsky, D. (1989). 「ハードウェアの記述と合成におけるステートチャートの利用」. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 8 (7): 798– 807. doi : 10.1109/43.31537 . S2CID 8754800 .
Polikarpova NI、Shalyto AAオートマトンベースのプログラミングSPb.: Piter。 2009年（ロシア）
ITMO大学「プログラミング技術」学科

[gram-1] アルフレッド・V・アホ、ジェフリー・D・ウルマン（1973年）。構文解析、翻訳、コンパイルの理論。第1巻。ニュージャージー州エングルウッド・クリフス：プレンティス・ホール。ISBN 0-13-914564-8。

[2] オロングレン、アレクサンダー (1974). 『オートマトン解釈によるプログラミング言語の定義』ロンドン: アカデミック・プレス. ISBN 0-12-525750-3。

[3] Johnson, WL; Porter, JH; Ackley, SI; Ross, DT (1968). 「有限状態技術を用いた効率的な語彙プロセッサの自動生成」 . Comm ACM . 11 (12): 805– 813. doi : 10.1145/364175.364185 . S2CID 17253809 .

[4] Naur, Peter (1963年9月). 「GIER ALGOLコンパイラの設計パートII」. BIT Numerical Mathematics . 3 (3): 145– 166. doi : 10.1007/BF01939983 . S2CID 189785656 .

[5] 「オートマトンベースプログラミング」（PDF） .情報技術、機械、光学に関する科学技術ジャーナル（53）. 2008年.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]