季節はずれの…「猛烈に眠かった話の続き (ジェネレータ、イテレータの話)」

2016-08-26記: なんかね、この記事、半年くらい前には書いてて、遥か未来に予約投稿したまま塩漬けしてたんだけど、ふと読み返してみたら、別にそのままあげてもいいんじゃないかな、と思ったのであげます。何を思って塩漬けしたのやら? ちょっと尻切れとんぼ? 何かこのあと書きたかったのかなぁ? まぁ思い出せないからいいや…。



話としては「generator-iterator (ジェネレータイテレータ) なんて言い方もあるのね」の続きにはなるが、ちゃんと書こうと思った動機は実は最新の 3.5 での変更の話がトリガーだったりする。けどその話は別の機会にする。(そっちだけで大作になっちゃうので。)

眠いながらも何をワタシは問題にしたのか、の種明かし

最初に「generator-iterator (ジェネレータイテレータ) なんて言い方もあるのね」の答えあわせをしておく。

実はこんな趣旨のことを言っている記事を見つけてカルチャーショックを受けたのである:「イテレータでは無限ループは書けませんがジェネレータなら出来ます」。

んなわけあるかい、どあほ。

そしてそれを見た 0.1 秒後には既になんでそんな誤解が起こるのかなんか、すぐにわかった。毎度思うことだが、「誰目線なのか」を意識できない人があまりに多い。それだけのことなのだが、順を追って説明しておく。

まず最初に言っておくが、ワタシをはじめ、まっとうなエンジニアが即座に「んなわけあるかい、どあほ」と思えるのは、「検証で確認するから」でも「慣れていて知っているから」でもない。当たり前だが「イテレータのコンセプトを理解しているから」だ。けれども「嘘だと思うならやってみる」:

はい、できあがり
 1 # -*- coding: utf-8 -*-
 2 class MyInfiniteIter(object):
 3     _items = [9, 1, 2]
 4     _idx = 0
 5 
 6     def __iter__(self):
 7         return self
 8 
 9     def next(self):  # Python 2.x では next
10         return self.__next__()
11 
12     def __next__(self):  # Python 3.x では __next__
13         oldidx = self._idx
14         self._idx = (self._idx + 1) % len(self._items)
15         return self._items[oldidx]
16 
17 for it in MyInfiniteIter():  # 無限ループる
18     print(it)

こんなものは書いてみる前からすぐに思いつく実装なのだが、それよりも何よりもまずは、「イテレータってなんなのか」ってことである。

おそらく現役で活躍している言語のなかでは3番目くらいに古い「C 言語」からまずは考える。イテレータよりも前に、「連続したメモリへのシーケンシャルアドレッシング」を考える:

 1 #include <stdio.h>
 2 
 3 int main(void)
 4 {
 5   int arr[] = {3, 4, 5, 6};
 6   int* p;
 7   for (p = &arr[0]; /* point to start of arr */
 8        p != &arr[4]; /* iterate over until p is not the end of arr */
 9        ++p
10        ) {
11     printf("%d\n", *p);
12   }
13   return 0;
14 }

これは arr という「メモリのカマタリ」への要素へのポインタを「一要素サイズぶんずつインクリメントすることで arr 全体を巡る」というコードである。C であれ Fortran であれなんであれ、このように「コンテナ要素を巡回」したり単に繰り返したりすることを「イテレートする」という。という、つーか英語だってーの。ポイントその壱ね。「まずは英語だっての」つー話。

もうこれだけでわかったんでねーの? 「イテレータは無限ループを書け」ないわけあるかい、どあほ、と即効で判断出来る理由は。

さて。上の「イテレートするコード」であるが、剥き身の C 言語が世界だった頃、この時代のこのポインタを「イテレータ」と呼んでいたわけではない。少なくともそういうコンセプトは「ポインタが全て」だったので、あえて「イテレータ」というコンセプトで呼ぶ理由もなかった。ポインタは言うまでもなく「指し棒野郎マクガイバー」に過ぎぬ。けれどもあまりにも強力なコンセプトなので、よっぽど「イテレータ論」に価値ある意味付けをもたらさない限りは、絶対にポインタに勝つことはない。

C 系の言語で「イテレータ」が脚光を浴びることになったのは、「template による型汎用プログラミングにおける、ポインタのアナロジーとして」である。「型汎用」が動機となった「ポインタもどき」は、ちょいとばかり一筋縄ではいかない。というのも、「イテレータが果たすべき要件」を抽象化すると、ポインタの概念はあまりにも自由過ぎて、トゥーマッチなのだ。イテレータはあくまでも「繰り返し要素を持つ某かを要素単位に巡回する」ものに限定されねばならない。そしてこの「巡回野郎」に限定したコンセプトを相手にすると、「イテレータ型に汎用な実装」が成立する:

