errore del compilatore su grafico di classe non essendo finitario a causa di un parametro di tipo espansivo ricorsivo

Question

Con questo pezzo di codice:

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

ottengo il seguente errore:

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

Qualcuno può spiegare che cosa l'errore messaggio è, perché T è infinitamente ricorsivo e perché il seguente codice funziona?

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

Answer 1

Dal Scala 2.9 specification (notare che questo è nel Registro modifiche come un cambiamento che è stato introdotto in 2.4, quindi non è una "nuova restrizione" in 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 spiegare perché grafici classe infinitari sono un problema:

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.

Fortunatamente, come Kennedy e Pierce sottolineano, c'è un modo conveniente per controllare se un grafo classe è infinitary. Sto usando le loro definizioni in tutta questa risposta.

Prima farò le variabili tipo distinto per chiarezza:

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

Avanti costruiamo il grafico tipo di parametro delle dipendenze utilizzando Kennedy e la definizione di Pierce. L'unica dichiarazione che aggiungerà spigoli al grafico è l'ultima, per A. Essi danno le seguenti regole per la costruzione del grafico:

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 edge C#i → D#j

Quindi, prima guardiamo a Z e C[Z], che ci dà un vantaggio non espansiva da Z a Y. Prossimo Z e A[C[Z]] ci dà un vantaggio espansiva da Z a Z e Z e B[A[C[Z]]] ci dà un vantaggio espansiva da Z a X:

ho indicato bordi non espansive con frecce tratteggiate e espansiva bordi con quelli solidi. Abbiamo un ciclo con un bordo espansiva, che è un problema:

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

questo non accade per i class A[Z] extends B[A[Z]], che ha il seguente grafico:

Vedi il documento per una prova che un tavolo di classe è infinito se è espansivo.

---