魅力的なPython: ジェネレーターによるステート・マシン

ジェネレーターによるステート・マシンとコルーチンで効率を高める

Python 2.2に導入されたシンプルなジェネレーターを利用すれば、ステート・マシンを単純化したり、コルーチンをシミュレートすることができます。Davidは、以前に「魅力的なPython」の連載記事でステート・マシン処理のための抽象パターンについて寄稿しています。その後、シンプル・ジェネレーターが導入され、マシンを記述するための、もっと自然なパラダイムがいろいろと提供されてきています。コルーチンは、ほとんどの一般的な言語では (非Stackless Pythonですら) 採用されていない「風変わりな (exotic)」フロー・メカニズムです。しかしながら、Pythonの新しいジェネレーターは、ほとんど完全にコルーチンの環境を作り出しており、いくつかの余計な手順も隠ぺいできるようにしています。本稿では、Davidが、分かりやすいサンプル・コードを紹介しながら、関係する概念をすべて解説してくれます。

[手違いにより、この記事の発行の順番が違ってしまいました。本来なら、Davidの前回の記事、Pythonジェネレーターで「無重量スレッド」を実装する よりも先に、この記事を発行することになっていました。混乱を招いたこと、お詫び申し上げます。- 編集者]

David Mertz (mertz@gnosis.cx), Producer, Gnosis Software, Inc.

David Mertz photoDavid Mertzは、ニーチェを傍らに、これらが昔の言語学者の思想なのだと書きたいのですが、その嘘は自ずと化けの皮がはがれることでしょう。ただ、おそらく彼の(まさしくここで只で宣伝してもらえる)近刊書Text Processing in Pythonは、いつの日にか、言語学のサイバー版と間違えられることになるのではないでしょうか。Davidのメール・アドレスはmertz@gnosis.cx です。その生活は、http://gnosis.cx/publish/ でじっくり観察できます。今回のコラム、以前のコラム、あるいは今後のコラムについて、ご意見やご提案があればお寄せください。



2002年 7月 01日

Python 2.2の新しいジェネレーターを完全に「理解する」には、少し時間がかかります。「魅力的なPython」の以前の連載記事でシンプル・ジェネレーター入門 を書いた後でも、ジェネレーターの「総体 (gestalt)」を十分に理解しているとはいえない状態でした。本稿では、ジェネレーターの使い方をいくつか補足し、できることなら、私自身も読者も「再開可能な関数 (resumable functions)」の考え方まで理解できるようにしたいと思います。

シンプル・ジェネレーターには、数多くの利点があります。問題となっているクラスのフローを従来よりも自然に表現できるようにすることの他に、ジェネレーターによって、数多くの非効率な点を劇的に改善することができます。Pythonでは、関数呼び出しが、かなり高価なものとなります。中でも、関数の引数リストの展開には時間がかかります (とくに、位置による引数やデフォルト引数は解析する必要があります)。また、フレーム・オブジェクトの初期化には、いろいろなセットアップ手順が必要です (comp.lang.pythonのTim Petersによると、Cで100行以上とのこと。私自身、Pythonのソースを調べたわけではありません)。それに対して、ジェネレーターを再開するのは、かなり安価です。引数は、すでに解析済みですし、フレーム・オブジェクトは、ただ黙って再開を待っているだけです (ほとんど何も特別な初期化は必要ありません)。もちろん、速度が最優先される場合には、バイト・コードにコンパイルされる動的言語を使うべきではありません。といっても、速度が最優先事項でない場合でも、速いに越したことはありませんが。

ステート・マシン再訪

「魅力的なPython」の別の連載記事で、私は、マシンが必要とすればいくらでも状態ハンドラーをユーザーが追加できるようなStateMachine クラス を紹介したことがありました。そのモデルでは、終了状態として1個以上の状態が定義され、開始状態は1個だけ定義されます (クラス・メソッドをいろいろと呼び出すことで、このような構成を設定します)。ハンドラーは、それぞれ、必要な構造体を備えていました。ハンドラーは、一連の処理を行い、その後しばらくしたら、次に進むべき状態を示すフラグを添えてStateMachine.run() メソッド内のループに返るのでした。また、cargo 変数を使用して、ある状態から次の状態に (未処理の) 情報を渡せるようにもしていました。

