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

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> に来ることができます.

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

初めての 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 ...

2011年振り返り, 2012年目標

振り返り

ちゃんと文章にすると非常に面倒なので箇条書きで誤魔化す. 一応時系列に沿って書いてみる.

  • 正月に1ヶ月毎日数学ネタでブログを書いてみた. 後半は途切れ途切れだが, 継続の重要性を知る.
  • ブログをはてダから bloggart に移行. 1年通して勉強になったし, 無理矢理 Python 製 CMS に触れる機会を作って良かった.
  • 大学院受験 → 合格
  • (ここらへんで周辺の人の転職が相次ぐ)
  • 大学院再入院
  • Python mini Hack-a-thon に出たり, C/API の勉強会を mayah さんと開いたり Python にのめり込む.
  • (娘1歳に)
  • Google Code Jam なんかに出てみる. 一応 T シャツもらえた.
  • (おそらく人生最後の完全数歳になった)
  • 退職
  • (地元で合唱の伴奏してたり)
  • ノーチラス入社
  • PyCon JP 2011 の運営に参加
  • スタート代数を開催
  • PyFes で Asakusa 紹介
  • pypy-ja に本格的に参加して, 主に静的解析のとこを追うことにした.
  • Python 公式ドキュメントの翻訳に参加. Python2.7 のドキュメントが年内に出て万歳.
  • 上の流れと並行して, 研究の前段階のお勉強. 研究は静的解析を使う方向で考え中.

転職の少し前あたりの2011年後半が濃過ぎて, けっこう記憶が前後してる.

こう並べてみると, やっぱりこの1年で自分が大きく変わったし成長してるなぁ, と思う. その変化の推進力は関わる人達からもらってることが多いので, 本当に感謝してます.

新たな目標

  1. 家庭大事に

    大前提

  2. 基礎の強化

    Linux コマンド解説マラソンとかやりたい.

  3. Apache Hadoop に貢献

    差し当たっては logging まわり.

追々後で思い付いていくんだろうけど, とりあえずこんなとこで.

ではみなさま良いお年を. 新年無事迎えられますよう.

それでは.

注釈器は何をしているのか? - 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 さん です. よろしくお願いします.

それでは.

今年読んだ面白CS論文紹介

今年読んだ面白CS論文紹介カレンダー というリレー形式のイベント用に書いています.

自己紹介

ネット上では cocoatomo という ID で活動してます.

現実ではサラリーマンしてますが, 社会人博士なんてものでもあります. 映画とか学生料金で入れます. まだ全然行ってないけど.「けいおん!」とか「ベルセルク」とか行きたい.

プログラム書く立場で働いてみて色々変えたいと思うところがあり, また研究者生活もしてみたいと思い (こっちが本心?), 博士に入りました. そこで, 静的解析を軸に「リリースされる前に, プログラムの予想外の不本意な動作をできるだけ除去したい」という目標で研究しています (まだ勉強している段階ですが).

この分野は昔からあって, 自分が予想していたよりは進歩しておらず, 計算機科学の先達が死屍累々な印象を受けました. 自分もその死体の山の1つになる可能性は高いですが, その死体の分だけ山が高くなるので, まぁ意味はあるでしょう.

という感じで生活してます.

では, さっそくその周辺の論文紹介をしていきます.

Has the Bug Really Been Fixed?

出会い

こっちの分野の論文を全然読んだことない自分にとって, 疑問文の題名はちと衝撃でした. ただ内容とすごく合っていて, それを思い出すと内容も自然と思い出されて,「こういうふうに題名は付けるのかぁ」と関心しています.

目的

この論文の目的は, バグ修正のときの修正漏れや別のエンバグを効率良く検出することです.

後者は regression test で頑張るので目新しいとこは無いです.

ストーリー

前者の手法が人間的で面白かったのです. この論文では以下のようなストーリーをイメージしています.

  1. ある入力でバグが起きる, というバグチケットが飛んでくる.
  2. バグの原因を修正して, チケットにある入力値でテストする.
  3. 「よっしゃー, テスト通った! コミットーーーー!!」
  4. (...コーヒーでまったり...)
  5. 「しまったー! 他の入力値だとまだバグってるやんけ!!」

