jvm backend in PyPy

PyPy (正確には RPython toolchain) の jvm backend への翻訳処理の設計を知りたくてソースコードを追い掛けてみた.

ややメモ書きっぽい感じだが, ほぼ自分用メモということで許してください.

(以下, パスは全て pypy のルートディレクトリを起点としている.)

入口

pypy/translator/jvm/genjvm.py の GenJvm クラス. たぶんだけど. pydoc はこんな感じ.

""" Master object which guides the JVM backend along.  To use,
create with appropriate parameters and then invoke
generate_source().  *You can not use one of these objects more than
once.* """

バイトコード吐いてるのが pypy/translator/jvm/generator.py の JVMGenerator. 既存の何かを使ってたわけではなく, 自作していたのか…… しかも raise NotImplementedError がそこかしこに見える……

これ作った人すごいなぁ. javac 相当のものを RPython で実装しているし. Antonio Cuni さんの仕事はどこまでなんだろうか?

GenJvm#generate_source

これを呼ぶと処理をしてくれるらしいのでここから読む.

メソッドの実装はこんな感じ.

def generate_source(self):
    """ Creates the sources, and returns a JvmGeneratedSource object
    for manipulating them """
    GenOO.generate_source(self)
    self.jvmsrc.set_jasmin_files(self.db.jasmin_files())
    return self.jvmsrc

Jasmin という jvm アセンブラを使っているようだ. Jasmin home page 処理は, 親クラスである GenOO の generate_source メソッドに処理を投げて, 出来上がった jasmin ファイルを jvmsrc 属性に格納して返しているようだ.

さてこのメインの処理を行っていそうなメソッドを覗いてみよう.

pypy/translator/oosupport/genoo.py を開く.

GenOO#generate_source

def generate_source(self):
    self.ilasm = self.create_assembler()
    self.fix_names()
    self.gen_entrypoint()
    self.gen_pendings()
    self.db.gen_constants(self.ilasm)
    self.ilasm.close()

う〜む, 綺麗だ. 文句の付けようが無い. だいたいどんな処理をやっているのか分かりやすくて良い.

GenJvm#create_assembler

まず処理の主体となるであろうアセンブラを用意しているところから見る. デフォルト実装は raise NotImplementedError となっていて, GenJvm クラスでは以下の実装になっていた.

def create_assembler(self):
    """ Creates and returns a Generator object according to the
    configuration.  Right now, however, there is only one kind of
    generator: JasminGenerator """
    return JasminGenerator(self.db, self.jvmsrc.javadir)

JasminGenerator クラスは pypy/translator/jvm/generator.py にある.

JasminGenerator のコンストラクタはいったん置いといて, 次の処理の中身を見てみる.

GenOO#fix_names

def fix_names(self):
    # it could happen that two distinct graph have the same name;
    # here we assign an unique name to each graph.
    names = set()
    for graph in self.translator.graphs:
        base_name = graph.name
        i = 0 ...

Mac で PyGame のインストール

PyPy の translationshell.py で遊んでいると, Flow Graph の表示に PyGame が必要になってくるので, それをインストールした記録.

homebrew と pip は入っているものとする.

$ brew install sdl sdl_image sdl_mixer sdl_ttf smpeg portmidi
$ pip install hg+http://bitbucket.org/pygame/pygame

"Warning: m4 macros were installed to "share/aclocal"." という警告が出たけど無視しても大丈夫でした.

smpeg のインストールで失敗したけど "Error: This is a head-only formula; install with brew install --HEAD smpeg" と出たので, 指示どおりに

$ brew install --HEAD smpeg

とやったら無事インストールできました.

きちんと手順をまとめておくと, こんなふうになります.

$ brew install sdl sdl_image sdl_mixer sdl_ttf portmidi
$ brew install --HEAD smpeg
$ pip install hg+http://bitbucket.org/pygame/pygame

参考資料: https://bitbucket.org/pygame/pygame/issue/82/homebrew-on-leopard-fails-to-install#comment-627494

初めての RPython Toolchain

タイトルは釣りっぽく見えるかもしれませんが, 理論にばっかり興味あったので, RPython をちゃんと触るのは初めてです.

発端

理論派で手を動かすのが億劫な俺が実装書いてみようと思った動機は, PyPy Sudden Death Calendar 27日目 - JVM Backend に完敗した件を受けて にある話にあります. ここでは ootype によって JVM 用に変換されたクラスがしっちゃかめっちゃかだ, ということを追っています. なんでこんなことになっているのか分からないので, まずは簡単なインタプリタを例に RPython Toolchain の動きを追っていく計画です.

