由于扩展的递归类型参数,类图的编译器错误不是有限的

Question

有了这段代码:

trait B[T]
trait C[T]
class A[T] extends B[A[C[T]]]

我收到以下错误:

error: class graph is not finitary because type parameter T is expansively recursive
       class A[T] extends B[A[C[T]]]
               ^

有人可以解释错误消息的内容,为什么T无限递归以及为什么以下代码有效？

class A[T] extends B[A[T]]

Answer 1

从Scala 2.9规范(请注意,这是在更改日志中作为2.4中引入的更改,因此它不是2.9中的"新限制"):

子类型的实现已更改,以防止无限递归.现在通过对类图的新限制来确保终止子类型是有限的.

肯尼迪和皮尔斯解释了为什么无限类图是一个问题:

即使忽略子类型,无限闭包也会给语言实现者带来问题,因为他们必须注意不要以急切的方式为超类型创建类型表示,否则就会导致非终止.例如,.NET公共语言运行库支持C语言的中间语言中的泛型实例化和通用继承.类加载器维护当前加载的类型的哈希表,并且在加载新类型时,它将尝试加载其超类型,添加这些到表中,然后加载超类型中涉及的类型参数.

幸运的是,肯尼迪和皮尔斯指出,有一种方便的方法来检查类图是否是无限的.我在这个答案中使用了他们的定义.

首先,为了清晰起见,我会将您的类型变量区分开来:

trait B[X]
trait C[Y]
class A[Z] extends B[A[C[Z]]]

接下来,我们使用Kennedy和Pierce的定义构造类型参数依赖图.将向图表添加边缘的唯一声明是最后一个A.他们为构建图表提供了以下规则:

对于每个声明C <X?> <:: T和各subterm D<T?>的T,如果T_j = X_i添加一个非膨胀性边缘C#i ? D#j; 如果X_i是T_j添加扩展边缘的适当子项C#i ? D#j

所以首先我们来看看Z和C[Z],这让我们从非膨胀边缘Z到Y.接下来Z并A[C[Z]]让我们从一个广阔的边缘Z来Z,并Z和B[A[C[Z]]]让我们从一个广阔的边缘Z到X:

我已经用虚线箭头表示非膨胀边缘,用实心箭头表示膨胀边缘.我们有一个具有广阔边缘的循环,这是一个问题:

无限类表的特征在于包含具有至少一个扩展边的循环的那些图.

这不会发生class A[Z] extends B[A[Z]],具有以下图表:

如果类表是扩展的,那么请参阅该论文以获得类表无限的证明.