自動プログラミング。 パート3.状態と遷移図。 継続

目次

状態図！=グラフ図。

図1（c）は、状態図と遷移の誤った記録の例を示しています。 不正確な点は、赤い長方形で強調表示された遷移は、入力イベントだけでなく、この状態では同じ名前の元のグラフダイアグラムのフラグに対応するフラグによっても決定されることです（図 1（a）は、入力文字のみを考慮してプロセスの状態を監視することができなくなったため、フラグcを変更するロジックを何らかの形で考慮する必要があります。 問題はフラグc自体にもありませんが、このフラグを変更するロジックが状態s1だけに結び付けられていないという事実にあります。 このフラグの変更に関連付けられたイベントがs1のみに関連付けられる場合、そのような問題は存在しません。 赤で強調表示された遷移はs1に到達したパスに依存します 。これはオートマトンの定義と矛盾し、反応は入力シンボルと現在の状態のみに依存します。 本文でさらに言及するために、これを自動化の原則と呼びます。

図のアルゴリズムの顕著な非手動実装のグラフ方式 1（a）は、状態が明示的に定義されておらず、したがって状態間の遷移が定義されていないため、正しい状態図の形式で記述するのはそれほど簡単ではありません。 図の図を描くには 1（b）図のアルゴリズムによる 1（a） 同等のオートマトンを取得する必要がありました。 グラフスキームの同等のオートマトンを取得する手法は、次のいずれかの記事で検討対象になります。「非自動」プログラムを含むデジタルデバイスはすべて、これらの状態は明示的に記述されていないにもかかわらず、 数学的な意味での状態です。 このような状態は、量子電気力学の量子光子に似ており、簡単に説明することができます。それらはどこにでもあり、どこにも特定ではありませんが、存在し、作用します。

この例では、偶然、グラフ図の各ブランチが1つの状態に対応しています。 つまり、各出力シンボルは1つの状態でのみ取得されます。 ただし、フラグを変更するロジックが異なる場合、1つの出力シンボルが複数の異なる状態で取得されるか、言い換えると、グラフ図の同じブランチが複数の異なる状態に対応することがわかります。 これは、わかりやすさの点でさらに複雑なケースです。

州について話しているので、完全に自然な質問が発生します：「いくつの州に対処しなければなりませんか？」 自動実装では、必要に応じて、状態の数をある程度まで任意に設定します。

非手動アプローチの場合、同等のオートマトンの潜在的な状態の数は次のとおりです。

$$$$表示$$ 2 ^ \テキスト{total_digit_of all_variable_variables_being、ビット。 } $$表示$$

行動を決定する変数が少ない場合、アルゴリズムの記述の複雑さはそれほど顕著ではありませんが、そのような変数の数が増えると、アルゴリズムの知覚の複雑さは指数関数的に増大し、精神を抑圧します。

動作を定義する変数という用語を明確にする必要があります。 非手動実装の場合、これは実質的にアルゴリズム分岐を作成する変数です。 自動実装の場合、これは内部状態変数です。 変数として、 内部状態は、すべての状態がリストされている列挙型変数（=ちょうどint）、または2つの状態しかない場合は単なるbool変数です。 次に、オートマトンのソフトウェア実装のさまざまなオプションを示します。

すでに記事の冒頭で述べたように、グラフ図はオートマトンの記録形式であるだけでなく、従来のアルゴリズムの記録形式でもあります。 条件付き遷移操作が遷移矢印で表されているという事実は、驚くことではありませんが、サイクルをどのように表現するのでしょうか？ 私たちのマシンが長方形のテーブルを通過するとしましょう。つまり、垂直サイクルと水平サイクルの変数の組み合わせの合計数はm * nです。 結果のオートマトンには同じ数の状態がありますか？つまり、オートマトンスタイルでループを記述する方法はありますか？

ループを考えてみましょう：

for(i = 5; i--; ){} 

• 水平サイクルカウンター 、ステータスを決定します。
  {0}-垂直ループ、
  {1、...、5、...}-水平サイクル、
• 垂直サイクルカウンターが終了条件を決定します。

外部とみなせる唯一のイベントは行末です。このオートマトンの他のすべてのイベントは純粋に内部であり、アルゴリズム自体の動作によって生成されます。 ただし、これは、前述の自動化の原則に違反しません。特定の状態からの遷移に影響するすべてのイベントは、同じ状態自体によって生成されるためです。つまり、オートマトンの動作は、この状態への到達方法に依存しません。

