Generics seems broken...

Topics: General, Language Specification
Jul 30, 2013 at 1:12 PM
Edited Jul 30, 2013 at 1:49 PM
interface IEnumerable<T> extends Enumerable {
    GroupBy<K>(keySelector: ($: T) => K): IEnumerable<IGrouping<T, K>>
}
Im trying to createtype definitions for Linq.JS.
And generics seems totally broken, unless I'm doing something wrong here.

GroupBy returns an enumerable that contains "groupings" which contains items of type T (item type) and the group key K
In C#, I could do the above.
But here I get some weird error about wrapping generics with their own type args.

""A generic type may not reference itself with a wrapped form of its own type parameters. ""

Can I somehow get around this?
Developer
Jul 30, 2013 at 9:23 PM
This limitation is intentional, although we will be lifting it in the future. The reason it was never an issue in C# is because it uses a nominal type system rather than a structural one like Typescript. A workaround for the moment may be possible using additional type parameters and type parameter constraints depending on your exact API shape.
Coordinator
Jul 30, 2013 at 11:58 PM
Another, less precise, workaround would be:
interface IEnumerable<T> extends Enumerable {
    GroupBy<K>(keySelector: ($: T) => K): IEnumerable<any>
}
The "gotcha" is having T in an argument to the recursive call to IEnumerable. Like Dan says, we're working on lifting this restriction in a future version.
Jul 31, 2013 at 2:38 AM
When you guys says "lifting it in the future", do you mean by 1.0? 1.x? 2.x?
Developer
Jul 31, 2013 at 10:44 PM
We're aiming to have the restriction removed by 1.0.
Aug 3, 2013 at 9:47 PM
Is there any information about this wrapped generics restriction? I'd love to read an article describing the source this problem, exact scenarios where structural subtyping can't work with arbitrary 'wrapped' usages of generic types.
Developer
Aug 5, 2013 at 9:55 PM
With TypeScript's structural types determination of type relationships (subtype, assignability, identity) can potentially lead to infinite expansion of generics. Consider the following:
interface List<T> {
    data: T;
    next: List<T>;
    owner: List<List<T>>;
}
interface MyList<T> {
    data: T;
    next: MyList<T>;
    owner: MyList<MyList<T>>;
}
var list: List<Foo>;
var myList: MyList<Foo>;
list = myList;
To determine whether 'myList' is assignable to 'list' we must compare MyList<Foo> to List<Foo>. So we create the expansions of the two generic types and compare their properties. This in turn leads us to compare MyList<MyList<Foo>> with List<List<Foo>>, which in turn leads to another level of expansion, and so on ad infinitum.

We currently have a rule that ensures such "generative recursive generics" never occur, but were planning to change the type comparison algorithm to instead detect and short-circuit the expansion. The short-circuiting mechanism would change references to a type parameter to type ‘any’ in cases where we detect a wrapping reference during generic expansion, and it would thus cut off the infinite expansion. However, in finite scenarios where the generic expansion is guided by the program text, such as when materializing a generic type because of an expression construct (e.g. a property access), we wouldn’t prevent wrapping expansion because it is bounded by what the program actually explores. For example, the expression 'myList.owner.owner.owner' isn’t per se dangerous because nothing explores the expansion beyond three levels.

Hope this makes sense.
Aug 6, 2013 at 12:24 PM
Does this mean that once the restriction is lifted, it will work as expected?
I will get working intellisense/type safety for the example I presented at the first post here?
Or will it as you say, revert to "any" and thus make it look like it is more or less untyped?
Aug 7, 2013 at 2:57 PM
Thanks, it's much clearer now. I was thinking about general algorithm for checking subtyping and it seems to me that problem is undecidable in general case. Do you know if it is decidable or not? I was trying to build a correspondence with context free grammars. Possible property chains allowed by a type, like x.owner.owner.owner.data.data.data for 'List<T>' type in your example form a language that seems to be context free. With restrictions on generic type wrapping the correspondent language is regular and inclusion is decidable therefore.
Oct 25, 2013 at 4:15 PM
I've found the same issue when worked on IxJS (similar to Linq.js): https://typescript.codeplex.com/workitem/1839
Please, remove this restriction on generative recursion.
Coordinator
Oct 25, 2013 at 7:13 PM
Generative recursion should be much less restricted in the latest compiler in 'develop'. If you try it out, and have a case that still does not work correctly, please file an issue and let us know.