私が紹介したStateMachine クラスの一般的な使い方は、入力を状態の変遷にしたがって処理するというものでした。たとえば、私が使用しているテキスト処理ツール (Txt2Html) は、ファイルから行単位で読み出しを行います。各行がどんなカテゴリーに属しているかで、その行に応じた処理を行う必要があります。ただし、多くの場合、直前までの行によって与えられるコンテキストをチェックして、現在の行がどのカテゴリーに属しているのか (そして、どのように処理すべきか) を決定する必要があります。この処理をStateMachine クラスを中心に構築して実装するということは、しばらくの間何行かを読み出すA というハンドラーを定義し、その何行かをA 流のやり方で処理するということになるかもしれません。しばらくすると、次の1群の行をB ハンドラーで処理すべきであるという条件が成立します。A は、B 状態に遷移せよという指示を添えて.run() ループに制御を戻します。その際、A では正しく処理できなかった行、すなわちB がさらに行を読み出す前に処理すべき行も渡されます。最後には、あるハンドラーが、終了状態として定義されたどこかの状態に制御を渡すことで、処理が終了します。

以前の記事では、具体的なサンプル・コードとして、簡略化したアプリケーションを示しました。それは、行の処理ではなく、反復関数が生成する一連の数字を処理するというものでした。各状態ハンドラーは、単に、それぞれのハンドラーで任意に設定された範囲に入っている数字 (並びに動作状態に関するメッセージ) を表示するだけでした。数字列の中のある数字が範囲外のものになったら、別のハンドラーがその「処理」を引き継ぎます。今回の記事では、この数字列の処理をジェネレーターを使って (いくつか特別な技や機能も使いながら) 実装することを考えます。ただし、もっと上等なジェネレーターの例を示すとすれば、上の節で触れた入力ストリームのようなものを処理するものになるでしょう。まずは、以前紹介したステート・マシンを、簡略化バージョンのコードで復習することにしましょう。

リスト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)
# ... other handlers ...
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)

インポートされているStateMachine クラスやそのメソッドの動作に興味のある方は、以前の記事を参照してください。


ジェネレーターの利用

ステート・マシンを完全にジェネレーターを使って実装したバージョンは、このコラムで通例紹介するサンプル・コードより少し長いものになりますが、以下のサンプル・コードは、これでアプリケーション全体であり、サポート用に別途statemachine モジュールがインポートされるわけではありません。全体としては、クラスで実装したバージョンよりも短いものになっています (しかも、後で説明しますが、その他の機能もあり非常に強力でもあります)。

リスト2. stategen_test.py
from __future__ import generators
import sys
def math_gen(n):    # Iterative function becomes a generator
    from math import sin
    while 1:
        yield n
        n = abs(sin(n))*31
# Jump targets not state-sensitive, only to simplify example
def jump_to(val):
    if    0 <= val < 10: return 'ONES'
    elif 10 <= val < 20: return 'TENS'
    elif 20 <= val < 30: return 'TWENTIES'
    else:                return 'OUT_OF_RANGE'
def get_ones(iter):
    global cargo
    while 1:
        print "\nONES State:      ",
        while jump_to(cargo)=='ONES':
            print "@ %2.1f  " % cargo,
            cargo = iter.next()
        yield (jump_to(cargo), cargo)
def get_tens(iter):
    global cargo
    while 1:
        print "\nTENS State:      ",
        while jump_to(cargo)=='TENS':
            print "#%2.1f  " % cargo,
            cargo = iter.next()
        yield (jump_to(cargo), cargo)
