Java 类型推断何时产生无限类型？

programming-languages java wildcard type-inference

2022-09-04 22:37:55

JLS 在类型推理算法（§15.12.2）中提到：

上述过程可能会产生无限类型。这是允许的，Java 编译器必须识别这种情况，并使用循环数据结构适当地表示它们。

但是，我无法找到javac产生无限类型的实际示例。我认为在以下情况下它应该产生一个：

<T> T pick(T a, T b) { ... }

pick("string", 3);

字符串和整数都是可比较的<>，因此它们的常见超类型应该是（无限的）。Comparable<? extends Comparable<? extends Comparable<? ...>>>

我可以做：

Comparable<? extends Comparable<?>> x = pick("string", 3);

但后来我尝试了：

Comparable<? extends Comparable<? extends Comparable<?>>> x = pick("string", 3);

这不会编译。似乎递归在 2 个步骤后中止。

你知道任何让Java真正产生无限类型的情况吗？

--

编辑：看来以上是一个编译器bug。阅读规范，让我们看看计算是如何工作的：lub(String, Integer)

ST(String) = { String, Comparable<String>, Serializable, CharSequence, Object }
ST(Integer) = { Integer, Comparable<Integer>, Serializable, Number, Object }
EC = { Comparable, Serializable, Object }
MEC = { Comparable, Serializable }
Inv(Comparable) = { Comparable<String>, Comparable<Integer> }
lcta(String, Integer) = ? extends lub(String, Integer)
lci(Inv(Comparable)) = Comparable<? extends lub(String, Integer)>
lub(String, Integer) = Serializable & Comparable<? extends lub(String, Integer)>

所以应该是无限类型。Javac在这里似乎是错误的。也许它毕竟没有实现无限类型？lub(String, Integer)

答案 1

下面的代码将 javac 发送到无限循环。据推测，它试图构建一个无限类型，但没有设法将其表示为有限的循环数据结构。

interface I<T> {}
interface A<T> extends I<A<A<T>>>{}
abstract class X {
    abstract <T> T foo(T x, T y);

    void bar(A<Integer> x, A<String> y){
        foo(x, y);
    }
}

答案 2

这个问题已经由R.Grigore（2016）在他的论文Java Generics are Turing Complete中回答。

以下面的Java代码为例，他的建议：

//an empty interface
interface Z {}

//4 generic interfaces, one argument each
interface N<X> {}
interface L<X> {}
interface Qlr<X> {}
interface Qrl<X> {}

//one complex generic, inheriting from instantiations of two other
interface E<X> extends
    Qlr<N<? super Qr<? super E<? super E<? super X>>>>>,
    Qrl<N<?super Ql<? super E<? super E<? super X>>>>>
    {}

//main class with a single function
class Main{
    //heavily nested return type
    L<? super N<? super L<? super N<? super L<? super N<? super E<? super E<? super Z>>>>>>>>
    f(Qr<? super E<? super E<? super Z>>> v) {return v;}
}