課題5

MLなどの多相型システムを持つ言語の実装と型と の関わりに関する論文を読む

Polymorphism の実装って何すんの？

C や Pascal といった言語では、各式の型はコンパイル時に静的に決定されている。この性質から、各変数や各式の計算結果のうち浮動小数点数なものはfloating point register に割り当てることができ、また入れ子になったデータ構造の中でフラットな表現をとることができる。 しかし、scheme のように変数の型が静的に定まらない言語ではそのようなことは 単純 にはできない。ところで、3年生の前期の演習で ML という言語を勉強したと思うが、ML では型は静的に殆ど決定されているが、polymorphism があるために、 一部の式の型は静的には決定することができなかった。 ML の polymorphism がどんなものであるか思い出してみよう。 例えば次の関数を考えてみよう。

- fun f x = (x,x)
val f = fn : 'a -> 'a * 'a

この意味は、 f は関数であり、任意の型 'aの値を取り、 その型('a)の組の型の値を返すというものである。 多相型がない場合には上のような関数を書くには、'a の型毎に まったく同じプログラムを記述しなくてはならない。 このように多相型の存在はプログラマの記述を楽にしている。 しかし、一方でこのことから効率の良いコードをだすことが困難になっている。 例えば、

• 引数を通常のレジスタで渡すのか floating point register で渡すのか決定できない。
• 上のように任意の値の組というデータを返すのには、x のサイズが分からないためヒープのサイズが決定できない。

等の問題が考えられる。もちろん他にもある。 この欠点を解消するために、近年型システムを利用する方法が提案されている。

課題

本課題では、まずMLの型推論アルゴリズムを思い出して もらってその実装を行い、同時に型情報を使わないで多相型を実装するにはどう すればいいかを考えてもらう。その上で、これまでに提案されている効率を向 上する手法について論文を読んで勉強する。余力がある場合には、先に作成し た型推論プログラムを利用して、効率のよい実装のためのコンパイラの一部を 作成する。この場合にターゲットにするのは、MLのあるサブセットである。

課題のホームページ