プログラム仕様

このプログラムの仕様はすごく簡単で, 各行の先頭に暗黙の echo があるものとして動作します. プログラミング言語 ECHO とでも呼びましょうか.

実装

さっきのブログエントリの筆者でもある shoma さんが翻訳されている PyPy を使ってインタプリタを書く を参考に作りました.

"""
echo.py

programming language ECHO
implemented on top of PyPy

by cocoatomo
"""

import sys
import os

try:
    from pypy.rlib.jit import JitDriver
except ImportError:
    class JitDriver(object):
        def __init__(self, **kw): pass
        def jit_merge_point(self, **kw): pass
        def can_enter_jit(self, **kw): pass

jitdriver = JitDriver(greens=['pc', 'program'], reds=[])

def mainloop(program):
    pc = 0

    while pc < len(program):
        jitdriver.jit_merge_point(program=program, pc=pc)

        line = program[pc]

        # instead of print
        os.write(1, line)
        os.write(1, '\n')

        pc += 1

def parse(program):
    return program.split('\n')

def run(fp):
    program_contents = ''
    while True:
        read = os.read(fp, 4096)
        if len(read) == 0:
            break
        program_contents += read
    os.close(fp)

    program = parse(program_contents)
    mainloop(program)

def entry_point(argv):
    if len(argv) < 2:
        print("too few arguments. program file name needed.")
        return 1

    run(os.open(argv[1], os.O_RDONLY, 0777))
    return 0

def target(*args):
    return entry_point, None

def jitpolicy(driver):
    from pypy.jit.codewriter.policy import JitPolicy
    return JitPolicy()

if __name__ == "__main__":
    entry_point(sys.argv)

なんの変哲も無い処理系です.

PyPy は pypy-ja で fork している レポジトリ から取ってきました.

$ python ./pypyja/pypy/translator/goal/translate.py --opt=jit echo.py

とすると長々とビルドが走り, MBA によって俺の腿が温まりました.

$ cat input.echo
begin
1 ...

注釈器は何をしているのか? - PyPy Advent Calendar 2011

この記事は PyPy Advent Calendar 2011 の17日目の記事として書いています. 2周目ってけっこう速く来るんですね. 執筆時刻は気にしないように.

何を書くのか?

PyPy Toolchain には「注釈器 (annotator)」というものが含まれており, こいつは RPython に出てくる変数について, そのメタ情報である「注釈 (annotation)」を与えていきます.

