パズル 

m次元ユークリッド空間を、N枚の(m-1)次元超平面で分割したとき、最大何個に分割できるか？

という問題を教えてもらった。
m=1の場合は、c(1,N)=N+1
m=2の場合は、c(2,N)=1+N*(N+1)/2
m=3の場合は、c(3,N)=1+N*(5+N*N)/6
...
m=∞の場合は、c(∞,N)=2^N

mについて、一般式を求めることはしてないけど、簡単にできるはず。

量子測定。先週の読書感想文

雑誌「数学」61巻2号の「量子情報の数学的基礎」という論説を読んだ。こっちの内容は、完全に数学的だけど、大体同じ内容が数学的に細かい部分を省略した形で

不確定性原理・保存法則・量子計算
http://ci.nii.ac.jp/naid/110002069559

に書いてある。


歴史的な経緯は詳しく知らないけど、通常教科書でHeisenbergの不確定性原理として説明/証明されているものを実際に示したのは、KennerdとRobertsonという人であるらしい。それで教科書ではこの不確定性原理の解釈として、Heisenbergによるガンマ線顕微鏡の思考実験(「電子の位置を測定しようとして、波長の短いガンマ線当てると、電子と相互作用して、運動量が不確定になる」という話)がでてきたりするけど、前者の「Kennerd-Robertsonの不等式」はCCR(正準交換関係)からの帰結なので測定とか関係なく成り立つ"量子揺らぎ"の話で、一方後者のHeisenbergの元々の議論は測定誤差と撹乱に関わる話なので、この二つは別物と考えるべきというようなことが述べてある。

というような話は、Wikipediaにも書いてあった。Wikipedia偉いな！
http://ja.wikipedia.org/wiki/%E4%B8%8D%E7%A2%BA%E5%AE%9A%E6%80%A7%E5%8E%9F%E7%90%86


若干ややこしいのは、普通、不確定性原理と呼んでいるのは、"量子揺らぎ"に関する方の話だけど、測定誤差と撹乱に関する方の話も、歴史的経緯を考えると、不確定性原理と呼ばれるに値するし、上の論説でも、後者を不確定性原理と書いてたりする。まあ、他に呼び方ないし。ただ現在、大部分の物理学者が不確定性原理と呼ぶとき、頭においているのは、Kennerd-Robertsonの不等式の方だけど思うけど


肝心の小澤の不等式の証明は書いてなかったけど、簡単にできそうな気がしたので少し考えてみたものの、できなかったのでカンニングしたら、簡単に証明してあった

カンニング先↓
Physical content of Heisenberg's uncertainty relation: Limitation and reformulation
http://arxiv.org/abs/quant-ph/0210044

PyPy

PyPyについて、少し調べた。

PyPyは、RPythonというPythonのサブセットで書かれたPython実装。RPythonは、Python2.5とあんまり変わらんくて、一応型推論がやりやすいようにとか考えられて作られてるらしいけど、よく知らない。とりあえず、RPythonの型推論は、実装は見てないけどお手軽な代物っぽい([3])

PyPyには、RPythonのコードを解析して、C/CLI/LLVM/JVMなどに変換するためのツール群が含まれていて、多分これらのツール自体もRPythonで書かれているのだと思う。プロジェクトの目的としては、動的言語の設計や実装に関する実験を(Cではなく)Pythonで手軽に出来るようにしようということらしくて、CPythonより高速なPython実装を作り上げることを目標としているそうな。速度的には、今のところCPythonには劣るらしいけど(まあ数倍程度なので、目的によっては許容範囲？)、

python translate.py --stackless targetpypystandalone.py --objspace=thunk

とかやると(コンパイルにはそこそこ時間がかかる)、"stackless pypy with thunk"ができて、再帰限界が「なくなって」、遅延評価にも対応するようになる。これらの機能が、それぞれ数百行程度のPythonモジュールとして実装されている。他にも、GC自体がRPythonで書かれて、モジュールとして挿し替え可能になってたりとかするっぽい。一応、上でコンパイルしたPyPy処理系で、PyPyインタープリタを起動することはできた。普通のCPythonでも、PyPyインタープリタは起動が遅いのだけど、体感で更に数倍遅くなってる感じがする。


たらいまわし関数を遅延評価のお手軽なベンチマークとして使ってみると、圧倒的な速度差が体感できる。けど、GHCよりは遅い。stacklessにしないと、tarai(2009,1009,5)とかは、stack overflowで死んでしまう。

