2005年06月16日

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)]
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/4390516
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
×

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