自動実装されたプログラムはグラフ図として表すことができ、自動的に実装されたままになります。 図 4.対応する状態図のグラフ図と、記事の冒頭に示した遷移の例を示します。

ご覧のように、自動的に実装されたプログラムを記録すると、コンパクトさに関してグラフ図は状態図よりも著しく失われます。
ここで、自動プログラミングと自動回路を区別するものを検討してください。

自動回路のアーチファクト。

危機にwhatしているものをよりよく理解するために、ソフトウェアマシンの2つのカテゴリ（シンボリックと機能）を紹介します。 キャラクターマシンは、入力で一連の文字を受け入れ、出力で一連の文字を発行するマシンです。 これは、古典的な抽象オートマトン 、離散数学で実際に考慮されるオートマトンの完全な類似物です。 文字オートマトンは、コードの認識、正規表現の解析、言語分析、機能オートマトンの最適化、および一般的なアルゴリズムに使用されます。 それらの実装方法については、今日の記事の後半で説明し、次のいずれかの記事で詳細に説明します。

機能的なソフトウェアマシンは、これらのマシンとは反対です（本文ではプログラムと呼びます）-コンピューターまたはマイクロコントローラーのアプリケーションと制御プログラムの完全な類似体です。 これらは、同じモジュール、周辺機器のマイクロコントローラを制御するサブルーチン、またはいくつかの有用な作業を実行するサブルーチン、またはユーザーとのインタラクティブな作業を実装するサブルーチンですが、自動的に設計および実装されます。

自動回路では、抽象オートマトンの開発後の次のステップは構造合成です。抽象信号と状態が「ライブ」ビットでエンコードされ、エンコード方法が選択されると、すでにエンコードされたビットで動作する論理回路が構築されます。 機能的なソフトウェアマシンは、構造マシンに類似したソフトウェアです。

回路の観点からのみ機能的オートマトンを検討し、それらに構造的オートマトン以上のものが見えない場合、そのような狭い外観は干渉する可能性が高くなります。 このアプローチは、自動回路からのトレーシングペーパーであり、自動設計されたモジュールの配置方法のテンプレートを提供します。

これは、設計プロセスが面倒になるという事実につながり、ほとんどの場合、このテンプレートで規定されている不必要な正式な手順が含まれます。
しかし、実際のプロセスを形式化されたシグナルのセットに変えたり、ある種の「自動化された」APIを使用しないことは、自動プログラミングの利点をもたらします。 利点は、状態図のカテゴリに動的プロセスを記録することです。これにより、プログラミングがより予測可能になります。 オートマトンを操作オートマトンと制御オートマトンに適切に分割します。この分割の一部として、操作オートマトンを正しく合理的に選択することにより、ソリューションが効果的になり、次の記事で説得力を持って示されます。

回路自動機の開発者の動作を機械的にコピーします。これは、アーティファクトという言葉が意味するものです。自動プログラミングは、自動回路の揺りかごを残して、プログラムを処理します。 このプログラムは非常に便利でプラスチック素材であり、この素材の可塑性が人気を集めました。 通常の方法でプログラミングすることにより、デジタル回路を設計するルーチンを省くことができます。 アクションを実行する必要がある場合、条件を確認して実行します。特別なトリガー関数を作成する必要はありません。 私は何について話しているのですか？ このように書くことができます：

 if(IO_latch->Data_1_received && IO_latch->Permission) { State = 5; } 

 typedef bool paTrigger(); typedef void paAction(); struct tLink_Trigger_Action { paTrigger * Trigger; paAction * Action; int Next_state; }; bool Trigger_X(){return(IO_latch->Data_1_received && IO_latch->Permission);}; void Action_X(){State = 5;}; tLink_Trigger_Transition Table[States_max][ Triggers_max] = { /*State_0*/{}, /*State_1*/{ …,{ Trigger_X, Action_X }, … }, /*State_2*/{}, /*State_3*/{}, /*State_4*/{}}; uint Engine (uint Message) { if(State->Trigger()) { State->Action(); State = State->Next_state; } … } 

超形式主義の支持者が異議を唱えることができるのは、通常のプログラミングでは会計処理が少なく、自動回路方式ではすべてのビットがカウントされるということだけです。 これに対して、パラメータを考慮することに問題がある場合、アカウンティングを考慮してメインマシンをルーチンから解放するサブマシンを作成する価値があると答えます。 これは、建設的な分解のヒントです。

プログラムに関連する状況のドラマは、動的プロセスのモデリングと分析のための便利なツールを提供する自動メンタルテンプレートが同時に重い開発者を支配し、通常のプログラミングの単純な喜びを奪うという事実にあります。 私の意見では、これは自動プログラミング技術がエキゾチックな好奇心以上に上昇できない最も深刻な理由の1つです。

