Python で書く代数 - pyarith よ, 私は帰ってきた

1年ぶりの pyarith の記事です. 実は Python で書く代数 を書いてから, 追加した実装があるのでそれについて書きます.

書いてあること

  • pyarith のおさらい
  • 環について
  • 環の公理とテストケースの対応

おさらい

pyarith とは Python でどこまで代数的対象が表現できるかの実験ライブラリです. Python コードは読めるけど代数学のことは知らない人に, 代数的概念を説明することを目的としています. 今のところライブラリとしての実用性は目指していません. おそらくパフォーマンスも出ません.

前々回の記事 で「群」の解説をし, 前回の記事 で群であることを確かめるテストについて解説しました. このテストでは pytest というライブラリを使用し, パラメータ化されたテストを行いました.

この記事を書いたおかげで pytest に興味を持ってくれた人もいたようで, ちょっと嬉しいです.

前回扱ったのは「群」という概念でしたが, 今回は「環」を取り上げます.

群はある規則を満たす集合でした. 環は, 群にさらに満たすべき規則を追加した集合です.

群と環にどんな差分があるかは環を実装した Ring クラスの実装を見てみましょう. https://bitbucket.org/cocoatomo/pyarith/src/dfbb010c50390e5dece00b92558a5c3461199507/tests/test_ring.py ここから分かるのは「環は群に無い __mul__ というメソッドを持つ」ということです.

この Ring クラスと __mul__ というメソッドに課せられた制限はテストケースで表すのでした.

テストケースとその意味
test_mul_welldefined_right 右からの乗算が well-defined であること
test_mul_welldefined_left 左からの乗算が well-defined であること
test_ONE (乗法に関する) 単位元の存在
test_mul_ONE 単位元の性質
test_mul_associative_law 乗法の結合律

乗法は可換とは限らない演算なので, 可換性に関するテストはありません.

また加算と乗算が両方登場する性質を表すテストケースとして以下のものがあります.

テストケースとその意味 (2)
test_distributing_law 分配法則

小学生の頃に分配法則という言葉が出てきましたが, 当時はここまで重要な性質だとは思いませんでした.

環の公理一覧については http://ja.wikipedia.org/wiki/%E7%92%B0_(%E6%95%B0%E5%AD%A6) を参照してください.

pip と Python 3.3

以下, メモレベルで.

発端

「Python3 で Sphinx って使えるんだっけー?」と思って, 試しにインストールしてみたときに気付いた. Jinja2 を pip でインストールするときに, 不思議なエラーが出る. インストール自体は成功する.

やりとり

清水川さんと色々やりとり

というわけで, distribute の easy_install 使って入れてみたら, さっきのエラーは出ずに無事インストールできた.

原因がさっぱり予想付かなかったけど, 稲田さんによるとこんなことらしい.

pip けっこう過激な対応してますね……

(追記 2013/02/16 22:50) この点について稲田さんが Pull Request を作成しています → https://github.com/pypa/pip/pull/810

distribute じゃなくて pip 使ってる理由は uninstall コマンドが使えることなんだけど, また清水川さんから教わる.

easy_install で入れたものが, pip freeze -l でも認識されてるし, pip uninstall でもちゃんと egg を消してくれた.

venv

venv + distribute での Shpinx のインストールを試す (予定)

Heroku 上の Django アプリで django_session が溢れた

ある日 HHTQA が 500 を返して動かなくなってた.

$ heroku logs

の末尾にあやしいメッセージが.

OperationalError: (1142, "INSERT command denied to user 'user'@'hostname' for table 'django_session'")

MySQL の権限が変わるわけがない (ClearDB という add-on なので, ユーザとかは俺はいじれない) し, MySQLWorkbench では同じユーザで見れているので, 権限が根本原因ではない.

MySQLWorkbench で色々見てみると django_session というテーブルが肥大化している. テーブル名や expire_date というカラム名から, 明らかに不要なデータが溜まっている.

SELECT count(*) FROM django_session; -- 15677

このテーブル名で検索すると https://docs.djangoproject.com/en/dev/topics/http/sessions/?from=olddocs/#clearing-the-session-table という情報が見付かり, 手作業で削除することもできるそうだ.

