Support for recursive "type" definitions

[scabug]

Right now, when metaprogramming, you often need to loop over elements of a type. Right now, there are two ways to do this. One is to create functions with implicit arguments that return fake values (typically null.asInstanceOf). They don't do any useful computation as functions outside the effects they have on the type system. And besides being obtuse, they simply get in the way when all you need to do is get the type system to loop for you. It creates a new implicit which interferes with can get in the way of other implicit conversions and clutters up every interface that uses it. The meta scala source code is littered with these examples.
For example, look at "containsFn"
http://trac.assembla.com/metascala/browser/src/metascala/TLists.scala

We already have type functions, aka type aliases. We can use them for looping by defining a new type alias inside the thing you wish you loop over. This means you have to have access to the type source code you are defining in order to add a new kind of loop to it (the attached example of Add2 inside Num will hopefully make this clear). This means if anyone else wants to add a new type of loop inside the type Num, you have to be able to edit Num's source code to add your definitions to Succ and Zero, or use the implicits trick above, with all the problems thereof.

I suggest allowing types to be called recursively. It would allow for tremendously cleaner metaprogramming. As an example, look at the attached #Add function in UnrelatedToNum. I can now define a new looping construct outside of Add, and without having to have access to the Num source code. Obviously this construct would allow undecidable type statements, so an option to allow undecidable types is probably prudent.

This is similar to the request #1291 however even with -Yrecursion it either produces the error:

Meta.scala:25: error: illegal cyclic reference involving type Add
type Add[A<:Num,B<:Num] = A#IsZero#If[B,Succ[Add[A#Pre,B]]]
^
one error found

Or a stack overflow error if -Yrecursion is set high enough, so apparently whatever was fixed in that request to allow type recursion isn't actually working here.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-3165?orig=1
Reporter: Daniel Rogers (dsrogers)
Attachments:

• Meta.scala (created on Mar 10, 2010 5:02:02 PM UTC, 701 bytes)

[scabug]

Daniel Rogers (dsrogers) said:
Here is another place where this could be used (this does not compile for the same reason above):

type State[S,A] = S => (A,State[S,A])

Granted, this works as a real type...

trait State[S,A] extends Function1[S,State[S,A]]

But there is no reason I shouldn't be able to use a type alias instead here.

[scabug]

@odersky said:
This would be a drastic change of Scala's type system, and one where I believe nobody could say with confidence what the consequences would be. I know that the combination of path-dependent types and recursive types would make types into context-free trees where even equality is undecidable. Would that be a problem in practice? I don't know. But how can anyone convince us it would not be?