論文紹介: A First-Class Approach to Genericity
久野靖∗

2004.5.27

1

はじめに• 実行時キャストが避けられない→実行中にそこで止まってしまう可能性□ Genericity --- 「型パラメタ」を持つような型のこと• 最 大 の 弱 点 → generic (parameterized) types→ これを追加することで多くのプログラムの構造• 最初は CLU あたりから…

が改善されコンパイル時検査がより多く適用可能に• 現在は多くの言語に「普通の機能」として採り入れられつつある□ Java(JDK 1.5) と C#で導入• しかしまだ「Ad hoc」「特別扱い」「ちょっと違う」が多い• Java の場合→ generic type は 2nd class(実行時にはその情報がない)• C#の場合→実行時に型情報はあるが、パラメタは親2紹介する論文クラスになれない (mixin クラスが作れない)□ 以下では上述の問題のない 1st-class generic type□ Eric Allen, Jonathan Bannet, Robertの作り方を提案

Cartwright, A First-Class Approach toGenericity, OOPSLA 2003, pp. 96-114.

• さらにそのように拡張された型体系が堅固であることを証明• mixin が作れるような 1st-class genericity。
• いろいろと「そうだったのか!」と思わせるところがある。

• genericity とはどうあるべきか考えさせてくれるペーパー。

4BACKGROUND

4.1

Nominal versus Structural Subtyping□ structural subtyping(構造型) な OOPL →オブジェク

3

トはタグ (名前) なしレコード型。

INTRODUCTION• t1 ⊂ t2 とは、t1 が t2 の持つフィールドをすべて持ち、各フィールドの型が⊂であること。

□ ここ 10 年来、主流の OOPL は「static type systemswith nominal subtyping」なもの☆

• subtype 関係とコード継承とは無関係□ 言語例← C++、Eiffel、Java、C#□ nominal subtyping(名前型) な OOPL →オブジェクト• 単純かつ直観にかなう型検査規則

はタグつきレコード型。

• 明示的な型階層• タグ (通常クラス名) について subtype 関係を宣言→フィールドを継承• 相互再帰的データ構造を透明に扱える• 実行時エラーになったときその原因が判りやすい• たまたまフィールドが含まれても宣言がなければ□ 現在の nominal (名前づけ) type system → 厳密なsubtype でない

型検査には非力□ 例:∗ 筑波大学大学院経営システム科学専攻

1• Featherweight GJ(FGJ) → GJ の型モデル。堅固さの証明

abstract class MultiSet {abstract public void insert(Object o);abstract public void remove(Object o);abstract public boolean isMember(Objet o); }□ .NET で も Kennedy, Syme ら の モ デ ル に よ る

genericity の付加

abstract class Set {abstract public void insert(Object o);abstract public void remove(Object o);abstract public boolean isMember(Objet o); }• .NET では型情報を実行時まで保持

4.4□ Java では Set と MultiSet は無関係だが構造型な言語であれば subtype 関係になるはずType Erasure□ 型消去→コンパイル時にチェックし終わったら、実行時には型パラメタの情報なしで実行

4.2

Generic Types• たとえば List<T>を型検査し終わったら、実行時はただの List として実行□ 名前型な OOPL に generic type を入れる場合、クラス• 型消去を用いた場合、実行時には汎用型の情報はな

定義に型変数がつけられ、クラス内ではその型変数を型い→ 2nd class な型ということになるとして自由に使える• 実行時に型情報がないので、型情報に依存する実行• Java の場合の構文:時の操作を安全に用いることはできない

class 名前<型パラメタ, ...> extends ...

• 型パラメタには bounds が指定できる。
「extends ク5ラス」または「implements インタフェース」。指定
しないと Object。

• 実体化 (パラメタあてはめ) の際にこの指定に適合する必要

FIRST-CLASSTYPESGENERIC□ 2nd class であることの問題いろいろ• 型パラメタに対して Cloneable インタフェースを使うことができない (clone() した結果は Object なの□ genreric type(汎用型) →型変数、またはパラメタつきのクラス (パラメタが再び汎用型でもよい)

で元の型にキャストしたいが元の型は実行時には存□ 30 年にわたり研究されてきたが、名前型な言語におけ在していない)

る汎用型についてはあまり研究されていない• 型パラメタ T について「new T[]」と書くと「newE[]」になる (E は bound 型)• 名前型の OOPL の場合、クラス情報が実行時に参照できそれに基づいて分岐などもできる→動的な型の言□ NextGen --- GJ の拡張版で実行時にも型情報を残す。

語に近くなるC#の genericity もこれに相当□ 構造型な OOPL の場合、実行時には型情報を消去→同じ□ パラメタ型が実体化されるごとに (特別なクラスローダ構造なら区別がつかないによって) インタフェース、クラスを生成してパラメタなしクラス階層の中に情報を埋め込む (図 1)• タグによる判別をしない→コンパイル時の検査により安全性を保証• これにより実行時に型情報が使え、上述の問題も解消され、実行オーバヘッドもさほどない

4.3

