Ошибка компилятора о графе классов не является финалистом из-за параметра с расширением рекурсивного типа

С помощью этой части кода:

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]]

Ответ 1

Из Scala 2.9 спецификация (обратите внимание, что это находится в журнале изменений как изменение, которое было введено в 2.4, поэтому оно не "новое ограничение" в 2.9):

Реализация подтипирования была изменена для предотвращения бесконечного рекурсии. Прекращение подтипирования теперь обеспечивается новым ограничение графов классов финитным.

Кеннеди и Пирс объясняют, почему бесконечные графы классов являются проблемой:

Даже игнорируя подтипирование, бесконечное замыкание представляет проблему для языка, поскольку они должны заботиться о том, чтобы не создавать тип представления для супертипов в нетерпеливой манере, результатом является завершение. Например, общий язык .NET Runtime поддерживает общий экземпляр и общее наследование в его промежуточный язык, ориентированный на C. Класс загрузчик поддерживает хеш-таблицу типов, загружаемых в настоящий момент, и при загрузке нового типа попытается загрузить свои супертипы, добавить их в таблицу и в повернуть загрузку аргументов типа, связанных с супертипом.

К счастью, как указывает Кеннеди и Пирс, есть удобный способ проверить, является ли граф классов бесконечным. Я использую их определения в течение всего этого ответа.

Сначала я сделаю ваши переменные типа четкими для ясности:

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

Далее мы построим график зависимости типа параметра, используя определение Кеннеди и Пирса. Единственное объявление, которое собирается добавить ребра к графу, является последним, для A. Они дают следующие правила построения графика:

Для каждого объявления C <X̄> <:: T и каждого подтерма D<T̄> of 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]], который имеет следующий график:

См. статью для доказательства того, что таблица классов является бесконечной, если она экспансивна.