レベル: 初級 David Mertz (mertz@gnosis.cx), President, Gnosis Software, Inc.
2000年 8月 01日 ステート・マシンは、理論的な意味では、コンピューターおよびプログラミングに関連するほとんどすべてのものの基礎になっています。また、実用的な意味では、ステート・マシンは (特に、Python プログラマーにとって) 多くの通常の問題の解決に役立ちます。David Mertz はこの記事で、ステート・マシンをいつ、どのように Python で書くのかについて、いくつかの実践的な例を挙げて説明しています。
Python とは何か?
このコラムに寄稿した私の最初の記事で書いたように、Python は、Guido van Rossum によって開発された、フリーの高水準インタープリター言語です。分かりやすい構文と、強力な (ただし、オプションの) オブジェクト指向セマンティクスが組み合わされています。Python は、使用範囲が広く、きわめて移植しやすい言語です。
ステート・マシンとは何か?
正確に言うと、ステート・マシンは、ノードの集まりと、それに対応する変換機能の集まりからなる、有向グラフということになります。このマシンは、一連のイベントに応答して「実行」されます。各イベントは、「現行」ノードに属する変換機能のドメインで発生し、現行ノードにおける機能の範囲は、そのノードのサブセットになります。この機能は「次の」 (おそらくは同一の) ノードを戻します。これらのノードのうち、少なくとも 1 つは終端状態になっていなければなりません。終端状態に到達すると、マシンは停止します。
しかし、(ここで述べたような) 抽象的で数学的な説明では、ステート・マシンが実際のプログラミングの問題にどのように役立つのか、本当には分かりません。別の方法として、ステート・マシンを、ソース行としてノードも含むような命令的なプログラム言語として定義するやり方があります。この定義は、正確ではありますが、実践的な観点からは、最初の定義と同じように形式的で、役に立たないものです (この条件は、Haskell、Scheme、または Prolog などのような、宣言、関数、または制約ベースの言語には必ずしも当てはまりません)。
私たちにとって身近な、実際の仕事にもう少し適した例を使ってみましょう。どの正規表現も論理的にはステート・マシンと同等であり、それぞれの正規表現の構文解析プログラムは、ステート・マシンをインプリメントします。つまり、ほとんどのプログラマーは、実際には意識していなくても、ステート・マシンを作成しているわけです。
次の例を見ながら、ステート・マシンの実際的な定義をヒューリスティックに探して見ましょう。私たちは多くの場合、有限な集合のイベントに対応するために、特定の決まった方法を用意しています。応答がイベント自体にだけ依存することもありますが、先行するイベントに応じて適切な処置が取られることもあります。
この記事で採り上げるステート・マシンは、ある種の問題に対するプログラミング・ソリューションを示すための、高水準マシンです。読者のプログラミングの問題が、イベントに対応した振る舞いという種類のものである場合には、明示的なステート・マシンによってその問題が解決されるのではないかと思われます。
テキスト処理用ステート・マシン
明示的なステート・マシンが必要となる可能性が最も高いプログラミング問題の 1 つとして、テキスト・ファイルの処理があります。テキスト・ファイルの処理は、多くの場合、1 つの単位の情報 (典型的には 1 文字または 1 行) を連続して読み取り、読み取った単位に応じて何かを行うことからなります。場合によっては、この処理は「ステートレス」で行われます (つまり、このようなそれぞれの単位に、行うべきことを正確に判別するのに十分な情報が含まれています)。また、それ以外の場合には、テキスト・ファイルが完全にはステートレスでなくても、データのコンテキストは限定されたものになります (たとえば、処置が、行番号以外の情報には依存しないこともあります)。ただし、その他の共通テキスト処理問題では、入力ファイルはきわめて「ステートフル」です。各データの意味は、その前のデータに (そして、場合によっては後に続くデータにも) 依存します。レポート、メインフレームのデータ・フィード、人が読むことのできるテキスト、プログラミング・ソース・ファイル、およびそれ以外の種類のテキスト・ファイルは、ステートフルです。簡単な例として、Python ソース・ファイルに含まれる次のような行があります。
myObject = SomeClass(this, that, other) |
この行は、次のような行で囲まれていると、違った意味になります。
"""How to use SomeClass:
myObject = SomeClass(this, that, other)
""" |
この行が Python 処置ではなくコメントの一部であることを判別するためには、「ブロック引用」状態になっていることを知る必要があります。
ステート・マシンを使うべきでないとき
なんらかのステートフル・テキスト・ファイル用の処理プログラムを書き始めるときには、そのファイルから見つかると思われる入力項目のタイプを予想してください。各タイプの入力項目は、状態の候補となります。これらのタイプは、数種類である必要があります。この数が膨大であったり、不確定であったりするときには、おそらく、ステート・マシンを使うことは適切な手段ではありません (このような場合には、なんらかのデータベース・ソリューションのほうが適切であると思われます)。
また、そもそもステート・マシンが必要かどうかも考慮してください。より簡単な方法で開始したほうが良い場合も多いのです。テキスト・ファイルがステートフルであっても、それをいくつかの大きい塊で (それぞれの塊は、単一タイプの入力値になります) 読むことが簡単にできることがあります。テキストのタイプを変換するために、単一のステート・ブロック内の内容に基づいてなんらかの計算を行う必要がある場合には、ステート・マシンは本当に、インプリメントする価値のある唯一の方法になります。
次の単純な例は、ステート・マシンが必要になる場合を示しています。数値のリストをいくつかのブロックに分ける 2 本のけい線について考えてください。最初のけい線の下では、リスト内のゼロは、ブロック間の切れ目を表しています。2 本目のけい線の下では、ブロック内の要素の和が 100 を超えると、ブロック間に切れ目が入ります。しきい値に達したかどうかを判別するためにはアキュムレーター変数が使用されるため、サブリスト境界を「一目で」見ることはできません。したがって、2 本目のけい線のほうが、ステート・マシンらしきものの候補として適しています。
ある程度ステートフルであるにもかかわらず、ステート・マシンで処理するのが最適ではなさ そうなテキスト・ファイルの例として、Windows スタイルの .ini ファイルがあります。このファイルは、セクション・ヘッダー、コメント、および多数の値割り当てからなります。たとえば、次のとおりです。
; set the colorscheme and userlevel
[colorscheme]
background=red
foreground=blue
title=green
[userlevel]
login=2
title=1 |
この例には、実用的な意味はありませんが、.ini 形式の興味深い機能がいくつか示されています。
- その 1 つの理由は、各行のタイプが最初の文字 (セミコロン、左括弧、または英字) によって判別されるためです。
- もう 1 つの理由は、各セクション内で使用されている "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)
|
ステート・マシンを使うとき
テキスト・ファイルが「単純すぎる」場合にはステート・マシンを使用しないと決めましたので、ステート・マシンを使用する価値がある場合について考えてみましょう。このコラムの私の前回の記事では、Txt2Html について話しました。これは「スマート ASCII」ファイル (この記事もそれに該当します) を HTML に変換するものです。もう一度まとめて見ましょう。
「スマート ASCII」は、ヘッダー、通常のテキスト、引用符、およびコード・サンプルなどのテキスト・ブロックのタイプを区別するために、少数のスペーシング規則を使用するテキスト形式です。人間がテキストを読み書きする場合、こうしたテキスト・ブロック・タイプ間の変換は目で見て簡単に解析できますが、コンピューターでスマート ASCII ファイルをその構成要素テキスト・ブロックに分割するとなると、簡単にはいきません。.ini ファイルの例とは異なり、テキスト・ブロック・タイプはどのような順序になるか分かりません。すべての場合にブロックを分離するような単一の区切り文字はありません (ブランク行は、通常は ブロックを分離しますが、コード・サンプル内のブランク行は、必ずしもコード・サンプルを終わらせるわけではなく、またブロックが必ずしもブランク行で分離されるとは限りません)。正しい HTML 出力を得るためには、各テキスト・ブロック・タイプをそれぞれ異なる方法でフォーマットし直す必要があるため、ステート・マシンは格好のソリューションと思われます。
Txt2Html リーダーの一般的な振る舞いは、次のとおりです。
- 初期状態で開始する。
- 1 行分の入力を読み取る。
- 入力および現行状態に応じて、新しい状態への変換を行うか、現行状態に適したようにその行を処理する。
この例は、読者が遭遇する最も単純な事例を想定していますが、私が説明した以下のパターンを説明しています。
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
|
このコードを含むソース・ファイルは、Txt2Html とともにダウンロードすることができます (参考文献を参照)。変数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 クラスを実際に使用 するためには、使用したい状態ごとにいくつかのハンドラーを作成する必要があります。ハンドラーは、1 つのパターンに従っていなければなりません。ハンドラーは、別の状態に変換する必要が生じるまでイベントをループし、処理します。イベントを別の状態に変換することが必要になったときには、ハンドラーは、新しい状態の名前と、新しいステート・ハンドラー (状態ハンドラー) のために必要になるカーゴ (cargo) からなる、タプル (tuple) を戻します。
StateMachine クラスでcargo を変数として使用すると、ステート・ハンドラーで必要とされるデータがカプセル化されます (ステート・ハンドラーは、必ずしもその引数cargo を呼び出すとは限りません)。ステート・ハンドラーはcargo を使用して、次のハンドラーに必要なものを渡し、最後のハンドラーが終了した個所から新規ハンドラーが引き継ぎを行えるようにします。cargo は、一般的にはファイル・ハンドルを含んでいるため、最後のハンドラーが停止した個所以降にあるデータを、次のハンドラーが読み取れるようになります。cargo は、データベース接続、複合クラス・インスタンス または複数の項目を含むリストである場合もあります。
さて、ここでテスト・サンプルを見て見ましょう。このケースでは (以下のコード例で概要が示されているように)、カーゴは、常に反復関数にフィードバックされ続ける数値です。次のval の値は、val が特定の範囲内に収まっているかぎり、常に単純なmath_func(val) です。関数がその範囲外の値を戻した場合、その値が別のハンドラーに渡されるか、ステート・マシンが、何もしない end-state ハンドラーを呼び出した後も存在するかのいずれかになります。この例で説明されていることの 1 つは、イベント が必ずしも入力イベントではないということです。計算に関するイベントであってもかまいません (変則的です)。ステート・ハンドラーが相互に異なる点は、扱うイベントを出力するときに異なるマーカーを使用するということだけです。この関数は、比較的ささいな関数で、ステート・マシンの使用を必要としません。しかし、概念はよく示されています。おそらく、コードを見たほうが説明を読むよりも分かりやすいと思われます。
ファイル: 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)
|
参考文献
著者について  | | | David Mertz が、多岐にわたる経歴の中で、自分に与えられた役割を超える貢献をしてきたことは、あまねく知られています。その多くは、アカデミックな「ポストモダン」哲学の分野で行なわれています (しかし一方では、この記事も複数レベルの記述的「地位」を占めています)。David にはmertz@gnosis.cx で連絡することができ、また彼が熱心に研究している対象は、http://gnosis.cx/publish/ でうかがうことができます。このコラムに限らず、過去または将来のコラムに関するご意見やご希望も歓迎するそうです。 |
記事の評価
| 
