Recursive type literals

[sophiajt]

Introduction

Currently, type literals are capable of representing any instantiated (non-generic) type except those that are recursive. This is because, as an anonymous type, they do not have a name with which to create this type.

This proposal covers recursive type literals. These type literals add the additional ability of the literal referring to itself. This has one main advantage: emitting .d.ts files for expressions typed by class expressions now have a "flattened" representations. As class expressions could easily have recursive components, we'd like to be able to emit a corresponding type representation into the .d.ts file without contaminating the namespace with additional fresh type names.

Design

var x : <Node> { next: Node; value: number; };

The above acts similarly to this example:

interface Node { next: Node; value: number; };
var x : Node; 

with one critical exception: in the first example the 'Node' name is not visible outside of the type literal.

Typechecking

Typechecking of recursive type literals works just as recursive interfaces, with the exception (as mentioned above) that the name given to the recursive type literal is not visible in the lexical scope outside of the type literal. Otherwise, these expand and are compared for equality structurally just as interfaces.

Differences with other designs

This design differs from similar designs, named the 'self' type design where there is a specific keywords that the type can refer to its self. This proposal is strictly more expressive, albeit at the cost of some additional syntax. For example, embedded recursive types are possible:

var x: <Node> { up: <Parent>{ up: Parent; node: Node}; next: Node; value: number};

[ahejlsberg]

It's already easy to write a recursive type by declaring an interface and referencing it within itself, so as a practical matter self-referential type literals are only interesting in places where you can't declare interfaces. Such places include function bodies, but we've already discussed fixing that. I think if we did there wouldn't be many places in user written code where self-referential type literals would be useful. Furthermore, I think it would be confusing to have two ways of naming types.

That said, I realize we have an issue with self-referential types in auto-generated code (such as .d.ts files). I think we should consider introducing a simple way of referencing an enclosing type without giving it a name. For example, we could have ^ refer to the immediately enclosing type, ^^ to the next enclosing type, and so on. You could then write your example:

var x: { up: { up: ^; node: ^^; }; next: ^; value: number};

A couple of other examples:

var stringList: { data: string; next: ^; };
var selfFunc: () => ^;

I prefer this for two reasons: One, no names are introduced and thus there is no name scope confusion. Two, in auto-generated code we'd have to synthesize names such as _T1, _T2, etc. which really wouldn't be pretty. With the ^ syntax we wouldn't have to.

[DanielRosenwasser]

That's a very good point - it seems like part of our philosophy in emit when it comes to TypeScript has been to avoid generating names (i.e. it has always been easy to support variables named _this in any context but we do not).

