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

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

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

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

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

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

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

標準入力からテキストを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 )     

結果:

フーククス
​

同じタスクは、有限状態マシンの観点から考えることで解決できます。行の解析には、先頭の空白文字をスキップし、最初の単語の文字を出力し、末尾の文字をスキップするという 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 つの大きな利点があります。それは、読み取り(つまり、getchar関数の呼び出し) 命令が 1 つしかないことです。さらに、従来のバージョンには 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 を返す; } 

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

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

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

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

#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 (前) {}  


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 ( int const c ) { 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 * instanceiate (); virtual void feedChar ( StateMachine * , int ) const override ;    
  
       
         

  保護: 
Before () = default ;      

  プライベート:
静的State const * _instance ; };       



クラス内部: public State { public : static State const * instanceiate (); virtual void feedChar ( StateMachine * , int ) const override ;    
  
       
         

  保護:
内部() =デフォルト;      

  プライベート:
静的State const * _instance ; };       



クラスAfter : public State { public : static State const * instanceiate (); virtual void feedChar ( StateMachine * , int ) const override ;    
  
       
         

  保護: 
After () = default ;      

  プライベート:
静的State const * _instance ; };       



クラスStateMachine { public : StateMachine (); void feedChar ( int );  
  
    
     

  保護: 
void setState ( State const * );      

  private : 
State const * _state ; friend class Before ; friend class Inside ; friend class After ; };      
      
      
      



状態const * Before :: instanceiate () { if ( ! _instance ) { _instance = new Before ; }   
    
       
  

  _instanceを返します。 



void Before :: feedChar ( StateMachine * const m , int const c ) const { if ( ! isspace ( c )) { putchar ( c ); m -> setState ( Inside :: instanceiate ()); } }        
    
    
    
  



状態const * Before :: _instance = nullptr ;    


状態const *内部:: instanceiate () { if ( ! _instance ) { _instance = new内部; }   
    
       
  

  _instanceを返します。 



void内部:: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( Before :: instanceiate ()); } else if ( isspace ( c )) { m -> setState ( After :: instanceiate ()); } else { putchar ( c ); } }        
      
    
    
      
    
    
    
  



状態const *内部:: _instance = nullptr ;    


状態const * After :: instanceiate () { if ( ! _instance ) { _instance = new After ; }   
    
       
  

  _instanceを返します。 



void After :: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( Before :: instanceiate ()); } }        
      
    
    
  



状態const *後:: _instance = nullptr ;    


StateMachine :: StateMachine () : _state ( Before :: instanceiate ()) {}  


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 を設定する
}


アクションを実行します(c) {
  もし前であり、(c != 改行で、c が空白でない) ならば、write(c) と書く。
  内側にあり、c が空白でない場合は write(c) と記述します。
  after かつ c = newline の場合、write(c)
}


サイクル {
  前に設定

  (c: readCharacter) = EOL になるまでループします {
    ステートを設定する(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++ にオートマトンを追加するツール

• JV Noble。「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大学「プログラミング技術」部門