1   template<typename _InputIterator, typename _Function>
2     _Function
3     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4     {
5       for (; __first != __last; ++__first)
6 	__f(*__first);
7       return __f;
8     }

この関数 for_each にとっての「イテレータ」の要件は 3 つだけ。(1)ポインタのようにアドレスしている位置の比較が出来ること (__first != __last)。(2)ポインタのように要素位置を進めることが出来ること(++__first)。(3)ポインタのように「参照はがし」して要素内容を取りだせること(*__first)。template は「型汎用」なので、この3つの演算が適切に定義(オーバロード)されていれば、for_each はどんなものにも適用出来る。

もともとの C 言語のポインタと C++ template でのイテレータの「同じところ」はその「呼び出し側目線」である。「繰り返してやるぜこのメス豚め」と考えるぶんには、ただのポインタのコードと C++ イテレータは「何一つ変わらない」。

じゃぁ変わったのは本質的にはなんなのか? それは「呼び出されてやるぜ、貴様のために」側である。すなわち、「イテレータ型」は、「巡回させてやるぜ」という要件さえ満たせるならば、中がどうなっていようと構わない。つまり「オブジェクトが良きに計ら」うことが出来る。そう、あなたの好きな「オブジェクト指向」ってヤツだ。

いや待て。その前に、「なんのためにイテレータとあえて呼ぶ必要があったか」だ。『「繰り返し要素を持つ某かを要素単位に巡回する」ものに限定されねばならない』と書いた。これはまごうことなき「プロトコル」、見れば見るほど「プロトコル」、である。「プロトコル」ってのは「お約束」のことデショ。「巡り娘ちゃんのプロフィール」をちゃんと公開しとかないと、皆は誰が「巡り娘ちゃん」なのかわからぬ。これこそが「お約束」が果たす役割だ。

そう。イテレータは、呼び出す側目線では「巡る奴」以上の何者でもないし、呼び出し側目線でこのコンセプトと違うイテレータの考え方を持つ言語を、私はバカなので一つも知らない。知りたくもない。集合を巡ることだけが要件なのだから、対象が有限だろうが無限だろうが関係があるはずなどない。「有限集合を無限に巡る」ことは合法だ。だってイテレータの要件じゃないもの、「巡り方」は。好きに巡ればいいんだよ。

そして話はジェネレータへ

ジェネレータの話からは Python に限って話していく。Python だけでも相当盛りだくさんだからだ。それに Python 以外のジェネレータには私は詳しくはないし。

さて。「何を問題にしたのか」の話にはまだ続きがある。それは、「ジェネレータはイテレータである」という点に関してだ。

集合論的包含関係では、「ジェネレータはイテレータであるがイテレータはジェネレータとは限らない」となる。まずはこれを真っ先に知るべきなのだ。どういうわけだか「ジェネレータとイテレータは似ているが違う」という役に立たない理解から入ってしまう人がやたらに多いんではないのか。もう一度繰り返す。「ジェネレータはイテレータであるがイテレータはジェネレータとは限らない」。ベン図を頭に描いておくんだな。

「ポインタのコンセプトがイテレータのコンセプトに昇華」した際に我々が何を得たのかを、もう一度思い出しておきたい。「呼び出し側からみれば何も変わらない」というのが一つだが、「呼び出される側からみれば、箱庭での自由」を得たことは理解出来るだろうか? 「約束さえ守れるなら、中で何したって構わない」。つまり「イテレータを書く人」の自由が増したのだ。(当たり前だが「コンセプト」だけで解決したのではなく、C++ であれば「オブジェクト指向サポート」「ジェネリックプログラミングサポート」を伴うことで得た自由だ。)

ではジェネレータではどうか? そのためにはまず「ジェネレータはイテレータである」から考える。これは実際には「ジェネレータは、イテレータを生成する子ちゃんである」てぇことである。つまり一番底辺の発想はイテレータを作成するもの、がジェネレータなのである。そしてこれはまだ「呼び出し側目線」に留まったままの発想だ。そして、イテレータが得たのと同質の自由、「中で何したって構わなかろ?」がジェネレータにもあるのだが…。