def get_twenties(iter):
    global cargo
    while 1:
        print "\nTWENTIES State:  ",
        while jump_to(cargo)=='TWENTIES':
            print "*%2.1f  " % cargo,
            cargo = iter.next()
        yield (jump_to(cargo), cargo)
def exit(iter):
    jump = raw_input('\n\n[co-routine for jump?] ').upper()
    print "...Jumping into middle of", jump
    yield (jump, iter.next())
    print "\nExiting from exit()..."
    sys.exit()
def scheduler(gendct, start):
    global cargo
    coroutine = start
    while 1:
        (coroutine, cargo) = gendct[coroutine].next()
if __name__ == "__main__":
    num_stream = math_gen(1)
    cargo = num_stream.next()
    gendct = {'ONES'        : get_ones(num_stream),
              'TENS'        : get_tens(num_stream),
              'TWENTIES'    : get_twenties(num_stream),
              'OUT_OF_RANGE': exit(num_stream)         }
    scheduler(gendct, jump_to(cargo))

ジェネレーターによるステート・マシンについては、語るべきことが数多くあります。まず第一に、全体的に整っているということです。stategen_test.py では、関数だけを使うようにしており、クラスは使用しません (少なくとも私の感じでは、ジェネレーターは、OOP色よりも、関数プログラミング色のほうがずっと強いような気がします)。ただし、必要なら、これと同じ一般的なモデルを何個かのクラスにラップするのはたやすいことです。

このサンプルのメインの関数は、scheduler() であり、完全に汎用的なものになっています (と同時に、以前のパターンのStateMachine クラスよりも、かなり短くなっています)。関数scheduler() は、引数に、ジェネレーター - イテレーター・オブジェクト (「インスタンス化された」ジェネレーター) の辞書を必要とします。各ジェネレーターに付ける文字列名は、任意のものにすることができます。ジェネレーター - ファクトリー関数のリテラル名にするのが、分かりやすい選択ですが、上の例では、キーワードを大文字にしたものとしました。また、scheduler() 関数は、引数に「開始状態」もとりますが、自動的にデフォルト値が選択されるようにすることでもかまわないでしょう。

「スケジュールされた」各ジェネレーターは、いくつか簡単な約束ごとに従います。各ジェネレーターは、しばらくの間実行したら、前回のモデルの場合とまったく同様、次に進みたいジャンプ先となにがしかの「積み荷 (cargo)」の対 (つい) を委譲 (yield) します。どのジェネレーターにも、とくに「終了状態」の印は付けていません。代わりに、それぞれのジェネレーターがエラーを発生できるようにし、scheduler() から抜け出せるようにしています。具体的には、終わりを検出するかreturn 文に到達したジェネレーターは、StopIteration 例外を発生するようになっています。必要なら、この例外 (あるいは別の例外) をキャッチすることもできます。上の例では、exit() ジェネレーターの中で実行されるsys.exit() を使ってアプリケーションを終了しています。

コードについて2点補足しておきます。上のサンプル・コードでは、数字列の生成に、反復関数を使う代わりに、もっとすっきりしたループによるジェネレーター - イテレーターを使用しています。このジェネレーターは、連続的に「最後の値」に戻してもらうのではなく、単に、呼び出されるつど、(無限 / 無期限の) 数字のストリームを発行します。小さな関数ながら、ジェネレーターの機能をうまく説明しています。また、上のコードでは、「状態遷移」表を別個の関数として分離しています。現実のプログラムでは、状態遷移のジャンプは、もっとずっとコンテキストに依存したものになるでしょうし、おそらくジェネレーター本体の中で決定されることになるでしょう。「状態遷移」表を別個の関数として分離することで、上の例は、簡潔なものになっています。どれほど有効なのかはわかりませんが、1個の関数ファクトリーからジェネレーター関数を作成するようにすれば、もっと簡潔なものにできたのかもしれません。ただ一般的には、これが可能になるほど、各ジェネレーター同士が類似しているということはないでしょう。


コルーチンと半コルーチン