However, while I understand the value of predictable/deterministic output, I think something like ^ is non-obvious, a little hard on the eyes, and has low "searchability" (i.e. what search query do you use to figure out what's going on here? "^ in TypeScript types"? "Carat in TypeScript types"?).

The biggest win is that naming each recursive portion brings a lot of clarity.

Hey, why not take advantage of that unicode support for auto-generating names? What about τ1, τ2, etc.? 😉

[RyanCavanaugh]

I think we should consider introducing a simple way of referencing an enclosing type without giving it a name. [... ] With the ^ syntax we wouldn't have to.

In class expressions, the containing type is often going to be the constructor function instead of the instance type. Without a way to name the instance type within the constructor function type literal, we're going to end up writing out the instance type over and over and over again in the .d.ts file. ^ is still useful but we need something else to make anonymous class types generate nicely.

[sophiajt]

@RyanCavanaugh - right, I didn't mention that here, but that's a good example. It also calls back to what @ahejlsberg alludes to in his first paragraph.

For example:

// example.ts
var c = class Node { 
  constructor(public data: any) { }  
  next: Node;
  prev: Node;
  static default: Node;
}

Would become this .d.ts:

// example.d.ts
var c: {new(data: any): {next: ^; prev: ^; data: any}; default: {next: ^; prev: ^; data: any};};

Every usage of the class type ends up duplicating the type, which gets unreadable pretty quickly. Something @RyanCavanaugh and I noticed while sketching it out on the whiteboard is that you want to be able to embed interfaces in these types:

// example(revised).d.ts
var c: {new(data: any): Instance; default: Instance;
  interface Instance {next: Instance; prev: Instance; data: any};
};

Taking it one step further, perhaps allowing interfaces in more places is a better general fix. I could see another possible way of writing my original example as:

var x: interface Node { up: interface Parent { up: Parent; node: Node}; next: Node; value: number};

I'm not wed to any particular syntax.

[JsonFreeman]

I don't see any reason to allow ^ to refer to the class level. I think if we do it, ^ should only be allowed in anonymous types because classes already provide a mechanism for naming their instance and constructor sides (e.g. C, typeof C).

[mhegazy]

+1 for the use of interface keyword as a type reference. I think it is consistent with class and function expression before it.

[JsonFreeman]

Yeah I like that too. It seems like part of the family.

[ahejlsberg]

I see the (subtle) similarity with named function expressions and the scope of their identifiers, but I really don't see much of a need for this feature. In particular, I think it is an overly complex solution to the problem of referencing the enclosing type and it would still require type-to-string conversions to invent a name for the type, e.g.

var a: interface _T { (): _T; };

I would much prefer the simple ^ and then use regular interface declarations for more complicated scenarios.

[JsonFreeman]

I think the interface keyword solution is not complex from the user's perspective, it is very smooth. It would require us to do some work in the language, but it is very intuitive. Ryan's concern about what ^ means in a class still stands. Additionally, I worry about the readability of this because the user has to count the levels of the type! I think you should not have to count to read a type.

[JsonFreeman]

We also would have to come up with rules for where a ^ is licensed, and what it means in each licensing context.

[ahejlsberg]

As I understand it, the only real world problem we're trying to solve here is a way of denoting recursive type literals in auto-generated code. I have yet to be convinced there is a real world need for locally named interfaces in type literals in user written code because regular named types are entirely adequate (modulo our lack of local type declarations in functions which I'm definitely in favor of fixing). I think the ^ is a nice scoped solution to the actual problem. It's usage will be rare and defining the contexts and meanings shouldn't be hard.

[DanielRosenwasser]

A major issue with

var x: { up: { up: ^; node: ^^; }; next: ^; value: number};

is that ^^ and ^ actually refer to the same type, and both of the ^s refer to different types, depending on where they occur. So instead of having the compiler generate a fresh name, we're pushing the effort in figuring this out onto the user when they try to read the signature for themselves.

[ahejlsberg]

The ^ is not perfect, but I don't buy that it isn't easily understandable: The number of carets is the number of { } levels to pop out. It would be exceedingly rare for multiple occurrences of different number of ^ to occur within the same type in real world code--in fact, it would be exceedingly rare to have even a single use of ^.

Again, the only real problem we're trying to solve here is recursive types in auto-generated code. That's esoteric stuff. I don't think it makes sense to invent a whole new (and subtly different) kind of scoping for named type declarations just to solve that problem.

[CyrusNajmabadi]

I’m leaning toward Anders’ side on this. It all comes down to how big the scoping of this feature is. If it really is just for the case where we emit recursive types in decl files, then I think it’s a good choice.

My concern is that I think people will end up wanting to use this in other places. I don’t really buy the ‘people can just use a named type to get around the issue when writing their own code’. I think it’s fairly common for people to create simply one-off structural anonymous types (esp. when a function starts by returning a single value, but then moves to a richer return type). Introducing a named type, while simple, is a burden that some do not want to go through. Because of that, I think these features will be used by users outside of the autogenerated code case. And, as such, we’d want a solution that is great in all situations.

I’m also not very swayed by the ‘now we have multiple ways to create named type’ argument. No matter what, we’re coming up with a new way to provide a way for the compiler to refer to types, but only within a specific scoped context. Whether that is through a name like “ { …: node }” or by “{ next: ^ }” we’re still introducing a ‘new way’ to accomplish the task. So, even if the new way is similar to something we have already, that’s not a reason to avoid it IMO.