from __pypy__ import lazy

@lazy
def tarai(x,y,z):
    if x <= y:
        return y
    else:
        return tarai(tarai(x-1,y,z) , tarai(y-1,z,x) , tarai(z-1,x,y))


JIT。PyPyは、Pythonだけでなく、他の動的言語(PrologやSchemeの例が入ってる)の実装にも使えることを目指していて、一旦RPythonでインタープリタを書けばJITコンパイラは、そこから自動生成されるらしい。

http://codespeak.net/pypy/dist/pypy/doc/jit/overview.html
によると、

Our previous incarnations of PyPy's JIT generator were based on partial evaluation. This is a well-known and much-researched topic, considered to be very promising. There have been many attempts to use it to automatically transform an interpreter into a compiler. However, none of them have lead to substantial speedups for real-world languages. We believe that the missing key insight is to use partial evaluation to produce just-in-time compilers, rather than classical ahead-of-time compilers. If this turns out to be correct, the practical speed of dynamic languages could be vastly improved.

Today (beginning 2009), our prototype is no longer using partial evaluation -- at least not in a way that would convince paper reviewers. It is instead based on the notion of tracing JIT, recently studied for Java and JavaScript. When compared to all existing tracing JITs so far, however, partial evaluation gives us some extra techniques that we already had in our previous JIT generators, notably how to optimize structures by removing allocations.

将来的には、partial evalutionを利用したJITコンパイラの自動生成を考えてるけど、今のところ、Tracing JITにinspireされたJIT generator([4])が使われるとのこと。ただし、現時点(ver1.1)では、JIT生成はデフォルトではOFFになっている。


Pythonで速いPythonを書くというだけなら、きっとLisperが聞いたらLispが30年前に通った道だとか言われそうな話で、実際そういう実例があるのか知らないけど、ランタイムまで全部Lispで書いたLisp処理系というのは普通にありそうな気がする。

ただ、色んな機能をプラグイン的に追加したり落としたり差し替えたりできるというのは、試みとしては面白いし、意外とそういうことやった例はなさそうな気がする。まあ、そんなことが出来て実用上嬉しいことがあるのかと言われると、なかなかに微妙なとこではあるけど。あとはやっぱり、パフォーマンスと両立することが本当に可能かどうかという点が最大の問題になりそう

今のところ、PyPyが使ってる技術自体はそれほど目新しいことはないっぽいので、やっぱキーになるのはpartial evaluationになるんだろうか。正規表現の"インタープリタ"と正規表現与えたら、対応するオートマトンが生成できるというのはなんとなく出来そうな気もするけど、インタープリタ書くだけでそこそこ速い処理系ができます！とか言われると、自分を知れ！ そんなおいしい話があると思うのか？ お前のような人間に！という気分になるのだよな〜。

あとWikipediaとか見ると、Psycoの後継とか書いてあるけど、Psycoとは目指してるものは大分違う気がする。コンセプト的には、Psycoの方が圧倒的にインパクトがある。現状PyPy使って嬉しいことがあるかというと微妙な感じだし、PyPyは完成しても、Pythonエンドユーザにはあまり直接的な恩恵がなさそうな(速くなるのは、すごい恩恵といえばそうだけど)。Psycoも復活するとかいう噂なので、がんばっていただきたいところ


参考文献
[1]PyPy status talk
http://codespeak.net/svn/pypy/extradoc/talk/wroclaw2009/talk.pdf

[2]PyPy 1.1 - Present and Future
http://www.pycon.it/static/stuff/slides/pypy-11-presente-e-prospettive-future.pdf

[3]PyPy's Approach to Virtual Machine Construction
http://www.csc.lsu.edu/~gb/csc7700/Reading/pypy-vm-construction.pdf

[4]Tracing the Meta-Level: PyPy's Tracing JIT Compiler
http://codespeak.net/svn/pypy/extradoc/talk/icooolps2009/bolz-tracing-jit.pdf

と言いつつ諦めきれないで

Converting Python functions to dynamically compiled C
http://www.enthought.com/~ischnell/paper.html
とか見て、ごにょごにょしてみたけど、普通のPythonでデフォルトで使えるものが結構使えなくて(sumとかreduceとかxs[::2]みたいなんもアウト)、総計200行程度のコードが動かせるようになるまで、1時間以上かかってしまった。速度は10倍くらいにはなったけど