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

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 specification (请注意，这是在更改日志中作为 2.4 中引入的更改，因此它不是 2.9 中的“新限制”):

The implementation of subtyping has been changed to prevent infinite recursions. Termination of subtyping is now ensured by a new restriction of class graphs to be finitary.

Kennedy and Pierce解释为什么无限类图是一个问题:

Even disregarding subtyping, infinite closure presents a problem for language implementers, as they must take care not to create type representations for supertypes in an eager fashion, else non- termination is the result. For example, the .NET Common Language Runtime supports generic instantiation and generic inheritance in its intermediate language targeted by C. The class loader maintains a hash table of types currently loaded, and when loading a new type it will attempt to load its supertypes, add these to the table, and in turn load the type arguments involved in the supertype.

幸运的是，正如 Kennedy 和 Pierce 指出的那样，有一种方便的方法可以检查类图是否是无限的。我在整个答案中都使用了他们的定义。

首先，为了清楚起见，我将使您的类型变量与众不同:

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

接下来我们使用 Kennedy 和 Pierce 的定义构建类型参数依赖图。将向图中添加边的唯一声明是最后一个，对于 A .他们给出了以下构建图的规则:

For each declaration C <X̄> <:: T and each subterm D<T̄> of T, if T_j = X_i add a non-expansive edge C#i → D#j; if X_i is a proper subterm of T_j add an expansive edgeC#i → D#j

所以首先我们看 Z和 C[Z] ，这为我们提供了来自 Z 的非膨胀边缘至 Y .下一个 Z和 A[C[Z]]为我们提供了来自 Z 的广阔优势至 Z , 和 Z和 B[A[C[Z]]]为我们提供了来自 Z 的广阔优势至 X :



我用虚线箭头表示非膨胀边缘，用实心箭头表示膨胀边缘。我们有一个边缘膨胀的循环，这是一个问题:

Infinitary class tables are characterized precisely by those graphs that contain a cycle with at least one expansive edge.

class A[Z] extends B[A[Z]] 不会发生这种情况, 有下图:



请参阅论文以证明类表是无限的，如果它是扩展的。