この注釈器の具体的な動きの説明を書いていきます. 途中で力尽きる予定なので, その続きは後日書きます(エ

元ネタ

資料としては The Annotation Pass から参照されている Compiling Dynamic Language Implementations (←PDF です) という論文の §6 Annotator を使っています. 実質この記事は, §6の要約になっています.

この論文は 2005 年のものですが, 全体像を掴むのに良さそうなので選びました.

注釈とは

注釈というのは結局は型 (ある値の集合) なんだけど, Python の方の型とごっちゃになって面倒なので, 敢えて注釈という用語を使っています. 注釈が常に Python の型と一致しているわけではないし, そうなる必然性もありません. Python に新しい型システムを導入していると思ってください.

注釈付け

Python では初期化された瞬間でしか変数の型が分からないことが多いです. なので, 実行順序に沿って前の方から処理を追っていかねばなりません.

注釈付けの処理は本質的には型推論なのですが, Hindly-Milner のように前後に移動しながら型推論を行うことはできないので, それに比べると安直 (naive) な方法です.

ループとかプロシージャ呼び出しとかがあると変数の注釈がより緩い (general) 注釈に変更されることがあるのですが, その場合は再度最初から計算し直して, 注釈がこれ以上一般化 (generalize) されない状態にまで持っていきます.

注釈の種類

注釈の種類には, 型としてお馴染のものとやや Python では聞き慣れないものがあります.

  • Bot, Top: Bottom と Top. Java で言う「暗黙的にある null のクラス」と「Object」です.
  • Int, NonNegInt, Bool: Bool は特殊な Int として定義されています. (たぶん 0 と 1)
  • Str, Char: Char は長さ1の String です.
  • List(v): v はリストの要素のようです.
  • Pbc(set): set は実行時に定義される定数の有限集合だそうだ. function とか class とか method という callable もここに入っています.
  • None: Python の None です.

ここではリストに載せなかったけど, NullableStr みたいな注釈や dict, tuple, float, unicode point, iterator などなどの注釈もあるんだけど発想はストレートなものなので説明省略します.

そしてこれら注釈の間には包含関係があり, その関係による束 (lattice) を構成します. Top が一番上に来て最も緩い型を表し, Bot が一番下に来て最も狭い型 (=どんな値も取りようの無い型) を表します. これについては PDF の Figure 1 と 2 を見てください.

注釈器の目的

以下のように記号を置きます.

  • A: さっき出てきた注釈が成す束
  • V: 全ての変数の集合
  • E: 変数どうしの同値関係
  • b: 関数 V -> A

A, V は分かりやすいと思います. E は, 2つの変数が同じ値を指しているかどうかの情報を蓄えている, と捉えてください. b は, ある変数がどの注釈に属するのか (ある変数にどの注釈を付けるべきか) を表している, と捉えてください.

この記号を使って状態 (state) とその間の関係 (generality) を説明します.

状態というのは関数 b: V -> A と V 上の同値関係 E の組 (b, E) で, 要は注釈情報の集まりです. ある状態 (b', E') が状態 (b, E) より一般的 (general) というのは, ∀v ∈ V, b'(v) ≧ b(v) かつ E' ⊃ E であることを言います. (A 上の関係 ≧ は注釈の包含関係 ⊃ に等しい.) 言葉で説明すると, 全ての変数について同じかより広い注釈を付け, 同値関係にある変数の組が同じか増えている状況を言います.

最も一般的な状態 (b_max, E_max) というのは, ∀v ∈ V, b_min(v) = Top, E_max = {(v, v') | v, v' ∈ V} のことです. つまり, 型に関して何にも情報がありません. 逆に最も一般的でない状態 (b_min, E_min) というのは, ∀v ∈ V, b_min(v) = Bot, E_min = {(v, v) | v ∈ V} のことです. つまり, 全ての変数が値を取り得ないというへんてこりんな状況です.

ここまでで準備した言葉によって, 注釈器の目的を以下のように書くことができます.

解析対象のプログラムに対して, 最も一般的でない (狭い) 状態を求める.

語弊を恐れずに言うと, それぞれの変数が取り得る型の中で最も狭いものを求める, ということです.

まとめ

突然まとめに入ります.

PDF の 6.1 から 6.4 あたりを眺めて軽くまとめただけですが, 色々細かいところや 6.4 の後半以降を省いています. これがブログ記事だということもありますし, まだ自分がちゃんと読めてないという理由もあります. 元の論文が 2005 年に発表されたものなので, それ以降の情報なども加えつつ, これの続きに関してどこかでちゃんと説明したいと思っています.

次は Masahito さん です. よろしくお願いします.

それでは.

Let's translate.py! - PyPy Advent Calendar 2011

お前, 誰よ?

改めまして cocoatomo と申します. 技術的な話はこの ID とペンギンアイコンで通しているので, 他の場所で cocoatomo と見たらきっと私です.

プログラムの静的解析に興味があり, PyPy の処理過程のうちでも前半にある Control Flow Graph への変換および注釈付け (メタデータの付与) を勉強中です. 正直, 後半の JIT とかはあんま興味無いです. そこは @chlere さんという優秀な方がいるので, そちらにお任せして色々教えてもらっています.

今回の記事は PyPy Advent Calendar 2011 の4日目として書いています.

翻訳とは?

さて, 表題にある translate.py とは何ぞや? 翻訳? 何を翻訳? と思われたと思います. 実は私にとって「翻訳」は2重の意味があって, PyPy の処理過程の一部である translate.py のことと, 私が行っている PyPy の公式ドキュメントの翻訳です. (しかも translation.html の翻訳なので, 「翻訳」の翻訳です.)

translate.py は ${PYPY_HOME}/pypy/translator/goal/translate.py にあります. 私の翻訳は PyPy - RPython toolchain — PyPy 1.6 documentation に置いてあります. まだ翻訳は完了していませんが, これを読んでいけば PyPy がどんな処理を行っているかのイメージが付くでしょう.

PyPy が行っていることを大雑把に説明すると, RPython という Python っぽい言語で書かれたプログラムを変換して, 型などの情報を付加して, そこから色々な言語のソースコードを出力します. この変換のことを翻訳と名前を付けたようです.

translatorshell.py

さて難しい話は置いておいて, まずは翻訳して遊んでみましょう.

環境

私は楽をするためこんな環境で作業しています.

  • Mac OS X 10.7 Lion (gcc は llvm-gcc)
  • PyPy のソース一式を bitbucket から取得
  • homebrew で pypy をインストール

モジュールまわりで面倒が無いように homebrew に pypy をビルドしてもらって使っています.

翻訳遊び

(flow モデル のあたりを参照しながら読み進めると良いかもしれません.)

$ cd $PYPY_HOME/pypy
$ pypy bin/translatorshell.py

と実行すると, なにやらメッセージとともに ``>>>> `` という PyPy のプロンプトが出てきます. Python と違って ">" が4つあるのが特徴です.

System Message: WARNING/2 (<string>, line 46); backlink

Inline literal start-string without end-string.

ここで適当な関数 succ を定義して, 翻訳処理に掛けます.

>>>> def succ(x): return x + 1
>>>> t = Translation(succ)
>>>> t.view()
http://desmond.yfrog.com/Himg615/scaled.php?tn=0&server=615&filename=fxlg.png&xsize=640&ysize=640

何かウィンドウが出てきてフローチャートみたいなものが表示されました. このウィンドウは Pygame のもので, 変換結果が目で見て分かる形で表示されます.

中身は succ が変換されたものなので見れば, まぁ分かるでしょう. ESC キーを押してウィンドウを閉じてください.

今度はこれにメタデータを付加しましょう.

今は succ には数値が来ることを期待しているので, succ の引数 x が int であることを PyPy に教えましょう.

>>>> t.annotate([int])
>>>> t.view()

最初に annotate メソッドを実行すると, とあるモジュールがコンパイルされるようです. gcc-4.0 という実行ファイルが求められるので, 私は

$ ln -s /usr/bin/gcc /usr/bin/gcc-4.0

とやや適当な対応をしました. とりあえずこれで動いているようです.

http://desmond.yfrog.com/Himg859/scaled.php?tn=0&server=859&filename=41917068.png&xsize=640&ysize=640

t.view() と再度フローチャートを表示すると, さっきと少し変わっているところがあります. x_0, v_0, v_1 という文字の色が変わってリンクになっています. 真ん中の四角の中に inputargs: x_0 とあるので, きっと succ(x) の x のことなのでしょう. クリックしてみます. 何やらメッセージが出ますが SomeInteger という文字列が見付かるでしょうか? これがさっき「succ の引数 x は int である」と教えた結果です. PyPy では "int" という型情報を SomeInteger というクラスで表現しています.

v_0 をクリックするとやはり同じように SomeInteger という文字列を含んだメッセージが出てきます. Backspace を押して最初の画面に戻ってみると, v_0 というのは v_0 = add(x_0, (1)) というものらしいです. 元々のプログラムでは return x + 1 と1つの文で書いていたものが v = x + 1; return v (←注. Python のソースコードとしては正しくない) と2つの文に分割されているようです.

int である x に 1 を加えた結果はもちろん int なのですが, 普通の Python ではこのような推論は行ってくれません. それはそもそも「x が int である」という情報を渡す口が無いからです. (Python3 で関数アノテーション入ったじゃないか, と言われそうですが, あれに推論の機能は無かったはずです. もし間違っていたら是非教えてください.)

PyPy によって int 型だと判明した v_0 を次の四角に渡し, 次の succ__2 という名前の四角で v_1 として受け取られ return されています. もちろん v_1 に来るのは v_0 という int なので v_1 も int 型です. その証拠に v_1 をクリックしてみましょう. v_0 と同じように SomeInteger という文字列がありますね.

蛇足ですが, 元々は同じ v という変数なのに v_0 とか v_1 という名前に分けられているのは 静的単一代入 (SSA) という形式に変換されているからです. この形式では, ある変数への代入は1回しか行えず, 再度代入するときには別の変数に代入しているものと看做します. この形式にしておいた方が何かと処理が楽なので, 変換や最適化の中間表現として採用されます.

さてここまでで succ が PyPy 内部でどう扱われるかを見渡すことができました. 今回は succ という簡単な例でしたが, 是非 for 文や if 文を含む関数をみなさんの手を動かして PyPy で変換してみてください.

まとめ

今回は理論的に掘り下げた話はせず, まずは PyPy に触れてみよう, translation.py で遊んでみよう, という話をしました. 実は別の話を書こうと思って準備をしていたところ, Pygame のウィンドウを出すためにモジュールをコンパイルするところで引っ掛かってしまい, せっかくなのでそこの部分について詳しく書きました.

Advent Calendar の2周目が回ってきたら理論的なところなどを書いてみようと思います.

次の担当は Masahito さん です. よろしくお願いします.

それでは.

Licenses