2006/11/16 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎 コンパイラ演習 第 7 回 2006/11/16 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎

今日の内容 Polymorphism

Polymorphism Parametric polymorphism Subtyping polymorphism Ad-hoc polymorphism (overloading)

Parametric Polymorphism の例 (1) 型変数 # let f x = x;; val f : 'a -> 'a = <fun> # f 3;; - : int = 3 # f 3.14;; - : float = 3.14 ‘a を int で置換 ‘a を float で置換

Parametric Polymorphism の例 (2) 型変数 template <class T> class stack { T* v; T* p; int sz; public: stack(int s) { v = p = new T[sz=s]; } void push(T a) { *p++ = a; } T pop() { return *--p; } int size() const { return p-v; } }

Subtyping Polymorphism の例 void print_xy(Point *p) { cout << p->x << '\n'; cout << p->y << '\n'; } int main(void) Point *p = new Point(12, 34); ColorPoint *cp = new ColorPoint(7, 8, 9); print_xy(p); print_xy(cp); return 0; ここではColorPoint が Point の subtype であるとする Point*を受け取る関数を ColorPoint* で呼び出せる

Subtyping Polymorphismの例 (1) > let p = new point;; > let cp = new colored_point “red”;; > let f p = p#get_x;; > f p;; - : int = 0 > f cp;;

Subtyping Polymorphismの例 (2) void print_xy(Point *p) { cout << p->x << '\n'; cout << p->y << '\n'; } int main(void) Point *p = new Point(12, 34); ColorPoint *cp = new ColorPoint(7, 8, 9); print_xy(p); print_xy(cp); return 0;

Ad-hoc Polymorphism の例 let double (x : int) = x + x;; let double (x : float) = x +. x;; double 1;; double 1.0;; こちらは int の足し算 こちらは float の足し算 同じ名前の関数でも 型によって処理を変えられる

Ad-hoc Polymorphism の例 (1) int plus_i(int x, int y) { return x + y; } double plus_f(double x, double y)

Ad-hoc Polymorphism の例 (2) Martix MatMul(Matrix a, Matrix b) { Matrix c; c = a * b return c; }

Parametric Polymorphism を実現する上での問題 Polymorphic な変数が保持するデータのサイズがコンパイル時に決定しない 例： let f x y = (x, y) x と y は 32bit? 64bit? x と y はどのレジスタで渡される? 作られるタプルのサイズは?

Parametric Polymorphism の 実装法 Boxing Expansion (function cloning) Type-passing

Boxing すべての変数は参照を保持する よってすべての変数は同じサイズ (例: 32bit) データは参照の先の “box” の中に置く Lisp 系言語の実装でポピュラー 単純な実装ではオーバヘッドが大きい 関数をまたがらない範囲で受け渡される値に対しては box を作らない等の最適化がある x y 12 34.5

Expansion (Function Cloning) 各 caller site における引数の型に応じて、 関数の複製を作る let f x = x let g y = (f 2, f 3.4) let f_int x = x let f_float x = x let g y = (f_int 2, f_float 3.4)

Type-passing ｘ の型を実行時に 受け取る let f x = [|x|] (f 12, f 3.4) let f’ {T} (x : T) = if ({T} = {int}) then create_int_array(1, x) else if ({T} = {float}) then create_float_array(1, x) else … (f 12, f 3.4) (f’ {int}, 12, f’ {float}, 3.4)

Type Tag Passing 実行時に関数へ型情報を渡す let assign_array a b i = b.(i) <- a.(i) assign_array({array T}, a, b, i) { s = size_of_type({T}) copy s bytes from a + i * s to b + i * s }

Subtyping polymorphism の実装 簡単にやるには subtype 関係で 型が変わるところで値を変換するコードを 挿入すればよい もっと真面目に考えたいときは 例えば Garrigue, J. “Programming with polymorphic variants”. ML Workshop 1998. とか オブジェクト指向関連については9回目にやる予定です void print(Point*p) ColorPoint* cp = new ColorPoint(..); print(cp); … Point* p = conv_c2p cp print(p);

Ad-hoc polymorphism の実装 簡単にやるには expansionみたいなことをすればよい 型が分かっていればどの関数を 呼べばよいか静的に分かる もっと真面目にやる場合 Haskell とか P. Wadler and S. Blott, “How to make ad-hoc polymorphism less ad hoc”. POPL ‘89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages とか G’Caml とか http://web.yl.is.s.u-tokyo.ac.jp/~furuse/gcaml/

共通課題 １，２のどちらかを選んで回答せよ O’Caml, SML, GCC, javacなどの 既存の処理系を一つ選び、 その処理系において parametric polymorphismが どのような手法で実装されているか を説明せよ コンパイルなどの実験の結果をもとに説明しても、文書やコンパイラのソースコードを読んでの理解をもとに説明してもよい

共通課題 MinCaml を改造して、 overload する演算子を一つ以上導入せよ typing.ml の型推論結果を利用して実装 必要があれば字句・構文解析器も拡張 改造したソースコードを送ってください 例 整数と浮動小数の両方に使える加算演算子 真偽値反転にも符号反転にも使える演算子 整数乗算にも整数配列内積計算にも使える演算子

コンパイラ係用選択課題 Parametric polymorphism 拡張を 自作コンパイラ または MinCaml に実装せよ

課題の提出先と締め切り 提出先: compiler-enshu@yl.is.s.u-tokyo.ac.jp 共通課題の締め切り： 2週間後 (11/30) の午後 1 時 コンパイラ係用課題の締め切り： 2007年2月28日 Subject: Report 7 <学籍番号> <アカウント> 本文にも氏名と学籍番号を明記のこと