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

それでは.

Comments

blog comments powered by Disqus

Licenses