型推論と無限型(infinite type)

Java言語のジェネリクス(generics)では、型推論過程において無限型(infinite type)が推論されうる。ただしJava言語では無限型を表現できないため、非境界ワイルドカード(unbounded wildcard) <?> を用いた再帰型(recursive type)で代替される。

下記コードの条件演算子(?:)を用いた条件式★において、オペランド型 List<Integer> および List<Double> から式全体の型推論が行われる。このとき推論される型は lub(List<Integer>, List<Double>) = List<Number & Comparable<? extends Number & Comparable<? extends Number & Comparable<? extends...>>>> の構造をもつ無限型となる。Java コンパイラはこの型構造を検知し*1、再帰型 List<Number & Comparable<? extends Number & Comparable<?>>> として推論する。

import java.util.*;

class InferInfiniteType {
  static <T> T id(T a) { return a; }

  static void method(boolean b) {
    List<Integer> e1 = new ArrayList<>();
    List<Double> e2 = new ArrayList<>();
    List<?> r = id(b ? e1 : e2);  // ★戻り値の静的型は？
  }
}

なお、このケースでは戻り値を List<Number> 型で受けることは出来ない。戻り値型を List<?> や Object 以外で受ける手段はないと思う。おそらくは。*2

Java Language Specification, Java SE 8 Editionより一部引用。

The least upper bound, or "lub", of a set of reference types is a shared supertype that is more specific than any other shared supertype (that is, no other shared supertype is a subtype of the least upper bound). This type, lub(U₁, ..., U_k), is determined as follows.
(snip)
It is possible that the lub() function yields an infinite type. This is permissible, and a compiler for the Java programming language must recognize such situations and represent them appropriately using cyclic data structures.
The possibility of an infinite type stems from the recursive calls to lub(). Readers familiar with recursive types should note that an infinite type is not the same as a recursive type.
Chapter 4. Types, Values, and Variables, 4.10.4. Least Upper Bound

The type of a standalone reference conditional expression is determined as follows:

(snip)

Otherwise, the second and third operands are of types S₁ and S₂ respectively. Let T₁ be the type that results from applying boxing conversion to S₁, and let T₂ be the type that results from applying boxing conversion to S₂. The type of the conditional expression is the result of applying capture conversion (§5.1.10) to lub(T₁, T₂).

Chapter 15. Expressions, 15.25.3. Reference Conditional Expressions

Java言語仕様に則った lub(List<Integer>, List<Double>) の導出過程は下記の通り。下線部lub(Integer, Double)にて無限型が推論されている。型推論は人間がやる仕事ではない。

U₁ = List<Integer>, U₂ = List<Double>
ST(U₁) = { Object, Iterable<Integer>, Collection<Integer>, List<Integer> }
ST(U₂) = { Object, Iterable<Double>, Collection<Double>, List<Double> }
EST(U₁) = { Object, Iterable, Collection, List }
EST(U₂) = { Object, Iterable, Collection, List }
EC = { Object, Iterable, Collection, List }
MEC = { List }, G = { List }
Relevant(List) = { List<Integer>, List<Double> }
Candidate(List) = lcp(List<Integer>, List<Double>) = List<lcta(Integer, Double)> = List<? extends lub(Integer, Double)>
- U₁ = Integer, U₂ = Double
- ST(U₁) = { Object, Number, Serializable, Comparable<Integer>, Integer }
- ST(U₂) = { Object, Number, Serializable, Comparable<Double>, Double }
- EST(U₁) = { Object, Number, Serializable, Comparable, Integer }
- EST(U₂) = { Object, Number, Serializable, Comparable, Double }
- EC = { Object, Number, Serializable, Comparable }
- MEC = { Number, Comparable }, G = { Comparable }
- Relevant(Comparable) = { Comparable<Integer>, Comparable<Double> }
- Candidate(Comparable) = lcp(Comparable<Integer>, Comparable<Double>) = Comparable<lcta(Integer, Double)> = Comparable<? extends lub(Integer, Double)>
- lub(Integer, Double) = Number & Comparable<? extends lub(Integer, Double)>
lub(List<Integer>, List<Double>) = List<Number & Comparable<? extends lub(Integer, Double)>>

Java コンパイラは lub(Integer, Double) 部分を1回だけ自己再帰し、List<Number & Comparable<? extends Number & Comparable<?>>> と推論するらしい。*3

yohhoyの日記

技術的メモをしていきたい日記

型推論と無限型(infinite type)