2006/11/16 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎

Presentation on theme: "2006/11/16 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎"— Presentation transcript:

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

2 今日の内容 Polymorphism

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

4 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 で置換

5 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; } }

6 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* で呼び出せる

7 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;;

8 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;

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

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

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

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

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

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

15 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)

16 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)

17 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 }

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

19 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 とか

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

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

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

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