まさにこの「ジェネレータを書く人」が得た自由の種類が、イテレータのそれとは違うのである。そして、紹介したような馬鹿げた誤解が生じるのもまた、このジェネレータの得た自由が「派手」なために、こればかりにスコープした説明がされるし、無垢な初心者が飛びつくわけである。もう一度言うが「ジェネレータはイテレータである」ので、ジェネレータ固有部分を使わない限りは、利用者目線では「同じものにしかみえない」ことは忘れてはならないし、「ジェネレータがイテレータである」部分について「イテレータと違う」ということが「起こるはずがない」と考えられないようなら、どこか頭のネジが緩んでおるのであろう。

それではようやくその「ジェネレータを書く人が得たもの」を説明してみる。

ジェネレータを書く人が得たもの Part I

唐突に「Part I」なのはあとでわかる。今はまだ「イテレータを作る子ちゃん」に留まっていて欲しい。たとえあなたが多少知識を持っていたとしても。

まず先に、いったんイテレータともジェネレータとも離れ、以下のコードを見て欲しい:

 1 class Edgar(object):
 2     def age(self):
 3         return 500
 4 
 5 class Alan(object):
 6     def age(self):
 7         return 120
 8 
 9 def query_age(vanpanera):
10     return vanpanera.age()
11 
12 print(query_age(Edgar()))
13 print(query_age(Alan()))

何の変哲もない。いわゆる「ビジターパターン」の基礎となるものとも言えるであろうが、query_age 関数の引数は「age」メソッドを仮定し(プロトコル)、それを「呼び出す」ことで自分の責務を果たす。ここでひとまず注目しておいて欲しいのが、query_age を呼び出すコードが呼び出されるコードに及ぼす「作用」についてである。ジェネレータで得たものがわかるとはっきりするが、ひとまずは、「一方通行である」ということである。print(query_age(Edgar()))はトップレベルに流れていくだけであって、この呼び出しコードが query_age 内部にちょっかいを出すことは出来ない。

ではようやくジェネレータだ。最初に紹介するのは「Python 2.2 で初めて What’s New In Python 2.2 で紹介された際に使われた例」である:

1 def generate_ints(N):
2     for i in range(N):
3         yield i

「ジェネレータを作るには yield を使う」ということを憶えることは無論大事だが、それよりも重要なのは、「呼び出しコードとセットで理解する」ことだ:

1 def generate_ints(N):
2     for i in range(N):
3         yield i  # (2)'
4 
5 for it in generate_ints(3):  # (1) ジェネレータはイテレータである…
6     # あたかもここで (2)' が実行されているようにみえる - ※
7     print(it)  # (2)

※部分があとで驚くべき逆転をするのは今は置いておくとして、先の query_age の「一方向性」とは既に違うことが見て取れる。「for i in range(N)」内の繰り返しが「何度も呼び出し側に戻っている」ように見えるはずだ。おや?? そう。これこそが「yield」。

yield の英語の意味を辞書で調べると、「産み出す」の意味とともに、「明け渡す」「譲る」の意味があることがわかるであろう。Python の yield はまさにこの両方の意味を込めているのではないか。呼び出す側に対して値を「産み出す」とも言えるし、「呼び出される側が呼び出し側に(値を伴って)処理を譲る」とも言える。Python は「イテレータ作り屋さん」を、「作り屋さんがお客様を出来次第都度呼び出す」というコンセプトでもって実現したわけである。ラーメン屋で言えばまさにセルフサービスだ。客がお盆を持って取りにいくわけである。回転寿司方式とは違う。

ただし今のところ、この革新的な発想の転換は、「効果」の面では特に何かを生み出したわけではない。処理フローの流れが「異端児」なだけだ。けれどもこの「異質な感じ」をまず掴んで欲しい。これが掴めないと以降の話は絶対に理解できない。まだピンと来ていないなら、是非立ち止まって、上のコードがどういう順番で流れるのか、正確に追いかけておくこと。

ジェネレータを書く人が得たもの Part II

一つ前で説明したのが Python 2.2 で導入された、最もプリミティブなジェネレータである。そして Python 2.4 までは、本当にこれしか出来なかった。

Python 2.5 でこれは驚くべき進化を遂げる。

もう一度思い出して欲しい。「呼び出し側コードに逐一戻る」フローを。「呼び出し側に逐一戻る」という理解は、つまり先の例では:

1 def generate_ints(N):
2     for i in range(N):
3         yield i  # (2)'  # -> ここで(2) が実行されている(print(i))と考えることも出来る # ※2
4 
5 for it in generate_ints(3):  # (1) ジェネレータはイテレータである…
6     # あたかもここで (2)' が実行されているようにみえる、と考えるのではなく…
7     print(it)  # (2)

