scala compiler's stackoverflow protection

Question

In runtime I can:

def X(R: Any): Any = X(R)

But can't do simmilar thing for compile-time:

scala> type X[R] = X[R]
<console>:11: error: illegal cyclic reference involving type X
       type X[R] = X[R]
                   ^

Seems like infinite loop/recursion protection, but as far as I understand the Halting problem - there is no general way to detect infinite recursion for turing-complete language (as detector itself may not halt), so additional compiler's check will not generally work here.

So is there a way to get infinite recursion on scalac? And, is there any other (than preventing such recursion) reason to have illegal cyclic reference?

Answer 1

There is a tricky way to get StackOverflow on scalac using recursion in combination with polymorphism:

scala> trait Re { type X[R <: Re] }
warning: there were 1 feature warning(s); re-run with -feature for details
defined trait Re

scala> trait ReRe extends Re {type X[R <: Re] = R#X[R]}
defined trait ReRe

scala> type X = ReRe#X[ReRe]
java.lang.StackOverflowError

It works because compiler think that R#X[R] is called on Re, but actually ReRe was passed when calculating type X.

No idea about purpose of illegal cyclic reference - maybe it protects only from infinite loops inside compiler, but not from infinite recursion (if turing-completeness is implemented using non-tail recursion).