注意深い読者なら、最初に告げた内容よりも格段に強力なフロー制御構造を密かに上のコードに導入していることに気付いたことと思います。サンプル・コードでは、1個のステート・マシン以上のものが実行されているのです。上のパターンは、実際には、コルーチン用の一般的なシステムとなっているのです。ほとんどの読者は、ここで少し背景説明が必要なのではないでしょうか。

コルーチンとは、他の制御コンテキストに自由に分岐し、かつ、その分岐点から自由にフローを再開することを可能にするプログラム機能の集まりのことです。ほとんどのプログラミング言語でおなじみのサブルーチンは、一般的なコルーチンの極めて限定された場合であると言えます。サブルーチンは、先頭の固定的な場所からしか開始できず、一度しか終了できません (中途から再開することはできません)。また、サブルーチンは、必ず、呼び出し元にフローを戻します。本質的に、コルーチンは、呼び出し可能な継続 (callable continuation) を表現します。もちろん、新しい単語を出してきても、それを知らない人にとっては必ずしも説明にはならないのですが。Randall Hyde著のThe Art of Assembly にある「2つのプロセス間でのココール・シーケンス (Cocall Sequence Between Two Processes) 」の図は、コルーチンを説明するのに大いに役に立ちます。参考文献に、この図へのリンクを示しておきます。Hydeが行っている全般的な解説へのリンクも参考文献に示してあります。これも役に立ちます。

否定的な意味合いを込めてですが、数多くの言語に用意されている例の悪名高いgoto 文でも自由な分岐が可能であるということができます。もちろん、「スパゲッティ・コード」を助長する、構造化の程度の低いコンテキストでではありますが。

Python 2.2+ のジェネレーターは、コルーチンに向けて、大きな一歩を踏み出しています。すなわち、ジェネレーターは、関数やサブルーチンと違い、再開可能であり、複数回の呼び出しの間で値を委譲することができます。ただし、Pythonのジェネレーターは、Donald Knuthが「半コルーチン (semi-coroutines)」と表現したものにすぎません。ジェネレーターは、再開可能であり、どこか別のところに制御を分岐させることができますが、制御の分岐で可能なのは、直接の呼び出し元に戻すことだけです。正確に言うなら、ジェネレーターのコンテキスト自体は (どんなコンテキストでも同じですが)、他のジェネレーターまたは関数を、あるいは自分自身を再帰的に、呼び出すことができますが、最終的なリターンは、必ず、リターンの相互関係に関して、1つずつ上位に戻らなければなりません。Pythonのジェネレーターは、お互いの途中から自由に再開する「生産者 (Producers)」と「消費者 (Consumers)」というコルーチンの一般的な使い方を許していません。

幸いなことに、本格的なコルーチンは、Pythonのジェネレーターを使えば、いとも簡単にシミュレートできます。からくりは簡単で、まさに上のサンプル・コードにあるようなscheduler() 関数にあります。実際、今回紹介したステート・マシンは、それ自体、もっとずっと一般的なコルーチンのフレームワーク・パターンなのです。このパターンに適合すれば、Pythonジェネレーターに残っている小さな制約も克服できます (不用意なプログラマーも、スパゲッティ・コードの真の力を利用できるようになります)。


Stategenの動作

stategen_test.py が何をやっているのかを調べるには、それを実行してみるのが最も簡単な方法です。

リスト3. STATEGENの実行 (ジャンプ制御は手動)
% python stategen_test.py
ONES State:       @ 1.0
TWENTIES State:   *26.1   *25.3
ONES State:       @ 4.2
TWENTIES State:   *26.4   *29.5   *28.8
TENS State:       #15.2   #16.3   #16.0
ONES State:       @ 9.5   @ 3.8
TENS State:       #18.2   #17.9
TWENTIES State:   *24.4
TENS State:       #19.6
TWENTIES State:   *21.4
TENS State:       #16.1   #12.3
ONES State:       @ 9.2   @ 6.5   @ 5.7
TENS State:       #16.7
TWENTIES State:   *26.4   *30.0
[co-routine for jump?] twenties
 ...Jumping into middle of TWENTIES