heroku コマンド使って, Heroku 上の環境で削除操作を行った.

$ heroku run find / -name django-admin.py
Running find / -name django-admin.py attached to terminal... up, run.1
find: `/proc/tty/driver': Permission denied
find: `/proc/1/task/1/fd': Permission denied
find: `/proc/1/task/1/fdinfo': Permission denied
find: `/proc/1/fd': Permission denied
find: `/proc/1/fdinfo': Permission denied
find: `/lost+found': Permission denied
find: `/etc/ssl/private': Permission denied
/app/.heroku/venv/bin/django-admin.py
/app/.heroku/venv/lib/python2.7/site-packages/django/bin/django-admin.py

$ heroku run .heroku/venv/bin/django-admin.py cleanup
DJANGO_SETTINGS_MODULE が無いと怒られるので設定.

あくまでモジュール名. ファイル名ではないので注意.
$ heroku config:add DJANGO_SETTINGS_MODULE=settings
$ heroku run ls '$DJANGO_SETTINGS_MODULE'
確認
$ heroku run .heroku/venv/bin/django-admin.py cleanup
SELECT count(*) FROM django_session; -- 1933

予想通り django_session テーブルが小さくなったので, Heroku アプリを再起動.

$ heroku restart
$ heroku logs

まだ何かエラーが出る. 以下 heroku logs の結果.

2012-07-14T12:52:29+00:00 heroku[web.1]: Starting process with command `python manage.py run_gunicorn 0.0.0.0:33646`
2012-07-14T12:52:30+00:00 app[web.1]: Unknown command: 'run_gunicorn'
2012-07-14T12:52:30+00:00 app[web.1 ...

Heroku の動作変更? Django の DATABASES 設定でコケた

以前 この記事 で書きましたが, Heroku の上で OSQA という Django アプリを動かしました.

最近また Heroku に静的ファイルを追加するため, git レポジトリにファイルを追加し, Heroku に再デプロイ (git push) しました.

これでアプリが再起動され, 無事動くはずだったのですが, Internal Server Error が出てしまいほとほと困りました.

heroku logs で見てみると不可解なことに, 使ってないはずの PostgreSQL に接続しようとしてエラーになっています.

2012-06-10T04:04:13+00:00 app[web.1]: /app/.heroku/venv/lib/python2.7/site-packages/gunicorn/glogging.py TIME: 2012-06-10 13:04:13,215 MSG: glogging.py:exception:143 Error handling request
2012-06-10T04:04:13+00:00 app[web.1]:   File "/app/.heroku/venv/lib/python2.7/site-packages/gunicorn/workers/sync.py", line 99, in handle_request
2012-06-10T04:04:13+00:00 app[web.1]:     respiter = self.wsgi(environ, resp.start_response)
2012-06-10T04:04:13+00:00 app[web.1]:   File "/app/.heroku/venv/lib/python2.7/site-packages/django/contrib/staticfiles/handlers.py", line 68, in __call__
2012-06-10T04:04:13+00:00 app[web.1]:     return self.application(environ, start_response)
2012-06-10T04:04:13+00:00 app[web.1]:   File "/app/.heroku/venv/lib/python2.7/site-packages/django/core/handlers/wsgi.py", line 250, in __call__
2012-06-10T04:04:13+00:00 app[web.1]:   File "/app/.heroku/venv/lib/python2.7/site-packages/django/core/handlers/base.py", line 45, in load_middleware
2012-06-10T04:04:13+00:00 app[web.1]:     self.load_middleware()
2012-06-10T04:04:13+00:00 app[web.1]:     mod = import_module(mw_module)
2012-06-10T04:04:13+00:00 app[web ...

Python で書く代数 - pytest で test class 編

前回 は pytest を使ってパラメータ化されたテストを実行しました.

実際に使ったテスト対象コードは, 群を Python で実装したコードでした. ABC モジュールと pytest によるテストを使って, 代数の公理的な定義を擬似的に表現しました.

ただし前回のテストコードではテスト関数が多く, 分類したい気持ちになってきます.

pytest のドキュメント を眺めると, 2.4.5 Parametrizing test methods through per-class configuration にクラスを使ってテスト関数をまとめる方法が書いてあります. 早速これを使います.

test hook

ここで使用するのはテストの前に実行される pytest_generate_tests 関数です. この関数でテスト実行前に, モジュールの中にあるクラスとそのメソッドからパラメータ化されたテストを生成しています.

def pytest_generate_tests(metafunc):
    """Collect and parameterize classes in this module as test cases.

    This test-case collecting function ignores module level functions.

    c.f. 2.4.5 Parametrizing test methods through per-class configuration
    """

    if metafunc.cls is None: # ignore module level functions
        return
    funcarglist = metafunc.cls.params[metafunc.function.__name__]
    argnames = list(funcarglist[0])
    metafunc.parametrize(argnames, [[funcargs[name] for name in argnames]
                                    for funcargs in funcarglist])

テストクラスには, テストコードを記述した関数をメソッドとして記述します.

class TestEquality:
    params = {
        'test_equals_reflexive_law': single_params,
        'test_equals_symmetric_law': double_params,
        'test_equals_transitive_law': triple_params
        }

    def test_equals_reflexive_law(self, a):
        assert a == a

    def test_equals_symmetric_law(self, a, b):
        if a == b:
            assert b == a

    def test_equals_transitive_law(self, a, b, c):
        if a == b and b == c:
            assert a == c

パラメータ化されたテストを実装するためにテストクラスには仕掛けが施されています. その仕掛けは params というクラスフィールドで, テストメソッドとそれが使用するパラメータの対応付けが辞書で設定されています. params 辞書の値は辞書のリストになっていて, 個々のテストケースが列挙されています.

single_params = [{'a': a} for a
                 in integer_values +
                 rational_values +
                 intint_values]

(ここでは single_params の書き方だけを載せましたが, モジュール全体は BitBucket のレポジトリ を参照してください)

前回の pytest.mark.parametrize デコレータとはパラメータ値の指定の方法が異るので注意してください.

pytest_generate_tests やその引数 metafunc の裏側については, また調べてブログに書くことにします.

それでは.

OSQA on Heroku

processes

$ mkdir osqa
$ cd osqa

$ brew install mysql
$ unset TMPDIR
$ mysql_install_db --verbose --user=`whoami` --basedir="$(brew --prefix mysql)" --datadir=/usr/local/var/mysql --tmpdir=/tmp
$ mysql.server start
$ mysql -uroot
mysql> CREATE USER 'osqa'@'localhost' IDENTIFIED BY '***';
mysql> CREATE DATABASE osqa DEFAULT CHARACTER SET UTF8 COLLATE utf8_general_ci;
mysql> GRANT ALL ON osqa.* to 'osqa'@'localhost';

$ svn co http://svn.osqa.net/svnroot/osqa/trunk .
$ virtualenv venv --distribute
$ source ./venv/bin/activate
$ pip install South django==1.3 django-debug-toolbar mysql-python markdown html5lib python-openid gunicorn
$ cp settings_local.py.dist settings_local.py

$ emacs settings_local.py
import os.path
import os
import sys
import urlparse
...
↓消す
DATABASES = {
...
↓heroku 用の DB 設定を追加
# Register database schemes in URLs.
urlparse.uses_netloc.append('mysql')

try:

    # Check to make sure DATABASES is set in settings.py file.
    # If not default to {}

    if 'DATABASES' not in locals():
        DATABASES = {}

    if 'CLEARDB_DATABASE_URL' in os.environ:
        url = urlparse.urlparse(os.environ['CLEARDB_DATABASE_URL'])

        # Ensure default database exists.
        DATABASES['default'] = DATABASES.get('default', {})

        # Update with environment configuration.
        DATABASES['default'].update({
            'NAME': url.path[1:].split('?')[0],
            'USER': url.username,
            'PASSWORD': url.password,
            'HOST': url.hostname,
            'PORT': url.port,
        })
        if url.scheme == 'postgres':
            DATABASES['default']['ENGINE'] = 'django.db.backends.postgresql_psycopg2'

        if url.scheme == 'mysql':
            DATABASES['default']['ENGINE'] = 'django.db ...

Python で書く代数 - pytest 編

テストについて

前回は群を Python で書いてみました. 群は公理というルールを使って定義されていました. この公理を Python で表現するのに, テストが使われていました.

Python でのテストと言えば unittest や nose が有名ですが, pytest という新しいテストライブラリのことを知ったので, これを使ってみました.

この pytest の大きな特徴はテストメソッドで使用する値を簡単にパラメータ化できることです.

人間がテストケースを考える場面では, ただ闇雲に適当な値を渡すのはテストとしては良いものではありません. とりあえずで値を列挙すると無駄な意味の無いテストケースを作ってしまうことが多く, テストの実行自体に時間がかかります. そしてエラーが起きたとしても, そのエラーがいったいどんな原因によって起きたのか考えないといけません. (個人的にはあまり頭を使わず安直にエイヤというのは好きではないです.)

ランダムな値を渡す手法は fuzzing と呼ばれていて, 人間がテストケースを想定する範囲の外にあるバグを見付けるのに使われるそうです. 詳しくはこのスライド http://www.slideshare.net/TokorotenNakayama/fuzzing-pyfes を見ると良いと思います.

群の公理は「群の任意の元」という表現を含んでいるため, 具体値を使用するテストでは無限の時間が必要になってしまい, 全てをテストすることは不可能です. なので, 今回の Group クラスのサブクラスのテストとしては, パラメータ化されたテストで特殊値の付近だけをテストすることにしました. 例えば, Integer クラスでは整数を表現しているので特殊値として 0 があります. 0 の付近の値でテストが通れば, 高い確率で他の値でも動くものと期待できます.

pytest によるテスト

pytest は easy_install もしくは pip コマンドでインストールできます. ここでは virtualenvwrapper を使って, pytest という名前の個別の環境にインストールしています.

pip, virtualenv, virtualenvwrapper についてはこの記事 http://d.hatena.ne.jp/rudi/20110107/1294409385 に詳しく載っています. そちらを参照してください.

$ echo $VIRTUALENV_USE_DISTRIBUTE
True
$ mkvirtualenv pytest
(pytest)$ pip install pytest

テストケースの実行は pytest コマンドで行います.

$ pytest tests/grouptest.py

pytest にテストケースとして認識させるには, メソッドの先頭を test にすれば良いようです. ここは nose などと仕様を合わせているようです. (ドキュメントには明記されていなかった気がしますが.)

肝心のテスト関数にパラメータを渡すところはデコレータを使用して以下のように書きます.

@pytest.mark.parametrize('cls', groups)
def test_ZERO(cls):
    cls.ZERO
    return True

pytest.mark.parametrize の第1引数にはテスト関数の引数の名前を, 第2引数にはテスト関数に渡す値の list を入れます. この list の部分を generator で書いてしまうとエラーが出て, テストが実行できません. どうやら pytest が最初にテストケースをカウントしていて, 長さが測れるものでないといけないようです. 最初エラーメッセージの意味が分からず, 長いことハマっていました.

複数の引数を持つテスト関数を書く場合は以下のようにします.

integer_values = [Integer(i) for i in range(-2, 3)]

@pytest.mark.parametrize(
    ('a', 'b'),
    [(a, b) for a in integer_values for b in integer_values]
)
def test_equals_symmetric_law(a, b):
    if a == b:
        assert b == a

第1引数が tuple になり, パラメータの値も tuple になっています.

今回使用したテストコードの完全なソースコードは https://bitbucket.org/cocoatomo/pyarith/changeset/08e381828aeb#chg-tests/grouptest.py を参照してください.

過去のリビジョンの URL を張っているのは, 実は現在は別の形式にしているからです. その話はまた次の記事で書こうと思います.

まとめ

この記事では pytest を使ってテスト関数の引数をパラメータ化し, そこに入れる値をリストとして書きました. これによって同じテスト関数を色々な値で実行できるようになりました.

pytest にはまだまだ機能があるので, 興味がある方は本家のドキュメントを読んでみてください.

Python で書く代数

代数は数学の中でもプログラミング言語と近しい存在です. 歴史的な事実関係は逆でプログラミング言語が抽象代数的な発想の中から生まれてきた, と言えるでしょう.

この記事では代数学上の事柄について, プログラミング言語の Python を使って記述していきます.

代数

現代の抽象的な代数は公理による定義を行います. 「公理」というのはひらたく言うとルールのことで, そのルールから証明という手続きを経て, 命題や定理を導き出します.

公理では

  • あるべき対象
  • あるべき演算
  • 満たすべき性質

について記述します.

プログラミングで言えば

  • あるべきオブジェクトや持っているべきプロパティ
  • あるべきメソッドやオペレータ
  • オブジェクトやメソッドが持つべき性質

にあたり, これらはテストでチェックしたり, Java の interface および abstract class 相当の仕組みを利用して, 実装しなければならないメソッドを表現します.

この対応関係を着想として, まずは代数的対象のうち「群 (group)」を Python で表現してみます.

ここで載せるソースコードは全て https://bitbucket.org/cocoatomo/pyarith にあります. 順次アップデートしていきます.

群を扱った Python スクリプトは https://bitbucket.org/cocoatomo/pyarith/src/1b3a578e1678/group.py です. テストスクリプトは https://bitbucket.org/cocoatomo/pyarith/src/1b3a578e1678/tests/grouptest.py です.

クラス Group を継承したクラスが群となり, そのクラスのインスタンスが群の元に相当します.

abstract method として実装してある __eq__, __add__, __neg__ メソッドが, 群であるために必須のメソッドとなります. a = b は実は a.__eq__(b) のことであり, a + b, -a もそれぞれ a.__add__(b), a.__neg__() に相当します. またテストの方でその存在をチェックしている ZERO というフィールドも, それが存在することが群に課せられた条件です. つまり, 群には「等号比較」「加法」「零元」「逆元」が必須の条件なのです. (等号の性質に関しては通常は群の公理に含めません. ここでは等号も実装しているので, 等号の性質も一緒にテストしています.)

これらは好き勝手に実装して良いのではなく, 満たすべき制約条件があります. このテストスクリプトでは, それをテスト関数の形で表現しています. (演算によって群が閉じていることのテストが抜けていますね…… 追加しておきます.)

テストケースとその意味
test_equals_reflexive_law 等号の反射律
test_equals_symmetric_law 等号の対称律
test_equals_transitive_law 等号の推移律
test_add_ZERO 零元の性質
test_add_negative 逆元の性質
test_add_commutative_law 加法の可換性
test_add_associative_law 加法の結合律

それぞれの制約がどういうものかはスクリプトを見ればすぐに分かると思います. 群の公理 (ルール) はこれで全てです. http://ja.wikipedia.org/wiki/%E7%BE%A4_(%E6%95%B0%E5%AD%A6) と見比べて確認してみてください.

(可換性は全ての群が備えているものとは限りません. 可換性を持つ群を「可換群」, 可換性を持たない群を「非可換群」と呼びます.)

まとめ

この記事では, 群の公理を abstract method とテスト関数を使って記述しました. Python スクリプトとして記述することで少しだけ理解しやすくなれば嬉しく思います.

これだけの少ないルールから群の様々な性質が証明されていくのは不思議ですね.

次回は環や体を対象としたり, テストを行うのに使用した pytest モジュールについて書こうと思います.

それでは.

syntax highlighting in bloggart

Elliptium は bloggart というブログエンジンをちょっと改造したもので動いています. 長らく syntax highlight の方法が分からなかったのですが, やっと分かりました.

bloggart には docutils と pygments がライブラリとして入っているので,

.. sourcecode:: <syntax type>

   hoge
   fuga

とやるだけでした.

docutils から pygments の syntax highlight 機能を利用するには http://www.deffbeff.com/blog/2009/06/using-pygments-with-docutils/ にある方法が標準的です. bloggart では rst_directive.py をモジュールが読み込まれる位置に持ってきて対応しています.

<syntax type> が取り得る文法を調べると, pygments.lexers._mapping.LEXERS という辞書を見ると良いようです. この辞書の値はタプルになっていて, 第3要素にある文字列が <syntax type> に来ることができます.

以上, ほぼ自分用のメモでした.

Python Developers Festa 2011.10

Python の勉強会で Asakusa/Hadoop について話してきました.

Python Developers Festa 2011.10 を開催します

Python Developers Festa 2011.10 を終えて

「エ!? Python の勉強会で??」と思うかもしれませんが, 主催者の @voluntas さんに「Hadoop について話さないか? @Shiumachi が Hadoop について話して, @cocoatomo が Asakusa について話してよ」という話が飛んできたので, 喜んで発表してきました.

発表資料

発表

Hadoop を知ってる人で Asakusa のことを初めて知る人向けに発表してきました. なので浅く広く発表したのですが, 実は Asakusa を知ってる人がけっこういて,「その人達には物足りなかったかなぁ?」と振り返って思います.

発表内容についてよく知り, 聞き手をイメージし, 聞き手に何を持って帰ってもらうか? を掴めないと, 良い発表はできないことを思い知りました. 今回は聞き手のイメージが甘く, 説明を浅くしすぎたと思います. 孫子の「敵を知り, 己を知らば, 百戦して危うからず」ですね. 反省して次回の発表に活かします.

発表した手応えとして,

  • Hadoop はみんな知っている. Asakusa もけっこうな人が知っている.
  • Hadoop の象はウケる
  • B2C の人が多いかと思いきや, B2B だったり基幹バッチを抱えている人もいた
  • バッチの問題はどこにでもある
  • 興味を持つ方々は Asakusa アプリケーションどうしの優先順位の設定に関心が強い

こんなものを感じました.

発表内容は申し訳無い部分が多々ありましたが, Asakusa を知ってる人が今より増えて興味を持っていただけると嬉しいです.

次回?

あるか分かりませんが, 次回に発表するとしたらこんなとこでしょうか.

  • PyPy (特に静的解析のあたり)
  • Heroku (Google App Engine の Django (< 1.0.0) から Heroku への移行)
  • 楕円曲線暗号 (←!? 全力で置いてけぼりにしそう. でも V さんが求めるなら解説します)

聞き手として

この勉強会は @voluntas さんの興味に基づいて発表が決められているので, 普段自分が聞かないような幅広い内容の発表が聞けました.

特に, @sawonya さんの部屋の片付けに関する発表が胸に刺さりました. えぇもうそりゃグサリと. こんな感じで. https://twitter.com/#!/cocoatomo/status/125133226791538688

また, 重かったのは @hiroki_niinuma さんの発表. 内容は自分の想像を絶していたので, ここに書くことはできません. ただ, 自分の身に置き換えて考えたときに, 平時から準備しておくことはたくさんある, ということを再認識してきました.

トラブル1

いつものことですが, 何かするときに必ず1つ忘れていくことがあって, それが今回は参加票の印刷忘れでした.

近くのセブンイレブンを探しましたが見付からず, 会場の隣りにある Fedex で印刷してきました. パソコン (10分以内) 262 yen + 印刷代 55 yen = 317 yen かかりました. 忘れ物の代償なのでこんなものでしょう.

皆さんも Oracle 青山センターに行って, 印刷を忘れたときは Fedex が便利ですよ!

トラブル2

実は発表準備中にちょこっとしたトラブルがあったので記録しておきます.

  1. なぜか認証が必要な Wifi (M-Zone とか会場の Wifi) に繋ごうとすると Safari ごと固まる
  2. 強制終了して再起動しても起動しない
  3. 仕方無いので Google Chrome を代わりに使う
  4. スライドが Sphinx の s6 テーマで作られていて, ローカルの JavaScript ファイルを読み込まないためプレゼンができない
  5. 困った\(^o^)/
  6. HTTP サーバを通せば Chrome も表示してくれるので, Mac OS X の Web共有を使ってちょちょっと Apache HTTP Server を立てる
  7. そこの DocumentRoot に Sphinx の build/html フォルダへのシンボリック・リンクを置いて事無きを得る.

事無きか? と言われると, Google Chrome に入れていたけいおんテーマを見られてしまいましたが, まぁ良い.

https://chrome.google.com/webstore/detail/jijlppfhlfgamaofmpafjpibhdmmcbde?hl=ja

最後に

実は Python Developers Festa (旧 Python Hack-a-thon) に参加するのは初めてだったのですが, 発表までさせていただいてありがとうございました.

主催者の @voluntas さん, 会場を提供していただいた Oracle さん, 素晴しい勉強会に参加できて非常に楽しめました. ありがとうございました!!

Licenses