Nominal Type Systems Supporting □ ただし型パラメタを親クラスにはできない
Genericity
class C<T> extends T { ... }□ Java への genericity の付加→ Odersky, Wadler らに• これにより mixin が作れない。これができるのはよる Generic Java (GJ)

mainstream 言語では C++だけ• たとえば図 2 のような用途• GJ の実装→型消去 (type erasure) による2

class Container<T with {init(); init(Integer);}> ...

class TimeStamped<T> extends T {public long time;
TimeStamped() {super();
time = new java.util.Date().getTime();}}□ また、もっと読みやすくするためいくつかの構文塘• init の代わりに型名を書いてもよい• 中かっこやセミコロンをはぶいてよい• その場に書くかわりにインタフェースを定義してもよい• これができない場合、毎回コピーして作るか、コンポジションするか。どちらも嬉しくない。
• しかしこれをできるようにすると色々考えるべきことが…

7.2

MixGen Extensions□ NextGen と上位互換な拡張。次の 2 点が拡張されている。

6

MIXINS: HISTORY AND MOTIVATION• 親クラスとして型パラメタが書ける --- mixin が□ mixin と い う 言 葉 の は じ ま り --- Lisp 系 言 語 の• with の中に abstract とか final が指定できる --メソッドの同定に必要作れるFlavors• あるクラスを「修飾」するためのクラス• 意味論的には「クラスをクラスにマッピングする関数」

Cyclic and Infinite Class Hierarchies□ Java でも GJ でも型階層は DAG(サイクルがない)□ mixin の重要な用途□ 1st-class genericity でも同様だが、そのチェックは• uniform なクラスの拡張機能を提供 (TimeStampedのように)

面倒

• Ex.

• 多重継承の代替 (簡潔、きちんとした)• Ex.

□ mixin を generic クラスにすることの利点←可変部分をパラメタとして指定することできちんと型検査可能

2class C<X with ...> extends X ...
class D<X> extends C<X> ...
class E extends D<E> ...

• Ex.

THE DESIGN OF MIXIN

3class C<X with ...> extends X ...
class D1 extends C<D0> ...
...
class Dk extends C<Dk-2> ...
class D0 extends C<Dk-1> ...

□ NextGen の拡張として MixGen 言語を提案した□ その説明の準備として NextGen の簡単な拡張、GJ の弱点の説明から

• Ex.

7.1

1

class C<X with ...> extends X ...
class D extends C<D> ...

• アプリケーションをきれいに分割する上で重要な機能

77.3

4class C<X with ...> extends D<C<C<X>>> ...
class D<X with ...> extends XPreliminaries□ GJ にはさまざまな制約があるがその 1 つとして…

(こ□ パラメタつきクラス内で new T() を使う場合、T としてD<C<C<Object>>> → … となる)は具体的なクラスを渡さないといけないし、コンストラクタのパラメタがちゃんと一致していないといけない。

れは D<C<Object>> → C<Object> →□ DAG を保証する 1 つの方法

□ C#ではコンストラクタの引数は 0 個でないといけない。

• generic class が mixin class をパラメタつき拡□ NextGen の次期バージョンでは with 句でコンストラクタのシグニチャを規定するようになる• 厳しすぎて不便→ mixgen では別の方法で検査

3張することを禁止□ 用語:

secondary mixin --- C<T1 , ..., Tn >が Ti...
Object d = new DFactory<C<Object>>().create();Integer e = new E<Object>().typeBreaker(d);を親クラスとして持つこと (Ex.2 が相当)

• すべての secondary mixin を網羅するには→まず• 最後の typeBreaker() の x.m() で Integer のはず

普通の mixin をすべて同定し、「class D<X ...>が String が返される→コンパイル時にチェックできextends C1 <C2 <...<>>>」においてすべての Ci がない型エラー (?)

普通の/secondary mixin であるものを集める• このような上書き事故は Java や C#のような分割コンパイルでは発見不可能→全プログラム検査が必要□ DAG を保証する mixgen のアルゴリズムになってしまう• (1) extends に現れるすべての mixin を引数 (親クラス) に置換← mixin の介在を削除してもループの• エラーが発見できてもパッケージ内側の問題なので利用側には理解しがたいかも。

有無は変化しない• (2) クラスヘッダ中の mixin 定義を削除← mixin ヘッダはそれ単独ではループにならない

7.5

Hyginenic Mixin• (3) すべての型引数を削除←パラメタを削除しても □ 上書き事故をなくさない限り型検査は困難→ mixin の意
ループの有無は変化しない
味を変更するしかない→実はそういうものがあった [16]• あとは通常のアルゴリズムで DAG 性をチェックすれ □ 動的分配の静的型検査…型 T でチェックし、実行時にはばよい
それに適合するシグニチャS のメソッド (存在は保証されている) を探索する□ 先の例に適用すると…

• モデル: T から実行時の型に向かって下向きに S を探しレシーバに最も近いところで見つかったものを• Ex.1 「D extends D」• Ex.2 「E extends E」

