ステータスマシンの概念とPythonでステータスマシンを使用するチュートリアル
12341 ワード
ステータスマシンとは?
ステートマシンに関する極めて正確な記述は、ノードのセットと対応する転送関数のセットからなる有向グラフィックである.ステートマシンは、一連のイベントに応答して「実行」します.各イベントは、現在のノードに属する転送関数の制御範囲内にあり、関数の範囲はノードのサブセットです.関数は、「次」ノード(同じかもしれない)を返します.これらのノードの少なくとも1つは最終状態でなければなりません.最終状態に達すると、ステータスマシンは停止します.
抽象的な数学の説明は(私が提示したように)ステートマシンを使用して実際のプログラミング問題を解決する方法は本当に説明できません.もう一つの戦略は、ステートマシンを強制的なプログラミング言語として定義することです.ノードもソースコード行です.実用的な観点から見ると、この定義は正確ですが、最初の説明と同じように、紙上の談兵であり、実用的ではありません.(説明型、関数型、または制約ベースの言語、たとえばHaskell、Scheme、Prologでは、必ずしもそうではありません.)
身近な実際のタスクに適した例を用いて議論してみましょう.論理的には、各ルール式は1つのステータスマシンに等価であり、各ルール式の構文解析器はこのステータスマシンを実現する.実際、多くのプログラマーはステータスマシンを作成する際に、本当にそれを考慮していません.
以下の例では,ステートマシンの真の探索的定義を検討する.通常、有限数のイベントのセットに応答するいくつかの異なる方法があります.場合によっては、応答はイベント自体に依存します.しかし、他の場合、適切な操作は、以前のイベントに依存する.
本論文で論じたステートマシンは,問題のプログラミングソリューションを実証するための高度なマシンである.応答イベントの動作のカテゴリ別にプログラミングの問題を議論する必要がある場合は、ソリューションが明示的なステータスマシンである可能性があります.
テキスト処理ステータスマシン
明示的なステートマシンを呼び出す可能性が最も高いプログラミングの問題は、テキストファイルの処理に関連しています.テキストファイルの処理には、通常、文字または行と呼ばれる情報ユニットを読み出し、読み出したばかりのユニットに対して適切な操作を実行します.場合によっては、この処理は「ステータスなし」です.(つまり、各ユニットには十分な情報が含まれており、どの操作を実行するかを正確に判断できます).他の場合、テキストファイルが完全に無状態ではない場合でも、データには限られたコンテキストしかありません(たとえば、操作は行番号よりも多くの情報に依存します).しかし、他の一般的なテキスト処理の問題では、入力ファイルは非常に「状態」です.のです.各データの意味は、その前の文字列(その後ろの文字列かもしれません)によって異なります.レポート、メインフレームデータ入力、読み取り可能テキスト、プログラミングソースファイル、その他の種類のテキストファイルにはステータスがあります.簡単な例は、Pythonソースに表示されるコードの行です.
この行は、次の行がこの行を囲んでいる場合、一部の内容が異なることを示します.
Python操作ではなく、この行のコードが注釈の一部であることを確認するために「ブロック参照」状態にあることを知っておく必要があります.
ステートマシンを使用しない場合
ステータスのあるテキストファイルのプロセッサを作成するタスクを開始すると、ファイルにどのタイプの入力項目を見つけたいかを自分に聞いてみましょう.各タイプの入力項目は、ステータスの候補です.これらのタイプは全部でいくつかあります.数字が大きいか不確定であれば、ステータスマシンは正しい解決方法ではないかもしれません.(この場合、一部のデータベース・ソリューションがより適切である可能性があります.)
ステートマシンを使用する必要があるかどうかも考慮してください.多くの場合、より簡単な方法から始めたほうがいいです.テキストファイルにステータスがある場合でも、ブロックに分けて読み取る簡単な方法があるかもしれません(各ブロックは入力値のタイプです).実際には、単一のステータスブロックでは、テキストタイプ間の転送がコンテンツベースの計算を必要とする場合にのみ、ステータスマシンを実装する必要があります.
以下の簡単な例では、ステートマシンを使用する必要がある場合を説明します.1列の数字をいくつかのブロックに分割するための2つのルールを考慮してください.最初のルールでは、リスト内のゼロはブロック間の間欠を表します.2番目のルールでは、1つのブロックの要素の合計が100を超えると、ブロック間の間欠が発生します.アキュムレータ変数を使用してしきい値に達したかどうかを決定するため、サブリストの境界を「すぐに」見ることはできません.従って、第2のルールは、ステータスマシンに類似したメカニズムに適しているかもしれない.
少し状態があるが、ステートマシンで処理するのにあまり適していないテキストファイルの例はWindowsスタイルである.iniファイル.このファイルには、ヘッダー、コメント、および多くの付与値が含まれます.例:
私たちの例には実際の意味はありませんが、それは示しています.iniフォーマットのいくつかの面白い特性.
ある意味では、各行のタイプは、その最初の文字(セミコロン、左カッコ、またはアルファベット)によって決定されます.別の角度から見ると、キーワード「title」は、各セクションに表示される場合、独立したコンテンツがあることを意味するため、このフォーマットは「ステータスあり」です.
COLORSCHEMEステータスとUSERLEVELステータスを持つテキストプロセッサプログラムを作成できます.このプログラムは各ステータスの付与値を処理します.しかし、これはこの問題を処理する正しい方法ではないようだ.例えば、Pythonコードを使用して、このテキストファイルに自然ブロックのみを作成することができる、例えば、処理.INIファイルのブロックPythonコード
または、必要に応じて、単一のcurrent_を使用できます.section変数による位置決定:処理.INIファイルの計算Pythonコード
ステートマシンの使用方法
ここで,テキストファイルが「単純すぎる」場合にステートマシンを使用しないことを決定し,ステートマシンを使用する必要がある場合について検討する.このコラムでは最近、「スマートASCII」(本明細書を含む)をHTMLに変換するユーティリティTxt 2 Htmlについて説明しています.
インテリジェントASCIIは、ヘッダー、一般テキスト、引用語、コードサンプルなどのテキストブロックのタイプを区別するためにいくつかの間隔規則を使用するテキストフォーマットです.読者または著者は、これらのテキストブロックタイプ間の遷移を容易に表示分析することができるが、コンピュータが「スマートASCII」ファイルをそのテキストブロックを構成するように分割する簡単な方法はない.似ていませんiniファイルの例では、テキストブロックタイプは任意の順序で表示できます.いずれの場合もブロックを区切る単一のデリミタはありません(空白行は通常テキストブロックを区切るが、コードサンプルの空白行は必ずしもコードサンプルを終了する必要はなく、テキストブロックは空白行で区切る必要はありません).各テキストブロックを異なる方法で再フォーマットして正しいHTML出力を生成する必要があるため、ステータスマシンは自然な解決策のようです.
Txt 2 Htmlリーダーの一般的な機能は以下の通りです.が初期状態で起動します. は、1行の入力を読み込みます. は、入力および現在の状態に従って、新しい状態に遷移するか、または現在の状態に適合するように行を処理する.
この例では、最も簡単な状況について説明しますが、Pythonの簡単なステータスマシン入力サイクルについて説明します.
Txt 2 Htmlを使用して、コードを取り出したソースファイルをダウンロードできます(参考資料を参照).変数stateはglobalとして宣言され、startText()などの関数で値を変更します.転送条件、例えばtextln.match()は、ルール式モードですが、カスタム関数でもある可能性があります.実際には、後でプログラムでフォーマットが実行されます.ステータスマシンは、テキストファイルのみをblocksリストのラベル付きブロックに解析します.
抽象ステートマシンクラス
フォームや関数でPythonを使って抽象ステートマシンを実現するのは簡単です.これにより、プログラムのステートマシンモデルは、前の例の単純な条件ブロックよりも際立って見えます(最初は、その条件は他の条件と何の違いもありません).また、以下のクラスとその関連処理プログラムは、分離状態での操作が良好に行われます.多くの場合、パッケージと読み取りが改善されます.ファイル:statemachine.py
StateMachineクラスは実際には抽象ステートマシンに必要なものです.Pythonを使用して関数オブジェクトを渡すのは簡単なので、他の言語の類似クラスと比較して、このクラスに必要な行数は非常に少ないです.
StateMachineクラスを実際に使用するには、使用するステータスごとにプロセッサを作成する必要があります.プロセッサはモードに一致する必要があります.イベントを別のステータスに移行するまでループ処理します.この場合、プロセッサは、新しいステータス名と、新しいステータスハンドラに必要なcargoを含むバイトグループを返す必要があります.
StateMachineクラスでcargoを変数として使用する方法ステータスハンドラに必要なデータをカプセル化(このステータスハンドラは、そのcargo変数を呼び出す必要はありません).ステータスハンドラは、cargoを使用して次のハンドラに必要な内容を伝達し、新しいハンドラは前のハンドラの残留作業を引き継ぐことができます.cargoは通常、次のハンドラが前のハンドラが停止した後により多くのデータを読み取ることができるファイルハンドルを含みます.cargoはまた、データベース接続、複雑なクラスインスタンス、またはいくつかのアイテムのリストである可能性があります.
次に、テストサンプルを検討しましょう.この例では(以下のコード例で概説する)、cargoは反復関数にフィードバックを絶えず送信する数値にすぎない.valがある範囲内にある限り、valの次の値はmath_func(val)にすぎない.関数が範囲外の値を返すと、その値は別のプロセッサに転送されるか、ステータスマシンが何もしないエンドプロセッサを呼び出した後に終了します.例では、イベントが入力イベントである必要はありません.計算イベント(この場合は少ない)でも構いません.ステータスハンドラの違いは、処理されたイベントを出力するときに異なるタグを使用するだけです.この関数は比較的簡単で、ステータスマシンを使用する必要はありません.しかし、概念をよく説明しています.コードは説明よりも理解しやすいかもしれません!ファイル:statemachine_test.py
ステートマシンに関する極めて正確な記述は、ノードのセットと対応する転送関数のセットからなる有向グラフィックである.ステートマシンは、一連のイベントに応答して「実行」します.各イベントは、現在のノードに属する転送関数の制御範囲内にあり、関数の範囲はノードのサブセットです.関数は、「次」ノード(同じかもしれない)を返します.これらのノードの少なくとも1つは最終状態でなければなりません.最終状態に達すると、ステータスマシンは停止します.
抽象的な数学の説明は(私が提示したように)ステートマシンを使用して実際のプログラミング問題を解決する方法は本当に説明できません.もう一つの戦略は、ステートマシンを強制的なプログラミング言語として定義することです.ノードもソースコード行です.実用的な観点から見ると、この定義は正確ですが、最初の説明と同じように、紙上の談兵であり、実用的ではありません.(説明型、関数型、または制約ベースの言語、たとえばHaskell、Scheme、Prologでは、必ずしもそうではありません.)
身近な実際のタスクに適した例を用いて議論してみましょう.論理的には、各ルール式は1つのステータスマシンに等価であり、各ルール式の構文解析器はこのステータスマシンを実現する.実際、多くのプログラマーはステータスマシンを作成する際に、本当にそれを考慮していません.
以下の例では,ステートマシンの真の探索的定義を検討する.通常、有限数のイベントのセットに応答するいくつかの異なる方法があります.場合によっては、応答はイベント自体に依存します.しかし、他の場合、適切な操作は、以前のイベントに依存する.
本論文で論じたステートマシンは,問題のプログラミングソリューションを実証するための高度なマシンである.応答イベントの動作のカテゴリ別にプログラミングの問題を議論する必要がある場合は、ソリューションが明示的なステータスマシンである可能性があります.
テキスト処理ステータスマシン
明示的なステートマシンを呼び出す可能性が最も高いプログラミングの問題は、テキストファイルの処理に関連しています.テキストファイルの処理には、通常、文字または行と呼ばれる情報ユニットを読み出し、読み出したばかりのユニットに対して適切な操作を実行します.場合によっては、この処理は「ステータスなし」です.(つまり、各ユニットには十分な情報が含まれており、どの操作を実行するかを正確に判断できます).他の場合、テキストファイルが完全に無状態ではない場合でも、データには限られたコンテキストしかありません(たとえば、操作は行番号よりも多くの情報に依存します).しかし、他の一般的なテキスト処理の問題では、入力ファイルは非常に「状態」です.のです.各データの意味は、その前の文字列(その後ろの文字列かもしれません)によって異なります.レポート、メインフレームデータ入力、読み取り可能テキスト、プログラミングソースファイル、その他の種類のテキストファイルにはステータスがあります.簡単な例は、Pythonソースに表示されるコードの行です.
myObject = SomeClass(this, that, other)
この行は、次の行がこの行を囲んでいる場合、一部の内容が異なることを示します.
"""How to use SomeClass:
myObject = SomeClass(this, that, other)
"""
Python操作ではなく、この行のコードが注釈の一部であることを確認するために「ブロック参照」状態にあることを知っておく必要があります.
ステートマシンを使用しない場合
ステータスのあるテキストファイルのプロセッサを作成するタスクを開始すると、ファイルにどのタイプの入力項目を見つけたいかを自分に聞いてみましょう.各タイプの入力項目は、ステータスの候補です.これらのタイプは全部でいくつかあります.数字が大きいか不確定であれば、ステータスマシンは正しい解決方法ではないかもしれません.(この場合、一部のデータベース・ソリューションがより適切である可能性があります.)
ステートマシンを使用する必要があるかどうかも考慮してください.多くの場合、より簡単な方法から始めたほうがいいです.テキストファイルにステータスがある場合でも、ブロックに分けて読み取る簡単な方法があるかもしれません(各ブロックは入力値のタイプです).実際には、単一のステータスブロックでは、テキストタイプ間の転送がコンテンツベースの計算を必要とする場合にのみ、ステータスマシンを実装する必要があります.
以下の簡単な例では、ステートマシンを使用する必要がある場合を説明します.1列の数字をいくつかのブロックに分割するための2つのルールを考慮してください.最初のルールでは、リスト内のゼロはブロック間の間欠を表します.2番目のルールでは、1つのブロックの要素の合計が100を超えると、ブロック間の間欠が発生します.アキュムレータ変数を使用してしきい値に達したかどうかを決定するため、サブリストの境界を「すぐに」見ることはできません.従って、第2のルールは、ステータスマシンに類似したメカニズムに適しているかもしれない.
少し状態があるが、ステートマシンで処理するのにあまり適していないテキストファイルの例はWindowsスタイルである.iniファイル.このファイルには、ヘッダー、コメント、および多くの付与値が含まれます.例:
; set the colorscheme and userlevel
[colorscheme]
background=red
foreground=blue
title=green
[userlevel]
login=2
title=1
私たちの例には実際の意味はありませんが、それは示しています.iniフォーマットのいくつかの面白い特性.
ある意味では、各行のタイプは、その最初の文字(セミコロン、左カッコ、またはアルファベット)によって決定されます.別の角度から見ると、キーワード「title」は、各セクションに表示される場合、独立したコンテンツがあることを意味するため、このフォーマットは「ステータスあり」です.
COLORSCHEMEステータスとUSERLEVELステータスを持つテキストプロセッサプログラムを作成できます.このプログラムは各ステータスの付与値を処理します.しかし、これはこの問題を処理する正しい方法ではないようだ.例えば、Pythonコードを使用して、このテキストファイルに自然ブロックのみを作成することができる、例えば、処理.INIファイルのブロックPythonコード
import
string
txt = open(
'hypothetical.ini').read()
sects = string.split(txt,
'[')
for
sect
in
sects:
# do something with sect, like get its name
# (the stuff up to ']') and read its assignments
または、必要に応じて、単一のcurrent_を使用できます.section変数による位置決定:処理.INIファイルの計算Pythonコード
for
line
in
open(
'hypothetical.ini').readlines():
if
line[0] ==
'[':
current_section = line(1:-2)
elif
line[0] ==
';':
pass
# ignore comments
else
:
apply_value(current_section, line)
ステートマシンの使用方法
ここで,テキストファイルが「単純すぎる」場合にステートマシンを使用しないことを決定し,ステートマシンを使用する必要がある場合について検討する.このコラムでは最近、「スマートASCII」(本明細書を含む)をHTMLに変換するユーティリティTxt 2 Htmlについて説明しています.
インテリジェントASCIIは、ヘッダー、一般テキスト、引用語、コードサンプルなどのテキストブロックのタイプを区別するためにいくつかの間隔規則を使用するテキストフォーマットです.読者または著者は、これらのテキストブロックタイプ間の遷移を容易に表示分析することができるが、コンピュータが「スマートASCII」ファイルをそのテキストブロックを構成するように分割する簡単な方法はない.似ていませんiniファイルの例では、テキストブロックタイプは任意の順序で表示できます.いずれの場合もブロックを区切る単一のデリミタはありません(空白行は通常テキストブロックを区切るが、コードサンプルの空白行は必ずしもコードサンプルを終了する必要はなく、テキストブロックは空白行で区切る必要はありません).各テキストブロックを異なる方法で再フォーマットして正しいHTML出力を生成する必要があるため、ステータスマシンは自然な解決策のようです.
Txt 2 Htmlリーダーの一般的な機能は以下の通りです.
この例では、最も簡単な状況について説明しますが、Pythonの簡単なステータスマシン入力サイクルについて説明します.
global
state, blocks, bl_num, newblock
#-- Initialize the globals
state = "HEADER"
blocks = [""]
bl_num = 0
newblock = 1
for
line
in
fhin.readlines():
if
state ==
"HEADER":
# blank line means new block of header
if
blankln.match(line): newblock = 1
elif
textln.match(line): startText(line)
elif
codeln.match(line): startCode(line)
else
:
if
newblock: startHead(line)
else
: blocks[bl_num] = blocks[bl_num] + line
elif
state ==
"TEXT":
# blank line means new block of text
if
blankln.match(line): newblock = 1
elif
headln.match(line): startHead(line)
elif
codeln.match(line): startCode(line)
else
:
if
newblock: startText(line)
else
: blocks[bl_num] = blocks[bl_num] + line
elif
state ==
"CODE":
# blank line does not change state
if
blankln.match(line): blocks[bl_num] = blocks[bl_num] + line
elif
headln.match(line): startHead(line)
elif
textln.match(line): startText(line)
else
: blocks[bl_num] = blocks[bl_num] + line
else
:
raise
ValueError,
"unexpected input block state: "+state
Txt 2 Htmlを使用して、コードを取り出したソースファイルをダウンロードできます(参考資料を参照).変数stateはglobalとして宣言され、startText()などの関数で値を変更します.転送条件、例えばtextln.match()は、ルール式モードですが、カスタム関数でもある可能性があります.実際には、後でプログラムでフォーマットが実行されます.ステータスマシンは、テキストファイルのみをblocksリストのラベル付きブロックに解析します.
抽象ステートマシンクラス
フォームや関数でPythonを使って抽象ステートマシンを実現するのは簡単です.これにより、プログラムのステートマシンモデルは、前の例の単純な条件ブロックよりも際立って見えます(最初は、その条件は他の条件と何の違いもありません).また、以下のクラスとその関連処理プログラムは、分離状態での操作が良好に行われます.多くの場合、パッケージと読み取りが改善されます.ファイル:statemachine.py
from
string
import
upper
class
StateMachine
:
def
__init__
(self):
self.handlers = {}
self.startState = None
self.endStates = []
def
add_state
(self, name, handler, end_state=0):
name = upper(name)
self.handlers[name] = handler
if
end_state:
self.endStates.append(name)
def
set_start
(self, name):
self.startState = upper(name)
def
run
(self, cargo):
try
:
handler = self.handlers[self.startState]
except
:
raise
"InitializationError",
"must call .set_start() before .run()"
if
not
self.endStates:
raise
"InitializationError",
"at least one state must be an end_state"
while
1:
(newState, cargo) = handler(cargo)
if
upper(newState)
in
self.endStates:
break
else
:
handler = self.handlers[upper(newState)]
StateMachineクラスは実際には抽象ステートマシンに必要なものです.Pythonを使用して関数オブジェクトを渡すのは簡単なので、他の言語の類似クラスと比較して、このクラスに必要な行数は非常に少ないです.
StateMachineクラスを実際に使用するには、使用するステータスごとにプロセッサを作成する必要があります.プロセッサはモードに一致する必要があります.イベントを別のステータスに移行するまでループ処理します.この場合、プロセッサは、新しいステータス名と、新しいステータスハンドラに必要なcargoを含むバイトグループを返す必要があります.
StateMachineクラスでcargoを変数として使用する方法ステータスハンドラに必要なデータをカプセル化(このステータスハンドラは、そのcargo変数を呼び出す必要はありません).ステータスハンドラは、cargoを使用して次のハンドラに必要な内容を伝達し、新しいハンドラは前のハンドラの残留作業を引き継ぐことができます.cargoは通常、次のハンドラが前のハンドラが停止した後により多くのデータを読み取ることができるファイルハンドルを含みます.cargoはまた、データベース接続、複雑なクラスインスタンス、またはいくつかのアイテムのリストである可能性があります.
次に、テストサンプルを検討しましょう.この例では(以下のコード例で概説する)、cargoは反復関数にフィードバックを絶えず送信する数値にすぎない.valがある範囲内にある限り、valの次の値はmath_func(val)にすぎない.関数が範囲外の値を返すと、その値は別のプロセッサに転送されるか、ステータスマシンが何もしないエンドプロセッサを呼び出した後に終了します.例では、イベントが入力イベントである必要はありません.計算イベント(この場合は少ない)でも構いません.ステータスハンドラの違いは、処理されたイベントを出力するときに異なるタグを使用するだけです.この関数は比較的簡単で、ステータスマシンを使用する必要はありません.しかし、概念をよく説明しています.コードは説明よりも理解しやすいかもしれません!ファイル:statemachine_test.py
from
statemachine
import
StateMachine
def
ones_counter
(val):
print
"ONES State: ",
while
1:
if
val <= 0
or
val >= 30:
newState =
"Out_of_Range" ;
break
elif
20 <= val < 30:
newState =
"TWENTIES";
break
elif
10 <= val < 20:
newState =
"TENS";
break
else
:
print
" @ %2.1f+" % val,
val = math_func(val)
print
" >>"
return
(newState, val)
def
tens_counter
(val):
print
"TENS State: ",
while
1:
if
val <= 0
or
val >= 30:
newState =
"Out_of_Range";
break
elif
1 <= val < 10:
newState =
"ONES";
break
elif
20 <= val < 30:
newState =
"TWENTIES";
break
else
:
print
" #%2.1f+" % val,
val = math_func(val)
print
" >>"
return
(newState, val)
def
twenties_counter
(val):
print
"TWENTIES State:",
while
1:
if
val <= 0
or
val >= 30:
newState =
"Out_of_Range";
break
elif
1 <= val < 10:
newState =
"ONES";
break
elif
10 <= val < 20:
newState =
"TENS";
break
else
:
print
" *%2.1f+" % val,
val = math_func(val)
print
" >>"
return
(newState, val)
def
math_func
(n):
from
math
import
sin
return
abs(sin(n))*31
if
__name__==
"__main__":
m = StateMachine()
m.add_state(
"ONES", ones_counter)
m.add_state(
"TENS", tens_counter)
m.add_state(
"TWENTIES", twenties_counter)
m.add_state(
"OUT_OF_RANGE", None, end_state=1)
m.set_start(
"ONES")
m.run(1)