Hatena::ブログ(Diary)

西尾泰和のはてなダイアリー

2010-08-27

Pretty Print 2

前回論文のリンクを張り忘れていたので: http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf

今朝の電車で試しに実行してみたら、おしい、カンマを忘れるの構文エラーが1つあった!まだまだ精進が必要ですな。

で、実行してみると案の定書いておいたraise NotImplementedErrorに引っかかったのであった。元論文の型クラスDOCに相当するものをPythonの空クラスADocを作って継承させたけど、そのクラスを使った型チェックをする前にまずはraise NotImplementedErrorでxが期待したクラスになっていないわけなんだからそれを表示して観測するべきだな、と修正。直前がUnionの時に期待と違うわけだな、とその箇所を眺めたら

     if isinstance(y, Union):
         return better(w, k, 
-                      be(w, k, [(i, x)] + z),
-                      be(w, k, [(i, y)] + z))
+                      be(w, k, [(i, y.x)] + z),
+                      be(w, k, [(i, y.y)] + z))

これか。元の論文ではDOCとDocを区別していたり、xって変数のある内側のスコープで別のxって変数を使ったりしてて、さすがにそういうのはどうかなぁと思いつつ「変数の名前の付け替えをするのはリファクタリングだから動いてテストを書いてから」とぐっとこらえてるナウ。

あと2箇所同じようなミスがあって、1箇所カッコのつけ方が間違っているのがあった。修正。テストも書いたよー

>>> pretty(10, Text("a"))
'a'
>>> print pretty(10, fillwords("a b c d e"))
a b c d e
>>> print pretty(5, fillwords("a b c d e"))
a b c
d e
>>> print pretty(3, fillwords("a b c d e"))
a b
c d
e

うむうむ、少なくとも基本的な機能に関してはちゃんと動いているな。今日の帰りはテストのカバレッジを100%にして、それでまだ時間があったらリファクタリングを始めるとしよう。

coverageを使う

http://pypi.python.org/pypi/coverage/2.6/

$ coverage run prettyprint.py
$ coverage html

まあ僕は面倒なので

$ coverage run prettyprint.py && coverage html

とやるのだけど。これをやるとこんなふうになる

f:id:nishiohirokazu:20100827215641p:image

カバレッジで覆われてないところのテストを書く。あー、でも最後のraise NotImplementedErrorとかは、うっかりミスをしたときにすぐ気づくように付けてあるもんであって普通は到達しないんだよな。わざと到達させるのも馬鹿らしい。

http://nedbatchelder.com/code/coverage/excluding.html

http://nedbatchelder.com/code/coverage/config.html#config

お、プロジェクトディレクトリに設定ファイル .coveragerc を置いて、正規表現で「これが含まれていたら無視しろ」って書けるらしい。例に、まさにraise NotImplementedErrorを無視するのが書いてあった。

    # Don't complain if tests don't hit defensive assertion code:
    raise AssertionError
    raise NotImplementedError

やったー、100%になったよー!

Pretty Print 3

カバレッジが100%になるようにテストを書いたらfillにバグがあることに気づいた。xsとzsを間違えて無限ループになってた。名前ひどい。

色々変数名の変更とかリファクタリングを実行。テストが100%だと安心だ。テスト重要。

そしてようやくAUTOASTの作るS式をきれいに表示する方に着手。しかしpretty printが必要な規模だと数秒掛かる。あー、そうか、元のコードはHaskellだからか。遅延評価で書かないといけないな。逐語訳中にはリストや文字列の結合が遅いのではないかと思ってコメントにそう書いていたが、そんなもの以上の問題があったわけだ。

0 1 2 3 4
5 6 7 8 9
10 11 12
13 14 15
16 17

real	0m4.189s

高速化をするときにはまずプロファイリングをしないといけない。

http://gist.github.com/553325

ふむ。なんかものすごい階数呼ばれている関数が幾つかあるなぁ。でもその中で一番時間を食っているのはbeか。beがなんでそんなにたくさん呼ばれるのかを考える。

    if isinstance(y, Union):
        return better(width, already, 
                      be(width, already, [(i, y.x)] + tail),
                      be(width, already, [(i, y.y)] + tail))

犯人はお前か!!

遅延評価させた: http://gist.github.com/553321

おお、5秒かかっていたのが1ミリ秒くらいになった!めでたしめでたし!


ところでもっと大きな構造について試してみたら再帰呼び出し回数の上限オーバーで死んでしまった。まあ、末尾呼出の最適化をする言語のコードを移植したらそりゃそうなるわな。beの大部分のコードがreturn be(...)なので、これはループに変換されるべきってこったな。明日時間があればそれをやろう。