バグというのは1匹見たら近くにもまだバグが30匹いるものです. 経験則でだいたい分かってるものと思います. 論文では Ant, AspectJ, Rhino を調査対象としていますが, そういう例が多かったという報告がなされています. (コミットコメントの "Oh, I am sorry I didn’t consider that possibility” とか “Oops, missed one code path” とか)

手法

バグチケットにバグを引き起こす全ての入力値が書いてあるわけもないので, バグが発生する箇所での発生する条件から入力値の条件 (WP=Weakest Precondition) を求める必要があります. しかし, たいていの場合この計算は条件式が膨らんで計算が手に余るようになります.

なのでさっきの経験則を使って, 全ての実行パスについて WP を計算するのではなく,「バグチケットにあった入力値からバグ発生箇所までの実行パスから, Levenshtein 距離である程度の範囲にある実行パスについてのみ WP を考える」という手法で距離で制限された WP (=WP_d) を求めます. この WP_d についてテストなり記号実行すれば良いのですが, 論文では (この記事の後で出てくる) JPF 上での記号実行をしてバグのあるなしを確かめています.

感想

この論文を読む前は,「バグの近くにバグがある」というのは経験則では分かっているものの, どうやって形式的な定義に落とせば良いのか想像も付きませんでした. この論文を読んで, まだ色々試さなきゃいけない静的解析の手法が残っていて, 現場での経験とセンスが必要とされるんだなぁ, という印象を持ちました. kinaba さんの 論文をよもう という素晴しいエントリもありますが, 論文は構えずに気楽に内容を楽しみながら読むもんだなぁ, ということも教わった論文です.

Snugglebug: A Powerful Approach To Weakest Preconditions

一言でまとめると「WP の計算に静的解析を組み合わせた解析手法」です. WP は上で出てきた Weakest Precondition です.

問題

多態 (polymorphism) のある言語 (論文では Java) だと, virtual call のせいで状態爆発が起きてちゃんと計算できなくなりやすいです.

解決策

なので, WP を計算するとき virtual call についてはいったん変数の形で扱っておいて, 後で具体的な実態が判明したときにその値で WP を計算し直すことにします. これを "Directed Call Graph Construction" と呼んでいます.

また関数単位での WP の再利用性を高めるために, generalization と名付けた WP を少し緩めた summary を作る手法もこの論文では紹介されています.

感想

プログラミング言語の能力と静的解析可能性はだいたい相反するところがあります. 通常, インターフェースに対してプログラミングをすることは推奨されています. しかし, 静的解析からするとそれは状態爆発を起こすもので, 正直解析の邪魔になります.

このトレードオフの状況で, プログラマのできることを制限し過ぎず, 停止性などの良い性質を証明できる言語が理想の言語なのかなぁ? という示唆を与えてくれた論文です.

Combining Unit-level Symbolic Execution and System-level Concrete Execution for Testing NASA Software

一言で言うと「NASA では, JPF というモデルチェッカーに記号実行を載せてそれを利用してテストケース作成を行ったり, システムレベルでのテストと (JPF が得意な) ユニットテストを組み合わせたりしてソフトウェアの品質を上げているよ」という話です. 一言と形容するには長いですね^-^;;

JPF は JVM instruction の意味論を入れ替えるプラガブルな仕組みになっているし, listener という実行中の動作の監視や通知の仕組みもあるので, 具体値での実行と記号実行を切り替えることもできます. その意味論を差し替える機能を使って, Java Object の field を遅延初期化する (読み取られるときに初期化する) ことで状態爆発を抑えつつ, テストしなければならない (木などの) 参照構造を組み立てます. 参照ではない primitive な値に対しては記号実行をしておきます. そして, 最後に記号値を具体値に直したらテストケースの出来上がりです.

システムレベルのテストとユニットテストを結び付けるところは, Monte Carlo 法で入力値を作ったり, 業務のエキスパートにお願いして業務的に取り得る値の範囲を設定したりした, という結構現実的なお話でした.

感想

NASA ではこの仕組みを有人飛行のシステムに適用しているので, 伝わってくる本気度が半端無かったです. そして, そういう現場での「自動で計算できるプログラムの性質」と「業務上の常識」の組み合わせが興味深かったです.

なんでもかんでも自動でやるのはやっぱり良くないよね〜, という言葉にするとごく普通な感想になってしまいますが,「全自動」に夢を見がちなので自戒として心に留めておこうと思った論文でした.

まとめ?

ちと時間オーバーしましたが, 17日の分の論文紹介でした. 次は @cocoa_ruto さん, お願いします.

最も速く Hadoop 環境を手に入れる方法

  1. クレジットカードを用意します
  2. AWS のアカウントを作ります
  3. S3 と EMR に申し込みます
  4. S3 に jar を上げて, EMR で実行します

えー, ネタが出落ちですみません. というか, 題名見てたいていの人はすぐ分かりますよね.

Amazon Elastic MapReduce on 2011-12-11 という EMR のバージョンアップが出たときに遊んでみた記録です.

EMR についてはこの連載 Amazon Elastic MapReduceの使い方─Hadoopより手軽にはじめる大規模計算 がまとまってて素晴しい情報源だと思います.

このバージョンアップでは, VPC でも EMR が動くようになりました. つまり VPN 環境さえ用意すれば, 自分のローカルなネットワークの延長として Hadoop クラスタが簡単に使えるようになりました. ハードを用意せず, Hadoop を動かすための設定もせず, (実質) ローカルな Hadoop クラスタが使えるのはやはりインパクトが大きいです.

EMR の Job Flow を組むときのウィザードにちょこっと書いてあるのですが, EMR 用に立ち上がるインスタンスには hadoop ユーザが設定されています. ウィザードの途中に keep alive という項目が出てくるのでそれを有効にしておくと, 指定したジョブが終わった後でも立ち上がりっぱなしにできます. WordCount とか適当なジョブを選んでおけば, ジョブの実行自体は数分で終わって, 後は普通の EC2 インスタンスとして触れます.

設定しておいた key pair を使って, hadoop ユーザとしてログインすることもできます. hadoop ユーザは sudoer のようで sudo su - するだけで root になれちゃいました. つまり何でもし放題です.

また HADOOP_HOME は /home/hadoop に設定してあって, そこにはお馴染の hadoop-examples.jar とかもあって, pi の値を計算して遊べます.

security group も elastic mapreduce の master, slave 用のものが自動で作成されるので, それを設定して使えます.

「一先ず hadoop コマンドを打って, Hadoop クラスタで遊んでみたい」とかいう用途には向くんじゃないでしょうか.

もちろん普通の EC2 インスタンスですので, 課金には気を付けてください.

この記事は hadoopアドベントカレンダー2011 の15日目の分として書かれました. 日付とかは気にしないでください.

それでは.

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 さん です. よろしくお願いします.

それでは.

スタート代数 第2回

今日はスタート代数の第2回でした.

スタート代数 #2

さて今回もガチにゼミをやってたわけで, 丁寧にゼミをやった結果, 今日の発表者は @mr_konn さん1人になってしまいました.

随所で参加者の方々から質問などが出てきて, 活発な議論ができて良かったと (主催者として) 感じています.

内容

今日の内容としては §1.1 を終え, やっと用語の定義などが終わりました. これでやっと本論に入っていけます. この先, 部分体全体とガロア群の部分群の対応を扱っていき, その美しさに心打たれる (予定) です.

定義ばっかりで面白くない部分だったのですが, 現代数学は定義のちょっとしたところに仕掛けがあったりするので気が抜けません. 「仕掛け」とは後々出てくる定理で必要な条件だったり, 他の概念と組み合わせるときに必要な条件だったりします. なので, 定義ばっかりでつまらないところは飛ばして, 命題や定理からまた定義に戻る, という本の読み方も良いです.

(と数学本の読み方の紹介など.)

ゼミの発表

発表者にツッコム係は主に主催者がやっているのですが, 私がゼミ発表するときに気を付けていることを書いていってみます.

状況としては, 教授の前で自分の勉強したことを話したり, 同じくらいのレベルの友達どうしで集まって発表し合うなど色んな場面が考えられますが, どの場面でも共通して大切に思っていることを書いていきます.

楽しくさせる

時間を割いて発表を聞いてもらうので, このゼミの時間の中で何かを得てもらいたい, と思っています. 「この時間を過ごして良かったな」と思ってもらうために「楽しくさせる」ということに気を遣っています.

「楽しく」というのは, 新しい知識を得たり, 上手な例を聞いて関心するなどの学問的な楽しさのことを言います.

そして, その時間を有意義にするには, 単にテキストを読めば分かることを喋るだけではだめなのです. それでは自習となんら変わりません. 自分の言葉での説明, 自分なりの解釈, そして自分で考えた話の構成で喋る必要があります. 決してテキストに喋らされてはいけません. そうやってテキストの内容を自分の色に変えて発表することで, 聞き手は2つの視点で内容を眺めることができ理解が深まります. 何より発表準備をした本人が理解が最も深まっているはずです.

「楽しくさせる」をゼミ準備の指標にすることで,「発表者の理解が深まる」「聞き手が新たな視点での物の見方が得られ刺激になる」というメリットを引き出すことができるのです.

キモを押さえる

これは, 結論を固定してから発表の構成を考えなさい, ということです. これ自体は色んなところで言われているので, 数学の場合について話したいと思います. もしかしたら, 別の分野での理論的なお話にも通じるのかも知れませんが, ほとんど知らないのでそこは想定に入れません.

数学ではたいていのテキストが, 定義 (Definition), 補題 (Lemma), 命題 (Proposition), 定理 (Theorem) とその証明 (Proof), 系 (Corollary) というパーツの集まりで, 依存関係を持ちつつ配置されています. この中でも「定理」が最も華々しい数学理論の成果なわけですが, その定理が成立するための最も重要なパーツがどこかにあるはずです. それがこの定理, ひいては理論のキモになります. 定義や定理の羅列の中に理論の流れを読んで, このキモを見付けるのが重要なのです.

どんな数学理論でも, その発端となる発想があるはずで, そこさえ押さえてしまえば後は芋づる式に示すべき命題や補題が出てくるものです. 例えば, 今回扱っているガロア理論では「多項式の根の取り替えを考えると, 体についての情報が分かる」という感覚がキモになっています. この感覚を正確に述べようとすると, 色んな用語の定義が必要になって, 定理を示すまでのステップを刻むために補題や命題が必要になってきます. これをまとめれば1つの数学理論になるはずです.

ゼミ発表においては発表する部分だけで構わないので, 話のキモを考え, それが良く伝わるような例えを出したり, 比喩の話をしたりすると良い発表になると思います.

まとめ

今回はガロア理論で必要な前提知識や用語の定義とその意味を押さえました. 次回からは体の拡大の種類を具体的に見ていきます.

またこの記事の後半では, 数学のゼミ発表について大事にしていることを書きました. もちろん私が常にできているかと言えば No なのですが, 常にこれを目指していることは確かです.

それでは.

Licenses