ご想像のとおり、この論争の的となっている状況を克服するための自然な方法は、両方のパラダイムを最大限に活用することです。 この場合、内部状態は次の着信イベントの処理方法を示すものではなく、一種の動作モードになります。 これは重要です。 むしろ、状態は、アルゴリズムがしばらくの間使用されているサブルーチンと見なされる必要があります。 同時に、彼は入力信号を処理し、週末にどこにでも行かずに放送することができます。 ある状態では、プログラムが同じタイプの作業を実行し、同じタイプの範囲を超えるすべてのものが別の状態に転送されることが理解されます。 状態から状態への遷移は、信号によって行われるのではなく、このアルゴリズムにとって重要なイベントによってのみ行われます。 そして、選択した条件に基づいて、これらのイベントを自分で選択します。 したがって、各状態モードには埋め込みプログラムを含めることができます。

つまり、プログラムを使用すると、 企業のマルチタスクの概念になります。これは、 企業のマルチタスクの古典的なアルゴリズムとは対照的に、何らかの理由で通常のアプリケーション自体が何らかの理由でOSを参照し、システムに制御を返す場合、プログラムは最初に設計されます制御を1ステップだけ受け取るプログラムとして、それを実行し、制御を次の反復に渡します。 企業のマルチタスクとプログラムの違いは正式に条件付きですが、プログラムを自動的に見ることはその反復性を意味するため、プログラムが制御を戻すことを「忘れる」ような問題はありません。

図に示すように、プログラムはマルチスレッドOSの制御下でも問題なく動作します。 同時に、もちろん、企業のマルチタスクは不要のようですが、モジュールの自動デバイスは、自動設計に関連する上記のすべての利点を保持しています。

プログラムは、移行中に発生する単一のアクションを実行でき、同じ状態（動作モード）で拡張アクティビティを実行できるため、その状態図は機能とMiles and Moorsを取得します。 たとえば、パーキングメーターは状態図で表されます。

パーキングメーターの例はまだ検討されていませんが、状態図を見ると、何が危険なのかを理解するのは簡単です。 状態図によるこのカウンタの説明は、テキストを使用して作成された同じマシンの説明よりもはるかに有益であることに注意してください。

理論の観点からは、ミーリーオートマトンとムーアオートマトンの機能を1つの状態図に組み合わせることで間違いを犯しません。 そのようなオートマトンで数学演算を実行する必要がある場合、それはミーリー・オートマトンと見なすことができます。 同じ機能を備えた抽象オートマトンの場合、Mealyオートマトンはより少ない状態で結果を出すことができます。 マイルをムーアマシンに、またはその逆に変換するための数学的手法があります。

上記はプログラムが何であるかについて少し光を当てます。それらを実装する方法に移りましょう。

機能的なソフトウェアを実装する方法。

グラフ図から直接続く最も明白な「直接的な」解決策は、switchステートメントを使用して、複数Cの代替の状態を決定することです。 次の入力シンボルを受け取ると、プログラムは現在の状態を判別し、状態ごとに入力シンボルが分析され、入力シンボルごとに特定の状態への遷移だけでなく出力シンボルも設定されます。

 #define mStep ((uword) (-2))// .  uint Automaton (uint Input) { static uint State = 3; uint Out; {,     ,   }; switch (State) { //////////////////////////////////////////// case 1: switch (Input) { /////////// case 0: { ,   }; State = 2; Out = 2; break; /////////// case 1: { ,   }; State = 3; Out = 3; break; /////////// case 2: { ,   }; State = 6; Out = 6; break; /////////// case mStep: break; } break; //////////////////////////////////////////// case 2: ... //////////////////////////////////////////// case 3: ... //////////////////////////////////////////// case 4: ... //////////////////////////////////////////// case 5: ... //////////////////////////////////////////// case 6: ... default: // Error }; return(Out); } 

Automataは、 SwitchテクノロジーとIAR visualStateで同様の方法で実装されます。

プログラマーステートの概念は、移行を行わずにしばらく機能するが、同時に「小さなアクティビティ」を継続できるプログラム操作モードとして解釈するため、プログラムを新しい状態に移行することが保証されていない入力シンボルがあるはずです（内部的な理由で彼が独りで行かない限り）、しかし、彼はそれを毎回アクティブにします。 ステップ記号はmStepです。