採用• Ex.3 循環する extends 関係に• モデル: 実行時の型から T に向かって上向きに S を探し最初に見つかったものを採用• Ex.4 「C extends C」• これまでの場合、どちらでも同じだったわけだが…

7.4

Accidental Overriding□ MixGen ではクラス階層が実行時まで判らないのでもっと工夫が必要□ 「M<T extends B with ...> extends T」にさまざまな T を与えた場合、T に含まれ B に含まれないメソッド□ T から下向きに S を探すが、mixin クラスがあってそのを M で定義してしまうかも→「事故的上書き」(上書きbounds に S が含まれていなければそこで止まる。

事故?)• すなわち、mixin クラスは S を隠す (パラメタ型に• mixin の型検査は難しい←何がパラメタに入って来ついて利用可能なものは bounds に書かれているもるか判らない• Figure 3.のだけだから)。

• 先の typeBreaker の例でも m() の探索は D<>で止まる→外側の m() しか見つからないので OK。
interface I {Object f(); }□ この方式では「どこから探すか」を (アップキャストにclass C<T with T()> extends T implements I {C() { ... }よって) 制御可能→プログラマがより多くの制御を行
Object f() { ... }える。
Integer m() { ... } }class D<T implements I with T()> extends T {□ 現在の JVM や CLR で効率よく実装可能 (次節)
D() { ... }Object f() { ... }String m() { ... } }class DFactory<T implements I with T()> {8 IMPLEMENTING MIXGEN
T create() { return new D<T>(); }class E<T with T()> extends T {□ NextGen →できるだけ「均一な表現」(homogeneousInteger typeBreaker(C<Object> x) { return x.m(); } }representation)4• パラメタ型のインスタンスに共通なコード→共通の抽象親クラスにinterface I<T> { T m(); }class C<S with S()> extends S implements I<S> {S m() { ... } }class D implements I<String> {String m() { ... } }... C<D> ...

• 特定のインスタンス専用のコード→そのサブクラス(個別のクラス) に• すべての generic なメソッド呼び出しは型消去された形で実行• 1 つのメソッドが複数の generic インスタンス化で何回も定義されることもある→各回ごとに違う書き• 個別型固有の部分→ snippet(断片) メソッド呼び出し→各型で上書き換えを生成• 結局、メソッド名の書き換え方式とは、クラス (インタフェース)C で新たに導入されたメソッドに対し□ NextGen コンパイラ→ 2 つのクラス+インタフェースを生成て、そのフルクラス名を前置することに。

• 型消去した親クラス• 上の場合クラス D での m は「I<String>m」。クラス• 個別クラスのテンプレートクラス (snippet の集まり)はめられる。ただの m() は転送メソッドでパラメタ

C での m は「I<S>m」で、ロード時にパラメタがあて• 対応するテンプレートインタフェース (親子関係をS の m() を呼び出す表現)□ いろいろ大変だけどこれで普通の JVM 上で下向き探索の• テンプレート中では List<T>は List$$L{0}$$R とようにふるまうコードが作れる

いった加工された形で存在→クラスローダが展開

8.1

9Basic Implementation Strategy

CORE MIXGEN□ 型システムの堅固さ…(略)□ NextGen 方式では駄目 (親クラスが変わるから共通の親クラスは作れない)□ 「非均質な表現」(heterogeneous representation)

10を採用

RELATED WORK

□ Agesen, Freund, Mitchell[1] --- 構文拡張による• 個別のクラスがそれぞれの実装コードを持つ型パラメタ→ hygienic でないので型検査は困難なはず□ JAM[6] --- 型パラメタではなくトップレベルの構文と8.2しての mixin → これも hygienic でない
Enforcing Hygienic Method Invocation□ Jiazzi[20] --- コンポーネントシステム、ローダによる組み合わせで mixin ができる。これも言語ではない□ MixGen の下向き探索を通常の分岐テーブルにコンパイので…

ルしたい→クラスローダにより隠されるメソッドを改名□ MixedJava[16] --- 最初に hygienic mixin を提案し

• mixin クラスで導入されるすべての新しいメソッド

たが generic type はない。

は改名が必要 (mixin のインスタンスのサブクラス• すべての型を mixin で表現する。すべての値は型(mixin の連鎖) とオブジェクト参照のペア (ポインでその名前の定義をするかも)• 改名されたメソッドへの参照も対応して書き換え

タがすべて倍の大きさになるという問題あり)□ インタフェース呼び出しでは統一的な書き換えは難しい• ダイナミックに型を持つという点で興味深いが Javaや C#の代案にはならない(呼び出し側に応じて書き換えが違う) →転送メソッドを生成□ インタフェースの適用にかかわる問題

5

11

FURTHER RESEARCH□ nominal type OOPL + 1st-class genericity →強力な言語• 今後広まると考える• JVM 上に実装→いろいろオーバヘッドあるが重大ではないと思う (forwarding method は JIT がインライン化できるし)□ CLR はオーバライドされない new をサポート→これを利用して名前書き換えでない実装ができるかも6