と見方を逆にすることも出来るであろう。2.5 で起こった進化はまさにこの視点の変化が関係する。つまりこういうことだ:

もしも「※2」で「(2)」の結果を受け取れるとしたらどうなるだろうか?

このことをもって、Python ドキュメントでは「ジェネレータは情報の一方的な生産者から、生産者かつ消費者という存在に変貌を遂げたのです。」という、熱量の高い表現でこの進化を歓迎している。これはいわゆる「コルーチン」モデルの基礎でもある。

今回の例も What’s New In Python 2.5 からのものをそのまま拝借する:

 1 # -*- coding: utf-8 -*-
 2 def counter(maximum):
 3     i = 0
 4     while i < maximum:
 5         val = (yield i)  # 呼び出し側に i を返しつつ、呼び出し側から値を受け取る  # ※3
 6         # If value provided, change counter
 7         if val is not None:
 8             i = val
 9         else:
10             i += 1
11 
12 # 使うほうはやや不自然な例 (無限ループる)
13 gen = counter(10)
14 for it in gen:
15     if it == 9:
16         gen.send(0)  # counter に値を送信する
17     print(it)

print(it) が「※3」で「あたかも実行」されているのと同じく、gen.send(0)も「※3」で「あたかも実行」されている。両者の違いは後者が値を counter に返すことだ。

ジェネレータは情報の一方的な生産者から、生産者かつ消費者という存在に変貌を遂げたのです。」という革新は、「呼び出し側コードに逐一戻る」という 2.2 で既にあった芽があってこそである、たぶん、きっと、おそらく。

そして繰り返しにはなるが、「これにてジェネレータは「イテレータ作る子ちゃん」だけではなくなった」ということだ。「イテレータだけでは出来なくて、ジェネレータでは出来ること」がこれにて登場したわけである。

ジェネレータを書く人が Python 2.x で「得ることが出来なかった」もの

Python 2.x でジェネレータを多用すればするほどどんどんストレスが嵩んでいく、一つの大き過ぎる機能不足がある。

以下は Python 2.x では十中八九意図したものと違う:

 1 # -*- coding: utf-8 -*-
 2 def gen0():
 3     for i in range(10):
 4         yield i
 5 
 6 def gen1():
 7     # gen0 が yield したものを yield したいのだが…
 8     yield gen0()
 9     # 結局以下しか意図したものにならない
10     # for it in gen0():
11     #     yield it
12 
13 print([i for i in gen1()])

これはジェネレータコードが大きくなってくるとすぐに問題になる。この制約のおかげで、「最初はジェネレータとして書いた内部関数」などを、「通常の関数にしてしまったほうがマシ」という決断をせざるを得ないことも多い。上の例で「結局以下しか意図したものにならない」としたコードが結局必要なのでは、あえてジェネレータである理由が薄れることも多いからだ。(つまりソースコードを小さくしたいというのが目的だとして、ジェネレータが空間効率が良い可能性がある、という側面を無視してでもソースコードを小さくしたいなら、「リストを返す関数じゃダメですか?」も選択肢になりえたりするから。)

例えばありがちなのは、「特殊なフォーマットを持つテキストファイルを読み込む」ための処理を、最初はジェネレータで書く、と言った場合だったりする。例えばこんなである:

 1 import re
 2 
 3 def get_lines(fn):
 4     with file(fn) as fi:
 5         for line in fi.readline():
 6             # ...何か re を使ってトークンに分解して…
 7             yield tok1, tok2
 8 
 9 for tok1, tok2 in get_lines("hoge.dat"):
10     # 何か処理

これの、上では get_lines を「使っている」コードを、さらに何か包みたくなるケースが多いのだ。

この求めている機能は「サブジェネレータへの委譲」であって、そしてこれがないことが「世界が破滅するほど致命的」なんてことはもちろんないので、小さなイライラとなって積み重なる程度の、「是が非でも欲しいけれども必須とも言えない」もの、であった。

そして Python 3.3 で「サブジェネレータへの委譲」が追加された

ヲ望みのブツ
1 def g(x):
2     yield from range(x, 0, -1)
3     yield from range(x)
4 
5 list(g(5))

これこそが欲しかったものである。先に「2.x で意図と違っていたもの」は今や:

 1 # -*- coding: utf-8 -*-
 2 def gen0():
 3     for i in range(10):
 4         yield i
 5 
 6 def gen1():
 7     # gen0 が yield したものを yield 
 8     # (gen0 が range(10) でループしているので以下一文は 10 回 yield することになる)
 9     yield from gen0()  # yield from
10 
11 print([i for i in gen1()])