意外と思ったようにプログラミングが出来なくて辟易する事も多いのじゃないだろうか。
ところで、前にも書いたけど、Pythonは易しい言語なので、平均的ユーザーも多いが、同じくらい尖ったユーザーも多い。
尖ったユーザーが良く話題にするのが、「Pythonと遅延評価」である。
それは上に書いたジェネレータやイテレータ絡みで、ネット上を検索すると、Pythonのオピニオンリーダー達は、Pythonでは遅延評価が扱えるので素晴らしい言語なんだ、と讃えがちである。
しかし、これも以前書いたけど、厳密には正しくないのだ。
Pythonでは遅延評価は扱えない。あくまで扱えるのは「一見遅延評価に見える」遅延評価モドキである。
個人的にはこの辺はキチンと押さえておいた方が良いような気がしてる。ジェネレータやイテレータでは扱えないモノをキチンと把握してた方が、むしろジェネレータやイテレータの理解に繋がるのではないだろうか。
なお、本当の話をすると、このテのトピックは本来ならどっぷりと遅延評価言語なHaskell辺りのエキスパートが話さなければならないんだが。
いずれにせよ、Pythonに欠けてるのは実は遅延リスト、とか遅延シーケンス、とかストリームと呼ばれるオブジェクトなのだ。ジェネレータやイテレータではこれを実装する事が出来ない。
Schemeを用いてまずはこの例を見てみよう。
Schemeには、実装によるが、SRFI-41と呼ばれるライブラリ(※)を扱う事が出来、このSRFI-41では強力な遅延リスト、そこではストリームと呼ばれるが、関連のライブラリが提供されている。
例えば、Schemeでストリームは次のようにして生成出来る。
(define strm (stream 1 2))
これはPythonだとほぼ次のようなカンジ、つまりyieldを用いたカタチで解釈される。
>>> def strm():
yield 1
yield 2
ところが、次のような事がPythonでは出来ない。
Schemeではこのストリームに要素を追加可能なのである。
> (set! strm (stream-cons 0 strm))
これはPythonで言うと、一旦作ったstrmに何らかの要素をyield込みで追加出来て、ジェネレータの状態を変更する、事を意味するのだが、生憎Pythonではそのような「ジェネレータをリコンストラクトする」機能は提供されていない。
>>> strm = 0 + strm()
Traceback (most recent call last):
File "", line 1, in <module>
strm = 0 + strm()
TypeError: unsupported operand type(s) for +: 'int' and 'generator'
>>> strm = iter(0) + strm()
Traceback (most recent call last):
File "", line 1, in <module>
strm = iter(0) + strm()
TypeError: 'int' object is not iterable
>>> strm.append(0)
Traceback (most recent call last):
File "", line 1, in <module>
strm.append(0)
AttributeError: 'function' object has no attribute 'append'
>>>
まずこれが、少なくとも遅延評価には必要な機能なのである。
次に、遅延評価と関数型言語は密接な関係があるが、Pythonはそれを満たしていないのだ。
例えばSchemeで無限長の1から始まる整数列のストリームは次のように定義する。
> (define (integers-starting-from n)
(stream-cons n (integers-starting-from (+ n 1))))
> (define integers (integers-starting-from 1))
最初にintegers-starting-fromと言う遅延評価前提の関数を再帰的に定義してる。平たく言ってしまえば1から始まる整数列は2から始まる整数列の先頭に1を付け加えたモノだ、と言うとんでもない定義になっている。
これもマトモな評価機構(先行評価)なら無限ループに陥る筈だが、前提が返り値はストリーム、つまり遅延評価リストなので、問題なく定義可能だ。
このとんでもない定義をPythonに移植するには、yieldを用いて近似的に次のように定義が出来る。
>>> def integers_starting_from(n):
while True:
yield n
n += 1
>>> integers = integers_starting_from(1)
以前書いたように、Python側も基本的には無限ループをyieldで一時停止させるようなジェネレータになってる。
両者ともオブジェクトなんで、代入した変数、integersをそのまま呼び出してもオブジェクト名を返すだけだ。
;; Scheme> integers
#<stream># Python>>> integers
<generator object integers_starting_from at 0x7f56542765f0>
ところがここから、が違う。さて、お立ち会い。
Pythonの場合は、__next__()メソッドを用いて、generatorオブジェクトから値を返す事が可能である。
>>> integers.__next__()
1
>>> integers.__next__()
2
>>> integers.__next__()
3
>>> integers.__next__()
4
>>> integers.__next__()
5
>>>
ところがSchemeだとどうだろうか。
Schemeのストリームへの基本アクセサはstream-carと呼ばれ、これはストリームの先頭を返す。ここ極めて重要。「ストリームの先頭の値しか取り出せない」と言うのが基本なのだ。
つまり、
> (stream-car integers)
1
> (stream-car integers)
1
> (stream-car integers)
1
> (stream-car integers)
1
> (stream-car integers)
1
と何度やってもintegersの先頭しか返ってこない。
もちろん、他に便利な複合的なアクセサもあるんだが、今はそれを使わないで基本だけで説明している。その方が分かりやすいからだ。
つまり、Pythonと同じ結果を得るには、基本アクセサstream-carともう一つの基本アクセサ、先頭以外の部分を返すstream-cdrを組み合わせて使うだけだと実は次のように書かないとならない。
> (stream-car integers)
1> (stream-car (stream-cdr integers))
2
> (stream-car (stream-cdr (stream-cdr integers)))
3
> (stream-car (stream-cdr (stream-cdr (stream-cdr integers))))
4
> (stream-car (stream-cdr (stream-cdr (stream-cdr (stream-cdr integers)))))
5
「うわっ、酷い、貧弱ゥ!!!」とか思う?だろ?
実は違うんだな。どうしてSchemeだとこんなメンド臭い事になるのか、キチンとした理由があるのだ。
「後の数になるほどstream-cdrを使う数が増えていく」と言うのはそれだけ先頭からの要素が邪魔になるから、だ。
じゃあ、何で邪魔になるのか、と言えば、先頭からの数値は「相変わらずそこに居座ってるから」なのだ。分かる?
そう、Schemeのストリームとは永続的にそこに鎮座してるデータ型なのだ。そこがPythonのジェネレータが作ったモノと決定的に違う。
事実、Pythonは初期状態に「巻き戻し」が出来ない。相変わらず__next__()メソッドを使うとどんどん新しい値を返してくる。
>>> integers.__next__()
5
>>> integers.__next__()
6
>>> integers.__next__()
7
>>> integers.__next__()
8
>>> integers.__next__()
9
>>> integers.__next__()
10
つまり、ここでのintegersと言うオブジェクトは最初のブツと既に同じではない。要するにオブジェクトで破壊的変更が行われてるのだ。
関数型言語ではむやみやたらにデータを破壊的に変更しない。結局、それが故にストリームは永続的に定義されたままで存在しようとし、それは関数型言語の機能としては極めて正しいのだ。
まとめると、Pythonの「遅延評価モドキ」が遅延評価たり得ないのは次の二つの理由による。
- ジェネレータ/イテレータで定義されたデータ構造を外部からリコンストラクトする事が不可能である。
- ジェネレータ/イテレータで定義されたデータ構造は破壊的変更前提で定義されている。
同じように無限長の「何らか」を扱えるように見えて、Pythonのジェネレータ/イテレータは遅延評価の要件を満たしてはいない。あくまで「遅延評価っぽい何か」を扱えるだけだ、と覚えておくべきだろう。ホンモノの遅延評価には100歩くらい及ばないのである。
とは言ってもPythonのジェネレータ/イテレータはそこそこ面白い。Schemeのストリーム程融通は利かなくても、それなりに楽しく使える機能ではある。
ここではPythonのジェネレータ/イテレータを使った3つ程の簡単な例を挙げてみよう。
1. 無限長フィボナッチ数列
またもやフィボナッチ数列である。
これもネットを検索すればジェネレータを用いた例としてある意味お馴染みだろう。
無限長の長さを持つフィボナッチ数列は、ジェネレータを使えば次のようにして定義可能だ。
def fibgen(a, b):
while True:
yield a
a, b = b, a + b
fibs = fibgen(0, 1)
2. 無限長素数列
以前にも無限長の素数列の実装を紹介したが、ここでは別の実装法を紹介しよう。
その前に朗報がある。Pythonのfilterと言う関数に付いて、だ。
こいつは昨今ではリスト内包表記の影に隠れてしまった。しかし、ジェネレータ/イテレータとの組み合わせでは力を発揮する事が分かった。
>>> [x for x in range(1, 11) if x % 2 == 0]
[2, 4, 6, 8, 10]
>>> filter(lambda x: x % 2 == 0, range(1, 11))
<filter object at 0x7f266c573460>
>>>
上は[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]と言う有限長のリストから偶数だけを選んで返す例である。リスト内包表記の場合はそのままリストを返すが、Python3.0以降の仕様ではfilterはイテラブルを受け取ってイテラブルを返してる。
このfilterの返り値であるイテラブルをリスト化するにはひと手間必要なんで、今だとリスト内包表記に比べると尚更メンド臭い印象になる。
>>> list(filter(lambda x: x % 2 == 0, range(1, 11)))
[2, 4, 6, 8, 10]
>>>
ところが、「イテラブルを受け取ってイテラブルを返す」と言う仕様だと「無限長」を相手にする場合極めて都合が良いのだ。
そう、Pythonのfilterは「無限長のイテラブル」を受け取っても屁ともしない。何故なら返り値は必ず未実行のイテラブルだからだ。
逆にリスト内包表記の場合は、無限長のイテラブルを相手にすると無限ループに陥ってしまう。
例えば、上で定義したintegers_starting_fromをfilterに渡して同じ様に偶数だけ抽出してみよう。
次のように書く。
>>> integers = integers_starting_from(1)
>>> evens = filter(lambda x: x % 2 == 0, integers)
>>>
そして作成したevensと言う変数に__next__()を適用してみる。
>>> evens.__next__()
2
>>> evens.__next__()
4
>>> evens.__next__()
6
>>> evens.__next__()
8
>>> evens.__next__()
10
>>> evens.__next__()
12
>>> evens.__next__()
14
>>>
そう、変数evensは無限長の偶数列になってるのだ。これって凄くないか?
事実上、Pythonのfilterは、むしろSRFI-41のstream-filterに近い実装になっている。まぁ、Pythonの宿命として結果破壊的変更な動作に最終的にはならざるを得ないけどな。
いずれにせよ、これは僥倖だ。
今回はこれを使って無限長の素数列を実装してみよう。今回も上で作ったintegers_starting_fromと言うジェネレータを用いる。
そして、今回、ある意味悔しいけど(笑)、はじめてPythonのイテレータ設計が登場する。
class sieve(object):
def __init__(self, stream):
self.stream = stream
def __iter__(self):
return self
def __next__(self):
try:
head = self.stream.__next__()
self.stream = filter(lambda x: x % head != 0, self.stream)
return head
except StopIteration:raise StopIteration
Pythonのイテレータ設計は基本的にクラス設計と同じだ。ただ、設定するメソッドが特殊メソッドなだけ、である。
ぶっちゃけ、__iter__()なる特殊メソッドが何を意図してるかハッキリしない。どうやらイテレートを始める前での前準備段階を弄る為にあるらしいが、具体的にどう使用するのか、と言うのはPythonのドキュメンテーションをひっくり返して調べてもロクな記述が無いのだ(笑)。
ただ、return selfしてるトコを見ると、このオブジェクト自体をイテラブルとして返す為に取り敢えずそう書いてる模様である。
イテレータとしての本体は__next__()である。ここではPythonの例外機構を使ってみた。
このイテレータ内でイテラブルを「作る」前提ならそうする必要はないのだが、外部からイテラブルを受け取って「加工」するとなると、まずはStopIteration例外を投げてくるのはその外部からやってきたイテラブルになる筈である。
つまり、ここでは敢えて、その引数に与えられたstreamが投げてきた例外をキャッチして、改めてStopIteration例外を投げるカタチにしている。
そして、ここでは受け取った変数headにself.streamのまずは最初の値を消費させてその値を代入する。こいつを計算基準、ないしは返り値として用いるからだ。
例えば[2, 3, 4, .....]と言う無限長の整数値のストリーム(self.stream)を受け取ったとしよう。ここで__next__()を使えばheadには2が代入され、self.streamは[3, 4, 5, 6...]となる。
ここでself.streamを代入しなおす。今、素数を計算してるわけで、当然self.streamからheadである2の倍数を全部除去しなければならない。ここで登場するのがPythonのfilterである。
filter(lambda x: x % 2 != 0, self.stream)
これで、実体化はしないが(filterが返すのはイテラブルな為)、self.streamは2の倍数を除去したイテラブルオブジェクト、[3, 5, 7, ...]になるだろう、と言うのは想像に難くない。これをself.streamに代入するわけだ。
次のイテレートだとheadには3が代入され、self.streamは[5, 7, 9, 11,...]となるだろうし、同じように3の倍数をフィルタリングすれば・・・そう、self.streamはどんどん素数列に近づいていくのだ。
その動作を一般的に記述すれば次のようになるわけだ。
self.stream = filter(lambda x: x % head != 0, self.stream)
そしてheadをreturnすれば良い。headは結果、必ず素数になってるだろう。
ところで、上のイテレータのコードを見て
「あれ?これなら単純にジェネレータでも書けるんじゃね?」
とか思った貴方。僕もそう思った。
ところが、これだと上手く動かないのだよ。
def sieve(stream):
while True:
head = stream.__next__()
yield head
stream = filter(lambda x: x % head != 0, stream)
そう、ロジック的にはこれで構わない筈なのだ。
ところがPython(3.8.5)だとおかしな挙動となる。
>>> primes = sieve(integers_starting_from(2))
>>> primes.__next__()
2
>>> primes.__next__()
3
>>> primes.__next__()
4
>>> primes.__next__()
5
>>> primes.__next__()
6
>>>
え?ウソ、何でやねん、と。
ハッキリ言って挙動を見る限り、Pythonのyieldにまつわるバグだと思うんだけど、今回は届けていない。っつーか、実装上の理由で言い訳されても腹立つだけ、だしな(笑)。
ぶっちゃけ、ロジック通りに動かず「実装上こうこうだから・・・」と言う話は理論でもなんでもないのだ(笑)。フツーのプログラマなら納得するかもしれんけど、俺は納得せんぞ(笑)。実装上の理由は「理論」じゃないのだ。
と言うわけで、このケースだとジェネレータの挙動が「おかしい」のでイテレータを使ったに過ぎない。これがバグとして将来的に直されるのかどうかも分からんのだ。
さて、ここでちょっとしたユーティリティを紹介しようと思う。ジェネレータ/イテレータの先頭から数えて行って、n番目のアイテムを返す関数、stream_refである。
def stream_ref(s, n):
while True:
head = s.__next__()
if n == 0:return headn -= 1
これはジェネレータでも何でもない、単なる関数である。内部的に受け取ったジェネレータ/イテレータの先頭の値を消費しつつ、目的の順番の値になったら単純にそれを返す関数である。
実際は、これもジェネレータ/イテレータの性質に引きづられて破壊的変更を必然的に伴うので、あまり良い実装じゃないかもしれないけど、この程度の実験だとそこそこ役立つユーティリティだろう。
使い方は以下の通り、である。
>>> primes = sieve(integers_starting_from(2))
>>> stream_ref(primes, 50)
233
>>>
これで50番目の素数は233だと言う事が分かる。
気をつけなければならないのは、先にも書いた通り、関数stream_refはPythonのジェネレータ/イテレータの仕様の要求に従ってオブジェクトprimesの破壊的変更を行う。
従って、ここでprimesに__next__()を適用すると、51番目の素数が返ってくるだろう。
>>> primes.__next__()
239
>>>
関数型言語が怖がってるのはこの現象なのだ。とある関数を呼び出して適用した後に、別の事柄を適用したら全く思いがけない結果が返る、と言うのはバグの元なのだ。
3. 無限長乱数列
最後に無限長乱数列の実装を紹介しよう。
これも枠組み自体は非常に簡単で、ハナクソで実装可能だ。
def rand(random_init, rand_update):
while True:
random_init = rand_update(random_init)
yield random_init
広く知られるトコではあるが、コンピュータ上の乱数はホンモノの乱数ではなく、疑似乱数である。実のトコ、「パッと目には分かりづらい」数列になってる、ってのがホントのトコだ。ここで言う数列は本当に数学的な数列である。
上のジェネレータrandは乱数の初期値random_init(シード、等とも呼ばれる初期値)と、実際どんな数列を作るか指定する関数rand_updateを引数とする。要するにジェネレータと高階関数の合わせ技である。
つまり、このジェネレータはあくまで枠組みであり、枠組みだけなら簡単に書ける、と言う証左だ。「どんな乱数にするか」と言うのは決定していなく、それで良いのである。その「決定を後回しに出来る」と言うのが、高階関数の旨味であるのだ。
いずれにせよ、rand_initはrand_updateによって加工され、その値は新しいrand_initになる。枠組みとしては完璧だ。
とは言ってもこのままでは面白くない。そこで、ここでは、数年前に流行った高性能と言われる乱数生成器、Xorshiftを実装してみよう。
さて、実は乱数実装法は色々ある。Pythonの組み込みライブラリであるrandomは、現時点で最高峰と言われる日本製のメルセンヌ・ツイスタで実装されていて、C言語なんかでstdlib.hに入っているrand()なんかより遥かに高品質な乱数を扱う事が出来る。
ただし、メルセンヌ・ツイスタにも欠点がある。こいつは計算が複雑で結構重いのだ。
もちろん、昨今のパソコンで「激重」って言うほど激重ではない。実際Pythonでラクラクと扱えるわけだから・・・ところが、場所によっては極めてクリティカルな乱数実装法である。例えばWebブラウザ上とかな。
Webブラウザだと昨今はどのページを見てもJavaScriptが走りまくっていて、ただでさえクッソ重い状況なのだ。どいつもこいつもページに広告貼りまくって、画像や動画なんかもデフォルトで存在し、広告にはJavaScriptが使われまくりで、黎明期のWebブラウザに比べるとクッソ重い環境と成り果てている。
昨今のWebブラウザだと、技術的には如何に軽く計算が行われるか挑戦が行われており、例えばWebブラウザを仮想マシンと見なして、インタプリタ的にコードを処理するのではなく、一回Wasm(Web Assembly)と呼ばれる一種アセンブリ言語へとコンパイルするような試みまで出てきた。
そう、今ではかつての端末に代わってWebブラウザ自体が一種端末化していて、パソコン自体の性能より、如何にWebブラウザ自体を高速に動作させるか、ってのがハッカーの主戦場となってる模様。
そんなカツカツの実行環境で、メルセンヌ・ツイスタなんぞを優雅に走らせる余裕なんてないのだ。
そんな中で、出てきた新しい乱数生成法がXorshiftである。これはメルセンヌ・ツイスタ程高品質な乱数は生成しないが、実用充分な範疇では「良い乱数」を返してくれて、ロジックも極めて簡単で軽い、と言う特徴がある。計算に排他的論理和とビットシフトしか使わないのである。
Wikipediaに紹介されているXorshiftのウチ、基本の一番上のヤツをPythonで実装してみよう。
これがPythonでのXorshiftである。
ここでもPythonの高階関数、reduceを用いている。
ここでのポイントは、実は受け取るリストが関数、しかも無名関数のリストでも構わない、と言う事だ。
外部から与えられたxは乱数のシードだが、そのシードはそのままreduceのアキュムレータに収まる。そして、そのアキュムレータに、関数リストに入ってる無名関数が先頭から順番に適用されていくのだ。
lambdaだらけでビビるかもしれないが、reduceの第一引数のlambdaは本質的には単純な事しかしていない。
lambda acc, func: func(acc)
funcで受け取ったリストの関数をアキュムレータaccに適用している。つまりfunc(acc)である。これがaccに書き込まれるのだ。そして新しいaccに次のfuncが適用され・・・となっていく。
実際はこの部分は次のように書かれている。
lambda acc, func: func(acc) & 0xFFFFFFFF
このうち、16進数での& 0xFFFFFFFFってのは不可思議な表現でWikipedia版には見られない記述である。
これが実はPythonでは必要で、と言うのも、理論上、Pythonはどんな大きな整数でも扱える。反面Cはそうではない。Cで左ビットシフトすると場合によっては、左の方のビット数値情報(1とか0とか)が消えてしまう。実はこの「ワザとビット情報を消す」のがXorshiftのキモなのだが、生憎Pythonの場合、どこまでも大きな数を保持してしまうのだ。
そこで32bitのメモリを全部1にする0xFFFFFFFFとの論理和を取ると、C言語のように長さは最長でも32bitの範囲に収まるわけだ。これを欠かすとどんどん数がデカくなって乱数らしくならなくなるんだな(笑)。
ちょっとしたハックはこの程度で、あとはWikipediaの例示と同じである。しかしreduceを使った方が・・・要するに事実上Xorshiftをワンライナーで書き上げられて、一々xに代入する、と言う「手続き型言語的な作法」に縛られなくて良くなる。
・・・まぁ、Pythonらしいか、と言われれば異論があるトコもあるだろうが、関数型言語的な作法としては「正しいやり方なのだ」と言っておこう。
では結果を見てみよう。
>>> random_numbers = rand(2463534242, xorshift)
>>> random_numbers.__next__()
723471715
>>> random_numbers.__next__()
2497366906
>>> random_numbers.__next__()
2064144800
>>> random_numbers.__next__()
2008045182
>>> random_numbers.__next__()
3532304609
>>> random_numbers.__next__()
374114282
>>> random_numbers.__next__()
1350636274
>>> random_numbers.__next__()
691148861
>>> random_numbers.__next__()
746858951
>>> random_numbers.__next__()
2653896249
>>>
こういうカンジの乱数列が手に入る・・・・・・まぁ、ちと数はデカいけどね。
実際乱数で使う際は、例えばこの場合、32bitの最大の値、4294967295辺りで割って、1以下の小数にしてしまうみたいだが、まぁ、Xorshiftの基本ロジックの実装は上の通りである。
これでXorshiftに拠る無限乱数列の実装は終わり、である。
幸いな事に、Pythonのジェネレータは、何度も書くが、破壊的変更を伴う実装なのだが、乱数列とは相性が良い。と言うのも、乱数に限って言うと「同じ値が出てくる」のは望ましくないわけだ。関数型言語だと乱数列でさえ基本的に「不変のデータ」としてそこに居座り続けちゃうので、サイコロ代わりに使うのは困ったちゃんなのである。
と言うか、そもそも「乱数生成」と言うのは、実のこと言えば、関数型言語とは相性が悪いのだ(笑)。理論的モデルではどのようにも語れるが、実用的には「ちと待てよ」と言う話に成りかねない。
よってこの件ではPythonの勝ちである(笑)。
とまぁ、今回はPythonのジェネレータ/イテレータを使った面白そうな例を3つ挙げてみた次第である。
※: 厳密にはライブラリではない。Schemeは歴史的に、ロバスト(頑強)ではあるけど、非常に小さなプログラミング言語で、本体は非常に研ぎ澄まされた汎用性の高い極少数のライブラリ関数しか持たない。故に実用的なプログラムが書けないのだ。
SRFIと言うのはScheme Requests for Implementationの略で、訳せば「Schemeにこんな機能があったらいいな要求集」である。つまり、仕様の範疇外で「こんな機能があったらいいな」と言う要求の纏めである。そのまんまだ。
従って、これは「外部ライブラリ」ではなく、Schemeの実装者が自分の作った実装に「この機能は取り込んだ方が良い」と選んで付け加える為の仕様集なのである。この時点だととある実装に取り込んだ機能は他のSchemeで同じ機能があればその部分だけは限定的かつ相互に「互換性」が生じるわけだ。
一方、「要求仕様集」なので、いわゆるライブラリのように「その言語で書かれたユーティリティ」ばっかではなく、言語実装の根幹に関わる、内部的な要求もチラホラある。例えばUNIX時と言われる日付や時間に関する実装はScheme上で実装は出来ないので、内部的にOSとやり取りせなアカン非常に血なまぐさい話としてこの「要求仕様集」には含まれているのである。
