[Python-ml-jp 467] PEP 255 -- Simple Iterator
Toda Takahiro
toda_takahiro ＠ h4.dion.ne.jp
2001年 7月 22日 (日) 13:00:53 JST
PEP: 255
Title: 簡易ジェネレータ
Version: $Revision: 1.15 $
Author: nas ＠ python.ca (Neil Schemenauer), tim.one ＠ home.com (Tim Peters), magnus ＠ hetland.org (Magnus Lie Hetland)
Discussion-To: python-iterators ＠ lists.sourceforge.net
Status: Draft
Type: Standards Track
Requires: 234
Created: 18-May-2001
Python-Version: 2.2
Post-History: 14-Jun-2001, 23-Jun-2001
--------------------------------------------------------------------------------
概要
このPEPでは、Pythonにジェネレータ(generators)の概念と、ジェネレータと
一緒に使われる新しいステートメントである "yield" ステートメントを導入
する。
動機
生産者(producer)関数が生産される値の間で状態の維持を要求するという難
しい仕事がある場合、ほとんどの言語は、生産される値ごとに呼び出される
コールバック関数を生産者関数の引数リストに付加する以上の、快適で効率
的な解決策を提供していない。
例えば標準ライブラリのtokenize.pyは次のようなアプローチを取っている。
呼び出す側は"tokeneater"関数をtokenize()に渡さなければならない。そして
tokenize()が次のトークンを見つけるたびに"tokeneater"が呼び出されるの
である。これによってtokenizeを自然なやり方で書くことができるとはいえ、
直前のトークンが何であったのかを(呼び出し側で)憶えておく必要があるため、
典型的にはtokenizeを呼び出すプログラムが込みいったものになってしまう。
tabnanny.pyのtokeneater関数がこの好例であり、すでに見たトークンと次に
見たいトークンをコールバック呼び出しの間で憶えておくために、状態機械を
グローバル変数群に保持しているのである。このアプローチは正しく動作さ
せるのが難しかったし、今もなお理解するのが難しい。不幸にもこれがこの
アプローチの典型なのである。
tokenizeの別のアプローチとしては、一度にPythonプログラム全体のパース
(構文解析)を単一の巨大なリストの形で生成する方法もありえたであろう。
この方法ではtokenizeのクライアントは自然なやり方で、つまりループや
入れ子のif文のようなローカルな制御フローとローカル変数とを使って書く
ことができたことであろう。しかし、これは実用的ではないのである。なぜ
なら、(パースされる)プログラムは非常に巨大でありうるので、パースの全
体を実体化するのに必要なメモリ量の上限を前もって確定することができな
いからである。また、プログラムの先頭のほうに何か特定のもの(例えば
future文や、IDLEでなされているように最初のインデントされた文)がある
かどうかだけを調べたいのであって、最初にプログラム全体をパースするこ
とが大変な時間の無駄になってしまうようなtokenizeクライアントも存在す
るためである。
tokenize関数をイテレータ(iterator)[1]とするという別の代替策もありえた
であろう。このイテレータの .next() メソッドが起動されるたびに次のトー
クンを配送するわけである。これは、呼び出し側にとって快適なやり方である
という点ではパース結果の巨大なリストの場合と同じだが、メモリ使用量が
予測できないという短所と「早く結果を出したいときはどうなるの?」とい
う短所は持たないのである。
しかしながら、これは .next()メソッド起動の間でtokenizeの状態を憶えて
おくという重荷をtokenizeそれ自体に転嫁するものであって、プログラムの
読み手がtokenize.tokenize_loop()を一瞥するだけで、どんなに忌まわしい
仕事であるかに気づくということになるであろう。(tokenize_loop()が非常
に理解しがたいものになるであろう。)
あるいは、一般的なツリー構造のノードを生成する再帰アルゴリズムを想像
してほしい: このアルゴリズムをイテレータ・フレームワークに変換するに
は、人手で再帰を取り除き、人手で探索(travarsal)の状態を保持しておく
ことが要求されるのである。
第四の選択肢は、生産者と消費者とを独立したスレッドで実行することであ
る。こうすれば両者の状態を自然なやり方で保持できるようになるし、両者
にとって快適でもある。実際に、Pythonソース配布にある
Demo/threads/Generator.pyはこれを一般的なやり方で行うための使いやすい
同期通信クラスを提供している。とはいえ、このクラスはスレッドのないプ
ラットフォームでは動作しないし、スレッドがあるプラットフォームにおい
てもスレッドを使わずに達成できるものと比較して大変遅くなってしまうの
である。
最後の選択肢は、PythonのStackless[2][3]実装を代わりに用いることであ
る。これにはスレッドの選択肢と同じプログラム上の利点があるのだが、ス
レッドに比べて大いに効率的である。とはいえ、スタックレスはPython中核
部への意見の相反する再検討であり、Jythonが同じセマンティクスを実装で
きないかもしれないのである。このPEPはこれを議論する場ではないので、
ジェネレータは現行のCPython実装へ容易に適合できるようなやり方で
Stacklessの役に立つ部分集合を提供するものであり、他のPython実装にとっ
ても比較的ストレートであると信じられていると述べておけば十分であろう。
現状の代替案は以上ですべてである。(ところで、)快適な解決策を提供する
他の高級言語がある。そのうち特筆すべきは、Sather[4]におけるイテレータ
(これはCLUにおけるイテレータからヒントを得ている)と、すべての式が
「ジェネレータである」ようなIcon[5]という斬新な言語におけるジェネレー
タである。両者の間には違いもあるのだが、基本的な考え方は同じものである。
つまり、「途中の計算結果(「次の値」)を呼び出し側に返すことができるような
ある種の関数を提供せよ。ただし、関数が前回中断した箇所から再開できる
ように、関数のローカルな状態を保持しながら。」という考え方である。
この考え方の非常に単純な例は次のようなものである:
def fib():
a, b = 0, 1
while 1:
yield b
a, b = b, a+b
fib()が最初に起動された時、aに0を設定し、bに0を設定し、それからbを
呼び出し側に返す。呼び出し側には1が見える。fibが再開(resume)した時、
fib自体の視点から見るとyield文は例えばprint文とまったく同じである。
つまりすべてのローカルな状態を保ちつつyield以後を継続して実行する。
そしてaとbがそれぞれ1と1になり、ループしてyield文まで戻り、1を呼び出
し側に返す。以下同様。fibの視点から見ると、コールバックでやるように、
一連の結果を配送しているだけである。しかし呼び出し側の視点から見ると、
起動されたfib(つまりジェネレータ‐イテレータ)は意のままに再開できる
ような反復可能(iteratable)なオブジェクトである。これで、スレッドの
アプローチにおけるのと同様に、両者をもっとも自然なやり方で書けるよ
うになる。ただしこちらはスレッドのアプローチとは違い、効率的に実行
されるし、すべてのプラットフォームで実行できるのである。実際には、
ジェネレータを再開することは関数呼び出しより高価にならないはずであ
る。
同種のアプローチが生産者/消費者関数の多くに適合する。例えばtokenize.py
は、引数として与えられたコールバック関数を起動する代わりに、次のトー
クンを譲り渡す(yield)ことができ、tokenizeのクライアントは自然なやり
方でそれらのtokenを反復処理することができる。というのも、Pythonジェ
ネレータはPythonイテレータ[1]の一種であり、しかもすこぶる強力な種類
のイテレータだからである。
仕様: Yield
次の新しいステートメントを導入する:
yield_stmt: "yield" expression_list
"YIELD" は新しいキーワードなので、このキーワードを徐々に導入するため
のfuture文[8]が必要となる。初期のリリースにおいては、ジェネレータの
使用を望むモジュールには次の行が先頭(PEP 236[8]参照)に含まれていなけ
ればならない。
from __future__ import generators
future文なしに識別子"yield"を使っているモジュールはウォーニングを生
じることになる。以降のリリースにおいては、yieldが言語のキーワードに
なって、もはやfuture文は必要とされなくなる。
yield文は関数の内側に限って使用される。yield文を含んでいる関数のこと
をジェネレータ関数と呼ぶ。ジェネレータ関数はすべての側面において通常
の関数オブジェクトであるが、そのコードオブジェクトのco_flagsメンバに
は新しいCO_GENERATORフラグがセットされている。
ジェネレータ関数が呼び出されたとき、通常のやり方で実引数が関数ローカ
ルの仮引数名に束縛されるが、関数本体のコードは一切実行されない。その
代わりに、ジェネレータ‐イテレータ・オブジェクトが返される。このオブ
ジェクトはイテレータ・プロトコル[6]に準拠しているので、とりわけ for
ループにおいて自然なやり方で使うことができる。文脈より意図が明らかで
ある場合には、非修飾名の「ジェネレータ」がジェネレータ関数あるいはジェ
ネレータ‐イテレータのいずれをも指しうることに注意してほしい。
ジェネレータ‐イテレータの .next() メソッドが起動されるたびに、yield
文もしくはreturn文(下記参照)に遭遇するか、あるいは、関数本体の終わり
に到達するまでのあいだ、ジェネレータ関数本体のコードが実行される。
yield文に遭遇した場合は、関数の状態が凍結されて、expression_listの値
が .next() メソッドの呼び出し側に返される。ここで「凍結」とは、ローカ
ル変数の現時点における束縛や、インクルージョン・ポインタ、内部の評価
スタックを含むローカルな状態が保持されるということを意味する。つまり、
次に .next() メソッドを起動するために十分な情報が保存されて、まさに
yield文が単なるもうひとつの外部呼出しであるかのように、関数の実行を継
続できるのである。
制限事項: try/finally構成体(try/finally construct)のtry句の中における
yield文は許されない。これは、ジェネレータが常に再開するということが
保障されないため、それゆえfinallyブロックが常に実行されることが保障
されない(これはfinallyが生まれた目的を著しく侵害するものである)とい
うことが、じゃまになっているのである。
仕様: Return
ジェネレータ関数は次の形式のreturn文を含むことができる。
"return"
ジェネレータの本体においてはreturn文のexpression_listが許されないと
いうことに注意してほしい。(ただし、当然のことであるが、ジェネレータ
の中でネストした非ジェネレータ関数の本体にはそれらが出現してもよい。)
return文に遭遇した時、通常の関数におけるreturnと同じように制御が進行
し、(もしあれば)適切なfinally句が実行される。続いてイテレータが尽き
たことを通知するStopIteration例外が生じる。明示的なreturnがないジェ
ネレータの終わりに制御が到達した場合にもまた、StopIteration例外が生
じる。
ジェネレータ関数であろうと非ジェネレータ関数であろうと、return は
「終わったけれど返すべきものが何もない」という意味であることに注意
してほしい。
returnが常にStopIteration例外の生起と等価であるとは限らないというこ
とに注意してほしい。取り囲むtry/except構成体がどのように扱われるかと
いう点に違いがあるのである。例えば、
>>> def f1():
... try:
... return
... except:
... yield 1
>>> print list(f1())
[]
こうなる理由は、どの関数においてもそうであるように、returnは関数から
単に抜け出すためであるが、しかし、
>>> def f2():
... try:
... raise StopIteration
... except:
... yield 42
>>> print list(f2())
[42]
こうなるのは、どの例外もそうであるように、StopIterationが引数無しの
"except"に捕捉されるからである。
仕様: ジェネレータと例外の伝播
未処理の例外――StopIterationを含むが、それのみに留まらない――が
ジェネレータ関数で生じた場合、またはジェネレータ関数を通過する場合は、
その例外は通常のやり方で呼び出し側へ渡されて、次にジェネレータ関数を
再開しようとするとStopIterationが生じる。言い換えれば、未処理の例外
はジェネレータの有益なる人生を終結させるのである。
例 (慣用的ではないが論点を説明するもの):
>>> def f():
... return 1/0
>>> def g():
... yield f() # ゼロ除算例外が伝播するから、
... yield 42 # ここには絶対に来ない
>>> k = g()
>>> k.next()
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 2, in g
File "<stdin>", line 2, in f
ZeroDivisionError: integer division or modulo by zero
>>> k.next() # もうジェネレータは再開できない
Traceback (most recent call last):
File "<stdin>", line 1, in ?
StopIteration
>>>
仕様: Try/Except/Finally
以前にも注記したように、try/finally構成体のtry句においてyieldは許さ
れない。それゆえに、ジェネレータはクリティカルな資源を最大限の注意を
払って取り扱う必要がある。finally句、except句、あるいはtry/except構
成体のtry句の中に現れないのであれば、yieldにはいかなる制限もない。
>>> def f():
... try:
... yield 1
... try:
... yield 2
... 1/0
... yield 3 # ここには絶対に来ない
... except ZeroDivisionError:
... yield 4
... yield 5
... raise
... except:
... yield 6
... yield 7 # 上の"raise"がこれを止める
... except:
... yield 8
... yield 9
... try:
... x = 12
... finally:
... yield 10
... yield 11
>>> print list(f())
[1, 2, 4, 5, 8, 9, 10, 11]
>>>
例
# 二分木クラス。
class Tree:
def __init__(self, label, left=None, right=None):
self.label = label
self.left = left
self.right = right
def __repr__(self, level=0, indent=" "):
s = level*indent + `self.label`
if self.left:
s = s + "\n" + self.left.__repr__(level+1, indent)
if self.right:
s = s + "\n" + self.right.__repr__(level+1, indent)
return s
def __iter__(self):
return inorder(self)
# リストからTreeを生成する。
def tree(list):
n = len(list)
if n == 0:
return []
i = n / 2
return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
# Treeの葉をin-orderで生成する再帰的なジェネレータ
def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.label
for x in inorder(t.right):
yield x
# いざご覧あれ: 木を生成する。
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# Print the nodes of the tree in in-order.
for x in t:
print x,
print
# 非再帰的ジェネレータ。
def inorder(node):
stack = []
while node:
while node.left:
stack.append(node)
node = node.left
yield node.label
while not node.right:
try:
node = stack.pop()
except IndexError:
return
yield node.label
node = node.right
# 非再帰的ジェネレータを使う。
for x in t:
print x,
print
どちらの出力もこのような文字を表示する
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Q & A
Q. "def"を再利用するのではなく新しいキーワードをなぜ使うのか?
A. 以下のBDFLの裁定の節を参照。
Q. 新しいキーワードを"yield"にするのはなぜか?
A. Pythonではキーワードを使うほうがよりよく制御フローを表現でき、
yieldは制御構成体である。またJythonにおける効率的な実装のためには
コンパイル時にコンパイラが潜在的な停止ポイントを決定できるように
することが必要であると信じられており、新しいキーワードはこれを容
易にする。CPythonリファレンス実装もまた、どの関数がジェネレータ
関数であるかを判別するためにこれを大いに利用している。(とはいえ、
CPythonでは"def"の代わりに新しいキーワードを置くことで解決できた
であろう。――だが「なぜ新しいキーワードを導入するのか?」と尋ねる
ような人はいかなる新しいキーワードをも望まないものである。)
Q. それでは、新しいキーワードではなく何か別の特殊な構文を使ってはど
うか? 例えば"yield 3"とする代わりに以下のうちのいずれかを:
return 3 and continue
return and continue 3
return generating 3
continue return 3
return >> , 3
from generator return 3
return >> 3
return << 3
>> 3
<< 3
A. これで全部だったかな<wink>? 何百ものメッセージのうちの二通がその
ような代替案を示唆しており、上記の例はそれらのメッセージから抜き
出したものである。新しいキーワードを必要としないことは結構構なこ
とではあるが、yieldによって非常に明快になることのほうがずっと結構
なことなのである。――かつてはキーワードやオペレータの意味のない
並びであったものの意味を理解することによって、(制御の)譲り渡しが
生じているということを、私は「推定」したいとは望まない。
Q. いったいなぜ"return"を許すのか? 強制終了を"raise StopIteration"と
記述してはどうか?
A. StopIterationのメカニズムは、Python 2.1におけるIndexErrorのメカニ
ズムと同様に、低水準の細部である。実装は見えないところでよく定義
された「何か」を必要とするのであり、Pythonは上級ユーザにたいして
そのようなメカニズムを見せている。とはいえ、これは低水準で働くこ
とをすべての人に強制することを主張するものではない。どんな種類の
関数であろうと"return"は「これで終わった」ということを意味するも
のであり、これは説明するのも使うのも易しい。try/except構成体の中
では"return"が常に"raise StopIteration"と等価であるとは限らないこ
とにも注意してほしい。(「仕様: Return」の節を参照。)
Q. "return"にも式を許してはどうか?
A. たぶんいつの日にか。Icon言語では、"return expr"は「これで終わり」
を意味するとともに、「最後の有意義な値もひとつあって、それがこれ
です」ということをも意味する。まずは、"return expr"の説得力のある
使い道もないので、値を配送するのに"yield"だけを使うことにするほう
がすっきりとしている。
BDFLの裁定
論争点: ジェネレータ関数と非ジェネレータ関数とを区別するために、"
def"の代わりに新しいキーワード(例えば"gen"や"generator")を導入す
るか、さもなくば別の構文を導入せよ。
反対論: 実用的には(人によって考えが違うであろうが)ジェネレータとは
まさに関数であって、ただ、再開を可能とするように変更されているだけの
ものである。それらがどのようにセットアップされるのかというメカニズム
は比較的重要でない技術論であるにもかかわらず、新しいキーワードの導入
はジェネレータがどのように開始するのかというメカニズム(きわめて重大
ではあるけれどもジェネレータの人生のごく一部にすぎない)を手の施しよ
うのないほどまでに強調しすぎてしまう。
賛成論: 現実的には(人によって考えが違うであろうが)ジェネレータ関数
とは実際は魔法のようにジェネレータ‐イテレータを生み出すようなファク
トリ関数である。この観点から見て非ジェネレータ関数とは大変異なってお
り、関数というよりも構築子(constructor)のように振舞うものであるから、
"def"の再利用は、よく言っても、紛らわしいものである。関数本体に埋没し
た"yield"文は、セマンティクスの大きな違いを警告するには十分でない。
BDFL: "def"のままにせよ。両者のいずれの主張も完全に納得のいくもので
はないので、(この裁定はBDFLの)言語設計者としての直感に従ったものであ
る。直感によれば本PEPが提案する構文は完全に正しい。――暑すぎもせず、
寒すぎもせず、というところである。しかし、ギリシャ神話におけるデルポ
イの神託がそうであるように、この直感はなぜそうなのかは語らないので、
PEPの構文への反対論にたいして反証を挙げることはできない。(すでに出た
反証についての合意は除いて、)もっともよい理由としては"FUD"が思いつく。
すなわち、もしこの構文が最初から言語の一部であったなら、この構文が
Andrew Kuchling の「Pythonの欠点」のページに掲載されているとはとても
考えられないので、正しいといえる。
リファレンス実装
現在の実装は、予備的な段階(文書なし)であり、PythonのCVS開発ツリー[9]
の一部となっている。このリファレンス実装を使用するためにはPythonを
ソースから構築することが必要になる。
このリファレンス実装は、Neil Schemenauer[7]による初期のパッチから派
生したものである。
脚注と参考文献
[1] PEP 234, Iterators, Yee, Van Rossum
http://www.python.org/peps/pep-0234.html
[2] http://www.stackless.com/
[3] PEP 219, Stackless Python, McMillan
http://www.python.org/peps/pep-0219.html
[4] "Iteration Abstraction in Sather"
Murer , Omohundro, Stoutamire and Szyperski
http://www.icsi.berkeley.edu/~sather/Publications/toplas.html
[5] http://www.cs.arizona.edu/icon/
[6] イテレータの概念は PEP 234 で述べられている。前出の[1]を参照。
[7] http://python.ca/nas/python/generator.diff
[8] PEP 236, Back to the __future__, Peters
http://www.python.org/peps/pep-0236.html
[9] この実装を試したいのであれば
http://sf.net/cvs/?group_id=5470
の説明にしたがってPythonをチェックアウトせよ。標準テスト
Lib/test/test_generators.py にはこのPEPに掲載されたものを含めて
多くの例がある。
著作権
この文書はパブリック・ドメインに置かれている。
Python-ml-jp メーリングリストの案内
