続・話すようにプログラムするPythonチュートリアル
話すようにプログラムするPythonチュートリアル - なんたらノート 第二期の続きです。前回は努力と根性でどうにかなるところまでやりました。今回は、前回再び泥臭いコードになってしまったプログラムを、もっと綺麗にしてみようと思います。
前回はできるだけ一般的な言葉で説明してみました。今回は、既存の概念とそれに対するよりPython的な方法を説明します。前回が知恵と根性なら、今回は知識の力を借りよう、という感じ。標準には含まれていませんが、とても便利なのでPythonデコレータが熱い - なんたらノート 第二期で紹介した、decoratorモジュールも活用します。
デコレータで本質/属性の分離
Python2.4から、デコレータ記法が増えました。例のdefの前の@です。以前から、「関数を入力して関数を出力する関数を使って、既存の関数を書き換える」というトリック（デコレータの本質はコレ）はありましたが、ちょっと面倒で、なかなか素直な発想が出てきませんでした。@が増えた2.4以降でも、その本質はあまり変わりませんでした。そこで、decoratorモジュールです。
前回のこれを見てください。3行のコードのうち、本質部分と非本質部分を一目で見分けることができるでしょうか？
tests = 0 def is_mod_zero(n, m): global tests tests += 1 return n % m == 0
たしかこれは、剰余ゼロ判定に判定回数をカウントする機能を埋め込んだものでした。そのような、意味づけや使われ方を考えたうえでないと、正しく読めません。
そこで、こんなデコレータを準備します。実際に剰余計算をする部分以外を実装し、それをデコレータとして使えるようにしたものです。
from decorator import * tests = 0 @decorator def testcount(f, *args, **kw): global tests tests += 1 return f(*args, **kw)
さてそうすると…
@testcount def is_mod_zero(n, m): return n % m == 0
見事、意味と実装コードがぴったり一致しました。パフォーマンスチェックが不要になったら、defの前の@の行を取り除くだけです。
コール回数を数えるということと、やりたい計算そのものとは、本質的に異なります。それらを関数レベルで完全に疎結合に実装しておき、比較的簡単に組み合わせられるのが、関数を取り回せる言語のいいところです。JavaやRubyのような、堅い手続き型言語の発想だと、もっと大げさな方法を取るか、行と行の間にデバッグコードを注入するしかないように思えます。いっぽう基本が関数言語なPythonは、JavaScriptやLISPのようなもので、関数そのものを自然に組み合わせることができます。しかも、いくらか読みやすい書き方で。
引数の部分適用(カリー化)
Python2.6には、Python3000を先取りしたwith構文を使う機能が盛り込まれています。新しい構文もいいのですが、それ以前に、Python2.5から標準となったfunctoolsを使って、「引数の部分適用」を活用することも考えましょう。
前回、「剰余ゼロとなるものが存在するか」をあらわすために、exists(tester, iterable) というインターフェースの関数を設け、そこにテストする関数を与えました。
return not exists(lambda m: is_mod_zero(n, m), prime_numbers_until(n-1))
普通、関数の実装には、パラメータとローカル変数しか使われませんが、このlambdaは、定義場所のスコープにある変数nを使っています。日常的に見るパターンなので、普段はあまり気になりませんが、よく考えると、lambda式が返すものの正体が関数だという点で、普通じゃないことが起こっているのに気づきます。そう、クロージャですね。
ただでさえごちゃごちゃしていて、そのうえクロージャまで意識するとなると、後を引き継いだ人に本当に読んでもらえるか、少し不安になります。
やりたいことは何でしょう？それは「引数を2つとる既存の関数を、その関数の最初の引数を固定したバージョンに変換」したいということです。つまり引数の部分適用ということ。
from functools import * return not exists(partial(is_mod_zero, n), prime_numbers_until(n-1))
もろ、「部分適用」という言葉どおりの表現になりました。
関数という「自由なロジックをあらわすパラメータ」を使うことで、無限の可能性を持つ関数を、高階関数と呼びます。引数として渡す関数のインターフェースに制約が課せられる、mapやfilterなどの高階関数に対しては、目的の処理をあらわす関数を状況に適合するようにラップした新たな関数を渡す必要があります。JavaScriptやRubyと比べて、より端的さを必要とする(でないとインデントが大変なことになる)Pythonの場合、複雑な記述を増やすより、関数をはじめからpartialに対応できる設計(手前から順に部分適用されることを想定)にしておき、式ですませるのが適切なアプローチだと思います。
遅延評価とイテレータ
これは前回、最後のおまけでやりかけていましたね。「それ未満のすべての素数」が増えてくると、すべて使わないかもしれない(2や3で素数じゃないと判別できてしまうかもしれない)のに、毎回コピーしていたらメモリがもったいない。ということで、ジェネレータを定義してイテレータを作成させました。
yieldを持つdefを書くだけで、ジェネレータというイテレータ生成機が書けるのは、とても便利です。が、それとて、やはり構文のネストのために「端的さ」を欠いてしまう要因となります。もっと一般化する方法はないかを考えましょう。
そこでitertoolsモジュールを導入ます。itertoolsには、map/filter/reduceなど、シーケンス的なオブジェクトを扱うビルトイン関数群に対応した、そのイテレータバージョンが定義されています。データ量がよっぽどのときしか使わないだろうって？いやいや、それらはストリーミングだけに使うわけではなく、遅延評価にも大いに役立ちます。じっさい、ジェネレータより簡単ですよ。実例を見てみましょう。
def prime_numbers_until(limit): return filter(is_prime_number, range(2, limit))
任意の数以下の素数列を返すprime_numbers_until関数、この例題の肝になるヤツです。（引用は前回の途中経過版から）
これをジェネレータで遅延実行に対応しようとすると、こうなります。
def prime_numbers_until(limit): for n in xrange(2, limit): #rangeもついでにイテレータに if is_prime_number(n): yield n
これに対して、「filterと同じ要領で、代わりにイテレータを返す」をそのまま書くためにitertoolsを導入すると、こんな感じです。
from itertools import * def prime_numbers_until(limit): return ifilter(is_prime_number, xrange(2, limit))
オリジナルとほとんど変わっていませんね。せっかくいい表現ができたので、最終的にこの記述を活かせるように考えていきましょう。
たしかに、itertoolsはジェネレータで説明できます。が、逆説的にいえば、ジェネレータとは、itertoolsの固定機能の代わりに、どうしてもカスタム手続きが必要な場合に使うもの、と考えることもできます。そのぐらいのつもりで、使えるときは積極的にitertoolsを使うのがPython的です。
さらに、この遅延評価のためのitertoolsを使えば、
def exists(tester, collection): for e in collection: if tester(e): return True return False
と定義したユーティリティ関数existsも、
from itertools import * def exists(tester, iterable): return any(imap(tester, iterable))
となります。
anyはPython2.5で増えたビルトイン関数で、ある集合の要素のいずれかがTrueの場合、Trueを返すというもの。つまり、「一人でも合格ならみんな合格」をイテレータでやるための関数です。
ここ、mapではなくimapなのがミソです。
ビルトインのmapを使っていては、anyは生きてきません。なぜなら、mapは要素をすべてスキャンし、新たなシーケンスを作ってしまうからです。既存の集合から、TrueとFalseでできた同じ要素数の集合を作り直すというのは、無駄にメモリを食ううえに無駄な計算が発生しますね。itertools.imapを使って遅延評価すれば、最初に出てきたTrueの時点以降のチェックは行われません。imapのおかげで、書き換え前のexistsの手続きと、まったく同じ計算コストでありながら、手続きを宣言にできるのです。
※ちなみに私、2.5でネイティブにall/anyが追加されたことに今日気づきました。知らずに自分で定義していた。気づくの遅っ(^^;
2.4の方は、anyを自分で定義しておきましょう。
def any(iterable): for e in iterable: if e: return True return False
ちょっと休憩
すこし賢くなってきました。自分の直感で気づいたものに、実は名前がついているんだと知ると、次からはもっと一般化して考えられますね。よくデザインパターンの人がいう、パターンの恩恵です。基礎のドリルと定理の勉強をきっちりやるだけでも、それと同じ恩恵は得られるんじゃないでしょうか。
よく、「車輪の再発明をするな」と言われますが、そもそも、「なんとかして上手に荷物を移動させたい」という動機と、そこから生まれる最初の工夫(たとえば、テコを使うとか、ころに乗せるとか)があればこそ、「車輪」の意味がわかるというものです。はじめから「車輪」という名前しかしらなければ、その本質的な概念にたどり着けない、もしくは、理屈だけで身につかないと思うのです。
「きみ、これからはJavaよりRubyがいいらしいよ」
「MVC等のデザインパターンを学んでください」
「一気に憶えるPHP4大フレームワークの使い方!!」
…みたいな。
「オレ、いつまでも使える"ころ"を考えたよ」と、「あ、これは車輪と言うのか」の両方を体験することが大事だと思います。そのバランスが取れた瞬間にのみ、プログラマーは成長できると思うのです。いつまでも努力と根性でもだめだし、かといって、いきなり不相応なパラダイムを勉強してもだめだし。それらがアンバランスだと、成長はぴたりと止まってしまうんじゃないか、と私は思います。成長し続ければいつか、もしかしたら、車輪ではなくキャタピラを発想できるかもしれません。
参照透過性とメモ化
次はメモ化についてです。これも、前回やったことに名前をつけたにすぎません。そう、最後の重要転換ポイント、やろうとしている本質の特性に発見した、あの普遍性です。
そもそも、ある数が素数であるか否かは普遍だ。絶対に変わらない。ただ、数論屋さんじゃない人は、最初にあまり大きな素数を知らないだけ。でも人間には記憶がある。どの数が素数なのかは、いちど知れば二度と考える必要はない。たとえば、53は素数だけど、57は素数じゃない、なんてのは、最初は知らなくても、知ってしまえば考える必要はない。
実装コードがどうなっていようと、「素数かどうかを判定する関数」はかならず、入力に対して同じ答えを返すはずです。入力に対して出力が保障される関数には、「参照透過性」があるといいます。
参照透過性のある関数がもし高コストで、かつ、何度も評価されるのなら、以前計算したことがある値を記憶から出してくるようにすることで、同じ計算を2回以上行うのを避け、パフォーマンスの抜本的な解決につながることがあります。
…って、これ、前回専門用語ぬきでやったのと同じことでしょう？でもこれ、実はもう少し続きの説明があります。
本質的には参照透過性のない言語において、このような「引数に対応する戻り値の記憶」を行うことを「メモ化」と呼びます。メモ化は、関数をひとつの単位として考えるのが特徴です。なぜなら、参照透過であることを絶対的に保証できるのは、関数の境界だからです。
というわけで、関数を境界としてメモ化を考えることにしましょう。どう実装しようかな〜っと思いきや、こちらをご覧あれ。
http://www.phyast.pitt.edu/~micheles/python/documentation.html#memoize
超綺麗な実装！そのまま読んで意味がわかるし、ほぼそのまま使えるぞ。ちょっと面倒なところを短く変更したものがこちら。
@decorator def memoize(func, *args): if not hasattr(func, "memoize_dic"): setattr(func, "memoize_dic", dict()) dic = getattr(func, "memoize_dic") if args in dic: return dic[args] else: result = func(*args) dic[args] = result return result
さて、こいつをそのまま「ある数が素数であるか否かは普遍だ」に適用してみよう。言葉どおりの理屈で考えれば、本来このメモ化の工夫をすべき関数は、素数判定の関数そのもの、「ある数」をキーに、「素数かどうか」をメモにするべきだ。そうすると、前回再帰で大変なことになったあの関数
def is_prime_number(n): return not exists(lambda m: is_mod_zero(n, m), prime_numbers_until(n-1))
は、こんなふうに表現できる。
@memoize def is_prime_number(n): return not exists(partial(is_mod_zero, n), prime_numbers_until(n-1))
デコレータ付けただけ。嘘みたいだけどホント。
ちょっと考えてみよう。さっき定義した遅延評価版の prime_numbers_until は is_prime_number を使っている。is_prime_number はそのままだと、prime_numbers_until(n-1) を呼び出すので、再帰回数が級数的に増大するはずだ。が、is_prime_number の入出力はメモ化されているため、未知の素数が登場しないかぎり、実装コード上の式が評価されることはなく、prime_numbers_until はコールされない。ところで、prime_numbers_until に渡す引数 n-1 から読み取れるように、未知の素数を求めるには「既知の素数」しか必要がない。…あ、これ、まったくスキないよね。prime_numbers_until のほうに手を入れてメモ化をどうしようかと考えずとも、十分に動くんじゃないだろうか。
まとめ
まとめて書くとこうなる。さあ、思い通りに動くか、動かしてみよう。
myutil.py
from decorator import * from itertools import * def exists(tester, iterable): return any(imap(tester, iterable)) @decorator def memoize(func, *args): if not hasattr(func, "memoize_dic"): setattr(func, "memoize_dic", dict()) dic = getattr(func, "memoize_dic") if args in dic: return dic[args] else: result = func(*args) dic[args] = result return result
primenum.py
from decorator import * from functools import * from itertools import * from myutil import * tests = 0 @decorator def testcount(f, *args, **kw): global tests tests += 1 return f(*args, **kw) @testcount def is_mod_zero(n, m): return n % m == 0 @memoize def is_prime_number(n): return not exists(partial(is_mod_zero, n), prime_numbers_until(n-1)) def prime_numbers_until(limit): return ifilter(is_prime_number, xrange(2, limit)) print list(prime_numbers_until(100)) print tests
剰余計算回数は409回。OK、パフォーマンスは良好だ。デバッグコードを消してもう少しまとめよう。
from decorator import * from functools import * from itertools import * from myutil import * def is_mod_zero(n, m): return n % m == 0 @memoize #メモ化 def is_prime_number(n): # それ未満の素数のいずれにも割り切れるものがなければ素数である return not exists(partial(is_mod_zero, n), prime_numbers_until(n-1)) def prime_numbers_until(limit): # 素数かどうかを条件に、2から任意数までの数列を遅延評価でフィルタして列挙する return ifilter(is_prime_number, xrange(2, limit)) print list(prime_numbers_until(100))
まさに、話すようなプログラムコードが完成しました。もしどうしても、xrange(2, limit)に対して空回りの回数が多いことが気になる方は、前回のように、prime_numbers_untilの手動メモ化もどきをやってみてもいいかもしれません。今回は可読性を優先して、ここで完了とします。
今回、精神力だけでは乗り越えられなかったであろう壁を、知識の力を借りて越えました。そのおかげで、「仕様を端的に表す、話すようなコード」という真の目標に到達できました。知識だけでは何もできませんが、何かやりたいとき、知識の力はなくてはならないほどの威力を持つものだということがポイントです。
文法と辞典だけでは、いくら度胸があっても、外国語をスムーズに話すことはできません。文法を駆使してなんとか文章にしたつもりでも、ネイティブスピーカーからはおかしな表現に聞こえます。それよりたぶん、非ネイティブ同士が会話すると、ぜんぜん理解し会えないでしょう。それと同じように、プログラム言語で会話をするのも、やっぱり、文法と辞典だけではうまくいかないと思います。外国語を上手く話すには、その国の言葉が持つ、辞書にない意味を感覚で理解し、より多く知ることが重要です。プログラムもまた、言語の構文要素や用語に込められた意味を、経験を通じて理解し、ボキャブラリを増やすことで、より上手く話せるようになります。
勉強しないといけないの？練習しなくちゃいけないの？はい、そのとおり。
精神力は最初の「できた」に到達する近道だけど、毎回安定して発明ができるほど強靭じゃない。だから、毎回精神力で乗り越えるよりも、むしろ身に染み付いた知識を持っていたほうが、精神力をより本質的な問題に集中させることができ、より良い結果が得られる。…と、私は思います。少なくとも、「車輪」の意味が理解できる程度の訓練をしたうえで、ね。