2番目の実装オプションは根本的に異なります。リストに示すように、各イベントのハンドラーを作成します

 uint Message_i0_handler(uint &State) { uint Out; switch (State) { //////////////////////////////////////////// case 1: { ,   }; State = 2; Out = 2; break; //////////////////////////////////////////// case 2: { ,   }; State = 1; Out = 1; break; ... }; return(Out); } uint Message_i1_handler(uint &State) { ... } uint Message_i2_handler(uint &State) { ... } void Message_Step_handler(uint &State) { switch (State) { //////////////////////////////////////////// case 1: {,     ,   }; break; //////////////////////////////////////////// case 2: {,     ,   }; break; //////////////////////////////////////////// case 3: {,     ,   }; break; }; return(mStep); } typedef uint (*paMessage_handler)(uint &State); paMessage_handler Reactions[3] = { Message_i0_handler_for_s1, Message_i1_handler_for_s1, Message_i2_handler_for_s1}; uint Automaton (uint Input) { Reactions [Input]; } 

上記のオプションは、基本的な考え方を反映した基本的なオプションですが、かなり面倒で時間がかかります。 ただし、それらは、かさばりを減らす（相対的）および作業を高速化する（実際の）方向に問題なく変更されます。

リストオプション2に示すコードを変更します。各Message_ixx_handlerイベントハンドラーを、各状態に対応する一連の関数に分割します。

 uint Message_i0_handler_for_s1(uint &State) { { ,   }; State = 2; Out = 2; return(Out); } uint Message_i0_handler_for_s2(uint &State) { { ,   }; State = 1; Out = 1; return(Out); } ... uint Message_Step_handler_for_s1(uint &State) { {,     ,   }; return(mStep); } 

 typedef uint (*paMessage_handler)(uint &State); paMessage_handler Reactions[6][3] = { { Message_i0_handler_for_s1, Message_i1_handler_for_s1, Message_i2_handler_for_s1}, ... { Message_i0_handler_for_s6, Message_i1_handler_for_s6, Message_i2_handler_for_s6}, }; paMessage_handler Reactions_for_Step [6] = { Message_mStep_handler_for_s1, ..., Message_mStep_handler_for_s6 }; uint Engine(uint Input = mStep) { uint State = 3; if(Input == mStep) return(Reactions_for_Step [State] (State)); else return(Reactions[State][Input] (State)); } 

このオプションを使用すると、割り込みハンドラーでのイベントディスパッチスキームと単一エンジンからの処理が適切に実装されます。

同様の方法が、 boost.statechartテンプレートの実装の基礎となります。

前の2つのオプションの主な欠点は、自動回路のアーティファクトです。つまり、この方法でプログラミングすると、「プログラマーのスタイル」のプログラミングを維持することができず、過度に肥大化した表形式のプログラミングスタイルを使用する必要があります。

表形式のプログラミングが提供するものを検討してください。

• 「+」は、各状態のすべてのイベントに対する反応をリストします（未処理のイベントにはスタブがあります）。 完全な説明があります。
• 「-」しかし、同時に、すべてが非常に面倒に認識されているため、一部のタイプミスの可能性は非常に大きいか、空白を残しています。 つまり、自動プログラミング自体がより信頼性の高い開発方法論であるという事実にもかかわらず、信頼性の向上については言及していません。

IAR社がvisualStateオートマトンのグラフィックプログラミングの道を進んだことは驚くことではありません。プログラミングの自動テキストベースのプログラミングスタイルは人向けではないことを考慮してください。

リストのバリアント1は、受け入れられた状態操作モードの概念によって拡張されている場合、変更の可能性の点ではるかに有益であると思われます。

各状態の入力信号ハンドラー（外部スイッチ）を個別の関数（関数モード）に配置します。

 uint State_1 (uint &State, uint Input) { {,     ,   }; switch (Input) { /////////// case 0: { ,   }; State = 2; Out = 2; break; /////////// case 1: { ,   }; State = 3; Out = 3; break; /////////// case 2: { ,   }; State = 6; Out = 6; break; /////////// case mStep: //    }; uint State_2 (uint &State, uint Input){...}; 

 typedef uint (*paState)(uint &State, uint Input); paState States[6] = { { State_1, ..., State_6}, }; uint Engine(uint Input = mStep) { static uint State = 3; return(States [State] (State, Input)); } 

オプション3と一見類似しているため、これは、一連の変更モードとしてのプログラマーの概念とより一致しています。 各状態関数はモード関数であり、それ自体が必要なすべての周辺機器、または周辺機器からの同期データフレームをポーリングし、入力文字だけでなくこれに基づいて遷移します。

入力シンボルには、すべてのプログラムに対して同じタイプのシステムメッセージが含まれる場合があります。 これは、特に、状態関数自体を従来の最も馴染みのある方法で記述できることを意味します。

このオプションは、 内部状態変数の各値がこの状態を処理する関数に一意に関連付けられているため、 オプション1よりも優れたパフォーマンスを示し、状態関数を呼び出すと、目的の関数へのポインター。 同時に、 オプション1を実装する場合 、 内部状態変数は状態番号に対応する値と繰り返し比較されます。

このオプションは高速ですが、ルーチンの量は減りません。 この実装の主な欠点は、状態テーブルを持ち、ヘッダーとコードファイルに状態の並列記録を保持する必要があり、いわば、二重記述の問題をコピー/貼り付けしないことです。 ただし、この問題は非常に簡単に解決されます。指定された例を変更します。定数テーブル内のポインターのインデックスである内部状態変数の代​​わりに、それ自体が状態関数へのポインターである内部状態変数を使用できます。

 typedef uint (*paState)( void * argState, uint Input); uint State_1 (paState * State, uint Input) { {,     ,   }; switch (Input) { /////////// case 0: { ,   }; State = (paState*) State_2; Out = 2; break; /////////// case 1: { ,   }; State = (paState*) State_3; Out = 3; break; /////////// case 2: { ,   }; State = (paState*) State_6; Out = 6; break; /////////// case mStep: //    }; uint State_2 (paState *State, uint Input){...}; uint Engine(uint Input = mStep) { static paState *State = (paState*) State_3; return(State(State, Input)); } 

 if(IO_latch->Data_1_received && IO_latch->Permission) { State = 5; } 

6. .

このソリューションの唯一の欠点は、マシンが作業を開始すると、ストール状態に切り替わるまでマシン内に残ることです。ディスプレイの場合、これは歓迎されますが、オートマタのコミュニティとして実装されたシステムの機能プログラム図7は、この方法で機能する能力がない場合があります。この場合、例6のように、各状態は個別の関数によって記述される必要があります。プログラムコードの実装の便宜上、遷移はマクロによって実行されます。

 typedef uint (*paState)( void * argState, uint Input); #define mGoto(argState,argOut){\ State = (paState*)argState;\ return(argOut);\ } #define mStall_code ( (uword)(-1) ) #define mStall(){\ return(mStall_code);\ } //   uint Engine(paState *State, uint Input = mStep) { return(State(State, Input)); } 

 paState *Display_state; void tDisplay::Out_text (int arg_x0, int arg_y0, int arg_x1, int arg_y1, int arg_x_shift, int arg_y_shift, unsigned char * argText, TMemo * argDebug) { //  Display_state = (paState*) state__Inside_text_block; //  while(Engine (Display_state, 0) != mStall_code); return; }//void tDisplay::Out_text (int arg_x0, int arg_y0, //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// uint state__Inside_text_block(paState * State, uint Input) { if(Input == mForce_Out_text_block) mGoto(state__Out_text_block, 0); while(1) { switch(*Text_end) { case '\0': case '\n': mGoto(state__Out_text_block, 0); } Text_end++; } }// uint state__Inside_text_block(paState * State, uint Input) //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// uint state__Out_text_block(paState * State, uint Input) { if(Text != Text_end) { //    . Out_text_block(); //   Execute_script  Line_width     x_rel += Line_width; } //    Text = Text_end; mGoto(state__Control_processing, 0); }// uint state__Out_text_block(paState * State, uint Input) //////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////// uint state__Control_processing(paState * State, uint Input) { if(*Text_begin == 0) { mStall(); } //  esc  mGoto(state__Control_processing, 0); } 

説明されているシンプルなAPIは非常に便利で非常に機能的です。これを使用して、例4を変更すると、次のようになります。エンジンはオプション4と同じです。

 uint State_1 (paState * State, uint Input) { {,     ,   }; switch (Input) { /////////// case 0: { ,   }; mGoto(State_2,2); /////////// case 1: { ,   }; mGoto(State_3,3); /////////// case 2: { ,   }; mGoto(State_6,6); /////////// case mStep: //   . return (0); }; 

シンボリックソフトウェアマシンを実装する方法。

 uint FSM[States_amount][Alphabet_size]; 

 uint FSM[States_amount][Alphabet_size]; uint Engine(uint Input) { static uint State = 0; State = FSM[State][Index_for(Input)]; if(State == (uint)(-1)) { State = 0; return 1; } else return 0; } //     while(!terminate) { if(Engine(Stream++)) goto Found; }; Stopped: //   ,    Found: //   }