Ошибка компилятора о том, что граф классов не является конечным из-за чрезмерно рекурсивного параметра типа - PullRequest
Новая
       55

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

13 голосов
/ 24 сентября 2011

С этим куском кода: 

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 Ответ

18 голосов
/ 24 сентября 2011

Из спецификации 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̄> из T, если T_j = X_i добавить неэкспансивный edge 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:

Graph for the bad version

Я указал нерасширенные ребра пунктирными стрелками, а расширяющиеся ребра сплошными. У нас есть цикл с расширенным ребром, что является проблемой:

Таблицы инфинитарных классов характеризуются именно этими графиками которые содержат цикл с хотя бы одним расширяющим ребром.

Этого не происходит для class A[Z] extends B[A[Z]], который имеет следующий график:

Graph for the good version

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

...