2005年06月16日

MinCaml読解ノート: 定数畳み込み

定数畳み込みは次のような結果がわかっている式をコンパイル時に計算した値に置き換えてしまう処理である。

let x = 1 in
let y = 2 in
x + y

MinCamlでは、演算のオペランドの両方の値が定数である場合にその計算結果で置き換えることだけを実装している。だから

let x = 3 in
let y = 7 in
let x + a + y

のような場合を10+aにはできない。

まず、小さな関数から見ていく。

memi, memf, memtは変数xと環境envを受け取り、xが登録されていて値が即値のInt/Float/タプルであれば真、それ以外の場合は偽を返す。

findi, findf, findtxの値が即値のInt/Float/タプルであれば値を返す。xが見付からないか型が合わない場合はエラーとする。

次に定数畳み込みの本体ConstFold.gである。

ソースコードと順番が前後するが、letではまず代入する式を定数畳み込みし、変数とその式を環境に追加する。

変数の評価はそのまま即値に置き換える。ただしIntの場合のみで、FloatTupleの場合はコメントアウトされている。これらは整数と異なり最終的にメモリ上に置かれるデータとなるため重複を嫌ったものであろうか。代償として畳み込みの効率は少し落ち、(let x=1.0 in x) +. (let y=2.0 in y)のような式を一回では3.0と計算できず、最適化フェーズを2回通る必要がある。重複した浮動小数点数は後の仮想マシンコード生成にて省かれるので、ここでFloatの処理を避ける必要はないように思えるのだが。

整数の演算、浮動小数の演算は、全ての項が定数なら計算した即値で置換。

比較による条件分岐では、比較が即値同士なら真偽が確定するので生きる方の式だけを残す。

LetTupleではタプルの中身がわかっている場合はタプルを分解し、要素の数だけLetを並べた形に変換する。同時にletの場合と同様変数と式を環境に追加する。

例えば、t=(a,b,c)とわかっているとき let (x,y,z)=t in elet x=a in let y=b in let z=c in e となる。

MinCaml読解ノート: インライン展開

小さい関数の関数適用をその本体で置き換える。 「概説」の説明の通りで、難しい点は特にない。

変数thresholdはインライン展開するかどうかを決める関数の大きさの閾値で、-inlineオプションによりセットされる。

関数sizeは式の大きさを計算する関数で、単にKNormal.tのノードの数を数え上げて決めている。

関数gがインライン展開の本体である。インライン展開する関数の表(最初は空)と式を受け取りインライン展開した式を返す。 関数定義のKNormal.LetRecと関数適用のKNormal.Appに対する処理が要。

KNormal.LetRecでは関数本体の大きさをsize関数で計算し、threshold以下であれば関数を表に登録する。

KNormal.Appは適用する関数が表に登録されているものなら、展開する関数本体の式で置き換える。 このとき、「仮引数を引数で置換」「本体の式を複製することになるため、α変換で変数名を一意なものに付け替え」をAlpha.gを使って一度に行う。Alpha.gは変換する変数名の表の初期値を外部から与えられるのでこのような流用が利く。

OCamlメモ

List.fold_left 関数 初期値 リスト
初期値をX、リストの要素をx1...xn、関数を中置演算子*で表すとして、
(((X * x1) * x2) * ... * xn)
を計算する。 fold_leftという名前はこの計算が左結合であることによる。 これを右結合にしたfold_rightというのもあり、向きの違いを反映して型が少し異なる。
# List.fold_left (fun x y -> x@[y*2]) [0] [1;2;3];;
- : int list = [0; 2; 4; 6]
# List.fold_right (fun x y -> (x*2)::y) [1;2;3] [0];;
- : int list = [2; 4; 6; 0]
List.fold_left2 関数 初期値 リスト1 リスト2
List.fold_leftに与える引数がxiではなくリスト1の要素xiとリスト2の要素yiの2つになったもの。上に倣って書き表すと
(((X * (x1,y1)) * (x2,y2)) * ... * (xn,yn))
のような感じになる(実際にタプルを構成するわけではないが)。
# List.fold_left2 (fun x y z -> x@[(y,z)]) [(0,0)] [1;2;3] [4;5;6];;
- : (int * int) list = [(0, 0); (1, 4); (2, 5); (3, 6)]

MinCaml読解ノート: ネストしたletの簡約

K正規化で述べたように、ここまでの中間コードはネストしたletのリストになっている。 このネストを開いて平たい一列のリストに直す。

そのために、letが入れ子になっている箇所で図のような繋ぎ替えを行う。

Flatten intermidiate code by transforming nested let.

このための処理が見慣れないと少しややこしい。 Assoc.fの中で内部定義された関数insertは、入れ子になったリストを末尾の手前までそのまま複製しながら進む。末尾の非letの要素eに代わり、eを持ち元のリストの続きに接続するLet(xt, e, f e2)を入れる。

let rec f = function
  | [...]
  | Let(xt, e1, e2) ->
      let rec insert = function
	| Let(yt, e3, e4) -> Let(yt, e3, insert e4)
	| LetRec(fundefs, e) -> LetRec(fundefs, insert e)
	| LetTuple(yts, z, e) -> LetTuple(yts, z, insert e)
	| e -> Let(xt, e, f e2) in
      insert (f e1)

※この処理では非末尾の条件分岐はletの要素になるため厳密には完全にネストがなくなるわけではない。またこの後のインライン展開で再びネストが発生するので、以後もネストしたリストとして扱うことに変わりはない。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。