covariant なコレクションと構造的型付けの話

前回の記事で言及した「structural な型付けしか存在しないオブジェクト指向言語」についてまだ少し考えていました。この記事はあまり裏をとっていない話が混じっているので注意して読んでください（誤りだと思ったら指摘してほしいです）。

最初に Scala の話を一つ。

Scala で immutable で covariant なコレクション、例えば List を使うと、空の状態では要素の型は Nothing になっていて、異なる型の要素を追加するにつれて Any に近づいていく。

scala> class A
defined class A

scala> class B extends A
defined class B

scala> class C extends B
defined class C

scala> class D extends B
defined class D

scala> class E extends D
defined class E

scala> class F extends E
defined class F

scala> val list1 = List()
list1: List[Nothing] = List()

scala> val list2 = new F :: list1
list2: List[F] = List(F@158aeed)

scala> val list3 = new E :: list2
list3: List[E] = List(E@e964fe, F@158aeed)

scala> val list4 = new C :: list3
list4: List[B] = List(C@9403a3, E@e964fe, F@158aeed)

scala> val list5 = 123 :: list4
list5: List[Any] = List(123, C@9403a3, E@e964fe, F@158aeed)

ここで List[E] に C を追加すると List[B] と型推論される。この B は E と C という2つのクラスから上に辿っていって初めて出会う地点 (join) だ。クラス階層はツリーだからそういう地点は必ず1つ存在し、1つしかない。ここで E と C の共通の祖先 (upper bounds) としては B の他にも A や A から Any までの間のクラスがあるのだが、いきなり上にいくと不便だからそのうちの一番下のものが選ばれる (least upper bound)。

trait を含む型の階層はツリーではないから話は少し複雑になる。

scala> trait T
defined trait T

scala> trait U
defined trait U

scala> trait V
defined trait V

scala> class X extends B with T with U with V
defined class X

scala> trait W
defined trait W

scala> class Y extends D with T with U with W
defined class Y

scala> val list6 = new X :: list1
list6: List[X] = List(X@13e86ec)

scala> val list7 = new Y :: list6
list7: List[B with T with U] = List(Y@30380, X@13e86ec)

trait を含む型の階層構造において、型は継承関係によって順序づけられるが、任意の2つの型を取り上げたとき、それらは継承関係にあるかもしれないしないかもしれないという、それ以上の性質は期待できない (partially ordered set) 。

この例では X と Y の共通の祖先には A, B, T, U （および A から Any までのクラス）があるが、結果の要素型として推論される型は祖先の集合の「底」に来る要素すべて (minimal elements) を足したものになる。すなわち B, T, U になる。 クラスだけを考えたときは「任意の2つの型を取り上げて上に辿ると、どこか1地点で出会う」という性質を期待できた (join semilattice) から、この中にクラスは1つしか存在しない。そのクラスを with の左に持ってきて残りの trait を右に持ってくれば B with T with U となる。

ちなみに何も継承していない trait を関与させると共通の祖先のない例が作れそうに思えるが、Scala の型推論ではそういう場合は実は ScalaObject with SomeTrait と見なされるようだ（エラーにはならない）。

scala> List[U]() ::: List[T]()
res6: List[ScalaObject] = List()

と、ここまでが前置き。空想上の「structural な型付けしか存在しないオブジェクト指向言語」ではクラスは単にメソッドのシグニチャの集合であって、名前があるとしたら単にエイリアスでしかないものとする。この言語のクラス階層では「任意の2つの型を取り上げて上に辿ると、どこか1地点で出会う」が成立し、さらに逆方向（下向き）でも成立する (lattice)。これは集合の包含関係がそうであるというのと全く同型である。

この言語にも Scala のように covariant な型付けをするコレクションがあると考える。メソッドとして a と b と c しか定義されていないとしよう。そうすると例えば {a, b, c} list という型のリストに {a, b} 型の要素を追加したら {a, b} list に、{a, b} list に {b, c} を追加したら {b} list になるはずだ。{a, b} list に {c} を追加したら {} list になるのだろう。

さて空のリストの型は何から始めたらいいのだろうか。上に上っていくわけだから、最初はクラス階層の一番下 (bottom element) でなければならない。クラスはメソッドのシグニチャの集合でしかないという定義から、メソッドとして a, b, c があれば {a, b, c} list で a, b, c, d だったら {a, b, c, d} list ということになる。だけどプログラム内すべてを見渡して定義されたメソッドの情報がすべて分からないと空リストの型が決まらないというのはどうもおかしい。

というわけで「プログラムでクラスがどう定義されようがすべてのクラスに対して一番下に来るクラス」を導入する必要性が出てくる。Scala の Nothing 型も存在するすべてのクラスを持ち上げる (lifting) ようなクラスだった。

ところでこのクラスは「メソッドのシグニチャの集合」には還元できない。だからこの型だけは名前によって直接名指されなければならない。

さて structural な型付けのオブジェクト指向といえば OCaml だけど、この辺どうなっているのだろうか。

# let list1 = [];;
val list1 : 'a list = []
# let list2 = object method a () = () method b () = () end :: list1;;
val list2 : < a : unit -> unit; b : unit -> unit > list = [<obj>]
# let list3 = object method a () = () method c () = () end :: list2;;
This expression has type < a : unit -> unit; b : unit -> unit > list
but is here used with type < a : unit -> unit; c : unit -> unit > list
Only the first object type has a method b

あれ－。

じゃあリスト自作で、と思ってクラス定義について調べると Scala 同様に variance の指定はできるようなんだけど Nothing 相当についてはどうしたらいいのか？

2008-10-13追記:図を作成して挿入した