TWENTIES State:
TENS State:       #19.9
TWENTIES State:   *26.4   *29.4   *27.5   *22.7
TENS State:       #19.9
TWENTIES State:   *26.2   *26.8
Exiting from exit()...

この出力は、基本的には、以前のstatemachine_test.py のものと同じです。結果の各行は、1つの状態ハンドラーすなわちジェネレーターで費やされたフローを表しています。行の先頭に、フロー・コンテキストが示されています。ただし、ジェネレーター・バージョンは、単にハンドラー関数を再び呼び出すのではなく、別のコルーチンがその中に分岐してきたときには、(ループ内で) 実行を再開します。get_*() コルーチンのすべての本体部分が、無限ループの中で定義されているとすれば、この違いは、あまりはっきりしません。

stategen_test.py で何が根本的に違うのかを確かめるために、exit() ジェネレーターで何が起こっているのかを見てみることにします。ジェネレーター - イテレーターを最初に呼び出すと、ユーザーからジャンプ・ターゲットが集められます (これは、現実のアプリケーションが利用するかもしれないイベント駆動型の分岐決定の単純な場合です)。ただし、exit() が2回目に呼び出されたときは、ジェネレーターの後のほうのフロー・コンテキストの中からであり、終了メッセージが表示され、sys.exit() が呼び出されます。サンプル・コードのやりとりでは、ユーザーは、直接out_of_rangeにジャンプすることもでき、その場合には、別の「ハンドラー」に遷移するのではなく (この同じジェネレーターに再帰的ジャンプを行って) 終了することになります。


まとめ

冒頭部分で触れたように、私は、ステート・マシンのコルーチン・バージョンは、以前に紹介したクラス + コールバック・ハンドラー・バージョンよりもかなり高速に実行されるのではないかと考えています。ジェネレーター - イテレーターを再開するほうが、明らかに効率がよくなるからです。今回の例は、あまりにも単純すぎて、ほとんどベンチマークを行う意味がありませんが、読者のみなさんから具体的な結果をお寄せいただければ幸いです。

ただ、私が今回紹介した「コルーチン・パターン」で高速化が実現されているとすれば、その裏には、このパターンが可能としている、びっくりするほど一般的なフロー制御が寄り添っています。ニュースグループcomp.lang.pythonの数多くの読者が尋ねていることは、Pythonの新しいジェネレーターがどの程度一般的なのかという点です。私は、今回説明したフレームワークを利用できることが答になっている、すなわち「充分一般的」だと考えています。Python関係のものは、ほとんどがそうなのですが、通常、理解するよりもプログラムするほうが、ずっと簡単です。今回紹介したパターンを試してみてください。きっと役に立つことと思います。

参考文献

  • 以前、このコラムで、一般的なステート・マシンの抽象パターンをPythonで実現する例を紹介しました。その記事が、今回の新しい概念を説明するための足がかりとなっています。
  • Stackless Pythonの考案者であるChristian Tismerへの私のインタビューで、コルーチンのことが、継続 (continuations)、マイクロスレッド、ジェネレーターなどの他の外来の (exotic) フロー構造とともに簡単に触れられています。この記事では、Python 2.2にジェネレーターが導入される以前にあったさまざまな問題の中のいくつかについて言及しています。
  • 一番最近で、つながりの強い記事としては、Python 2.2のアルファ期間中に、イテレーターとシンプル・ジェネレーターを紹介しようと私なりに努力した記事があります。
  • このコラムでは何回か、Pythonでの関数プログラムを取り上げています。ジェネレーターにFP (関数プログラミング) 風のところがあるとすれば、以下の記事も一読の価値があるかもしれません。
  • The Art of Assembly にも、コルーチンについての手引きが示されています (アセンブリー向けではありますが)。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=230142
ArticleTitle=魅力的なPython: ジェネレーターによるステート・マシン
publish-date=07012002