So, the question comes down to how important we think readability is. If this is only for auto-generated code (where readability would still be important, but maybe not as much as other cases), I can see ^ be suitable. However, if we expect this feature to be more wildly used (which I think is a distinct possibility), then the route would likely be clearer for users.

        -- Cyrus

From: Anders Hejlsberg [mailto:[email protected]]
Sent: Wednesday, August 27, 2014 7:40 PM
To: Microsoft/TypeScript
Subject: Re: [TypeScript] Recursive type literals (#517)

The ^ is not perfect, but I don't buy that it isn't easily understandable: The number of carets is the number of { } levels to pop out. It would be exceedingly rare for multiple occurrences of different number of ^ to occur within the same type in real world code--in fact, it would be exceedingly rare to have even a single use of ^.

Again, the only real problem we're trying to solve here is recursive types in auto-generated code. That's esoteric stuff. I don't think it makes sense to invent a whole new (and subtly different) kind of scoping for named type declarations just to solve that problem.

—
Reply to this email directly or view it on GitHubhttps://github.com.//issues/517#issuecomment-53667139.

[sophiajt]

The interface literal has other advantages. One that I noticed is that you can use it to create new types. For example, one pattern that we hadn't had a good handle on up to this point was how to type a mixin. One possible solution might look like:

function mixin<T, U>(t: T, u: U): interface TU extends T, U { ... }

There are of course more complex patterns you may want type functions or type operators for, but the advantage with this syntax is that it's already immediately familiar to TypeScript programmers who have used the interface declarations.

[CyrusNajmabadi]

@jonathandturner I really like that example. To me this is opening up my mind to new ways to think about the language. Namely, unlike traditional languages that proceed us (where you need to declare a type, and then reference it later) we allow you do just use a type declaration anywhere a type reference would normally be needed.

This also fits (IMO) where ES6 is going with things like class expressions. i.e. when I want to extend something in ES6 I can put any expression (including a class expression). I don't need to have the class declaration elsewhere, and then reference it in my 'extends' location.

There is something very very attractive about adding no new language syntax, and instead just relaxing things so that type declarations are allowed where type references are needed. It's sensible, and solves the problem neatly.

I love that I can start with:

function foo(): SomeType {
}

then go to

function foo(): { a: SomeType, ... } {
}

then

function foo(): interface Blip { a: SomeType, b: Blip } {
}

Now I have the type I want, with syntax that fits with the language that we have today, without having to clutter any external namespace with the Blip type.

[JsonFreeman]

Ditto to Cyrus and Jonathan's comments. It is very familiar to users, it has a nice analogy to the class expressions of ES6, and even to named function expressions in ES5, just at the type level!

The one thing we would still need to worry about is how to generate anonymous recursive types, but even if declaring a type at the use site doesn't solve that problem in general, I think it still has merit for users for the reasons Cyrus and Jonathan described. We can still error when we need to generate a unnameable recursive type until we come up with a solution for that.

[ahejlsberg]

The reason we can't do the mix-in example today isn't that we can't introduce names in type literals but rather that we don't permit extending naked type parameters. In other words, if we did permit extending naked type parameters you could just as well write the example as:

interface Mixin<T, U> extends T, U { }
function mixin<T, U>(t: T, u: T): Mixin<T, U> { ... }

In fact that's probably how you'd write it so you could use Mixin<T, U> in other places. Having this ability would be nice, but it's a completely different feature.

[jbondc]

Any newer progress on this?

Stylistically I'd seem to prefer a cast in the object literal to give it a name:

// (a)
function foo(): <Blip>{ a: SomeType, b: Blip } {
}
// (b)
function foo(): interface Blip { a: SomeType, b: Blip } {
}

Think (b) made a lot of sense with the interface as the structural building block.

With the addition of type alias<T> = number | T; (a) starts to look natural too.

[JsonFreeman]

This issue is really out of date. It is from before we had generic type aliases, local types, and maybe even intersection and union types. I would recommend looking at #3496 for more current and relevant discussion.

[mhegazy]

As @JsonFreeman, there are ways now to enable scenarios. we wanted to add an interface equivalent to class expressions, but do not think this is required.