Proposal for generators design

Cyrus Najmabadi (@CyrusNajmabadi)

A generator is a syntactic way to declare a function that can yield. Yielding will give a value to the caller of the next() method of the generator, and will suspend execution at the yield point. A generator also supports yield * which means that it will delegate to another generator and yield the results that the inner generator yields. yield and yield * are also bi-directional. A value can flow in as well as out.

Like an iterator, the thing returned by the next method has a done property and a value property. Yielding sets done to false, and returning sets done to true.

A generator is also iterable. You can iterate over the yielded values of the generator, using for-of, spread or array destructuring. However, only yielded values come out when you use a generator in this way. Returned values are never exposed. As a result, this proposal only considers the value type of next() when the done property is false, since those are the ones that will normally be observed.

Basic support for generators

Type annotation on a generator

A generator function can have a return type annotation, just like a function. The annotation represents the type of the generator returned by the function. Here is an example:

function *g(): Iterable<string> {
    for (var i = 0; i < 100; i++) {
        yield ""; // string is assignable to string
    }
    yield * otherStringGenerator(); // otherStringGenerator must be iterable and element type assignable to string
}

Here are the rules:

~~The type annotation must be assignable to Iterable<any>~~.
- This has been revised: IterableIterator<any> must be assignable to the type annotation instead.
The operand of every yield expression (if present) must be assignable to the element type of the generator (string in this case)
The operand of every yield * expression must be assignable to Iterable<any>
The element type of the operand of every yield * expression must be assignable to the element type of the generator. (string is assignable to string)
The operand of a yield (if present) expression is contextually typed by the element type of the generator (string)
The operand of a yield * expression is contextually typed by the type of the generator (Iterable<string>)
A yield expression has type any.
A yield * expression has type any.
~~The generator is allowed to have return expressions as well, but they are ignored for the purposes of type checking the generator type.~~ The generator cannot have return expressions
Open question: Do we want to give an error for a return expression that is not assignable to the element type? If so, we would also contextually type it by the element type.
- Answer: we will give an error on all return expressions in a generator. Consider relaxing this later.
Open question: Should we allow void generators?
- Answer: no

Inferring the type of a generator

A generator function with no type annotation can have the type annotation inferred. So in the following case, the type will be inferred from the yield statements:

function *g() {
    for (var i = 0; i < 100; i++) {
        yield ""; // infer string
    }
    yield * otherStringGenerator(); // infer element type of otherStringGenerator
}

Rather than inferring Iterable, we will infer IterableIterator, with some element type. The reason is that someone can call next directly on the generator without first getting its iterator. A generator is in fact an iterator as well as an iterable.
The element type is the common supertype of all the yield operands and the element types of all the yield * operands.
It is an error if there is no common supertype.
As before, the operand of every yield * expression must be assignable to Iterable<any>
yield and yield * expressions again have type any
If the generator is contextually typed, the operands of yield expressions are contextually typed by the element type of the contextual type
If the generator is contextually typed, the operands of yield * expressions are contextually typed by the contextual type.
~~Again, return expressions are allowed, but not used for inferring the element type.~~ Return expressions are not allowed. Consider relaxing this later, particularly if there is no type annotation.
Open question: Should we give an error for return expressions not assignable to element type (same as the question above)
- Answer: no return expressions.
If there are no yield operands and no yield * expressions, what should the element type be?
- Answer: implicit any

The `*` type constructor

Since the Iterable type will be used a lot, it is a good opportunity to add a syntactic form for iterable types. We will use T* to mean Iterable<T>, much the same as T[] is Array<T>. It does not do anything special, it's just a shorthand. It will have the same grammatical precedence as [].

Question: Should it be an error to use * type if you are compiling below ES6.

The good things about this design is that it is super easy to create an iterable by declaring a generator function. And it is super easy to consume it like you would any other type of iterable.

function *g(limit) {
    for (var i = 0; i < limit; i++) {
        yield i;
    }
}

for (let i of g(100)) {
    console.log(i);
}
var array = [...g(50)];
var [first, second, ...rest] = g(100);

Drawbacks of this basic design

The type returned by a call to next is not always correct if the generator has a return expression.

function *g() {
    yield 0;
    return "";
}
var instance = g();
var x = instance.next().value; // x is number, correct
var x2 = instance.next().value; // x2 is given type number, but it's actually a string!

This implies that maybe we should give an error when return expressions are not assignable to the element type. Though if we do, there is no way out.
2. The types of yield and yield * expressions are just any. Many users will not care about these, but the type of the yield expression is useful if for example, you are implementing await on top of yield.
3. If you type your generator with the * type, it does not allow someone to call next directly on the generator. Instead they must cast the generator or get the iterator from the generator.

function *g(): number* {
    yield 0;
}
var gen = g();
gen.next(); // Error, but allowed in ES6 (preferred in fact)
(<IterableIterator<number>>gen).next(); // works, but really ugly
gen[Symbol.iterator]().next(); // works, but pretty ugly as well

To clarify, issue 3 is not an issue for for-of, spread, and destructuring. It is only an issue for direct calls to next. The good thing is that you can get around this by either leaving off the type annotation from the generator, or by typing it as an IterableIterator.

Advanced additions to proposal

To help alleviate issue 2, we can introduce a nominal Generator type (already in es6.d.ts today). It is an interface, but the compiler would have a special understanding of its type arguments. It would look something like this:

interface Generator<TYield, TReturn, TNext> extends IterableIterator<TYield /*| TReturn*/> {
    next(n: TNext): IteratorResult<TYield /*|TReturn*/>;
    // throw and return methods elided
}

Notice that TReturn is not used in the type, but it will have special meaning if you are using something that is nominally a Generator. Use of the Generator type annotation is purely optional. The reason that we need to omit TReturn in the next method is so that Generator can be assignable to IterableIterator<TYield>. Note that this means issue 1 still remains.

The type of a yield expression will be the type of TNext

function *g(): Generator<number, any, string> {
   var x = yield 0; // x has type string
}

If the user does not specify the Generator type annotation, then consuming a yield expression as an expression will be an implicit any. Yield expression statements will be unaffected.
For a return expression not assignable to the yield type of the generator, we can give an error (require a type annotation) or we can infer Generator<TYield, TReturn, any>?

function *g() {
    yield 0;
    return ""; // Error or infer TReturn as string
}

Once we have TReturn in place, the following rules are added:

If the operand of yield * is a Generator, then the yield * expression has the type TReturn (the second type argument of that generator)
If the operand of a yield * is a Generator, and the yield * expression is inside a Generator, TNext of the outer generator must be assignable to TNext of the inner one.

function *g1(): Generator<any, any, string> {
    var t = yield * g2(); // Error that string is not assignable to number
}
function *g2(): Generator<any, any, number> {
    var s = yield 0;
}

If the operand of yield * is not a Generator, and the yield * is used as an expression, it will be an implicit any.

Ok, now for issue 1, the incorrectness of next. There is no great way to do this. But one idea, courtesy of Cyrus Najmabadi (@CyrusNajmabadi), is to use TReturn in the body of the Generator interface, so that it looks like this:

interface Generator<TYield, TReturn, TNext> extends IterableIterator<TYield> {
    next(n: TNext): IteratorResult<TYield | TReturn>;
    // throw and return methods elided
}

As it is, Generator will not be assignable to IterableIterator<TYield>. To make it assignable, we would change assignability so that every time we assign Generator<TYield, TReturn, TNext> to something, assignability changes this to Generator<TYield, any, TNext> for the purposes of the assignment. This is very easy to do in the compiler.

When we do this, we get the following result:

function *g() {
    yield 0;
    return "";
}
var g1 = g();
var x1 = g1.next().value; // number | string (was number with old typing)
var x2 = g1.next().value; // number | string (was number with old typing, and should be string)

var g2: Iterator<number> = g(); // Assignment is allowed by special rule!
var x3 = g2.next(); // number, correct
var x4 = g2.next(); // number, should be string

So you lose the correctness of next when you subsume the generator into an iterable/iterator. But you at least get general correctness when you are using it raw, as a generator.

Additionally, operators like for-of, spread, and destructuring would just get TYield, and would be unaffected by this addition, including if they are done on a Generator.

Thank you to everyone who helped come up with these ideas.

I've updated the proposal with the results of further discussion. There have only been a few minor changes:

Answers to open questions in the basic proposal.
Change the rule about what return type annotations are allowed on a generator function. IterableIterator<any> must be assignable to the return type annotation.
Return expressions are not allowed in generators. We can consider relaxing this later if the need arises.

For the sake of completeness, I think it would extremely helpful to actually state the current declarations of the types named here:

interface IteratorResult<T> {
    done: boolean;
    value?: T;
}

interface Iterator<T> {
    next(value?: any): IteratorResult<T>;
    return?(value?: any): IteratorResult<T>;
    throw?(e?: any): IteratorResult<T>;
}

interface Iterable<T> {
    [Symbol.iterator](): Iterator<T>;
}

interface IterableIterator<T> extends Iterator<T> {
    [Symbol.iterator](): IterableIterator<T>;
}

interface GeneratorFunction extends Function {
}

interface GeneratorFunctionConstructor {
    /**
      * Creates a new Generator function.
      * @param args A list of arguments the function accepts.
      */
    new (...args: string[]): GeneratorFunction;
    (...args: string[]): GeneratorFunction;
    prototype: GeneratorFunction;
}
declare var GeneratorFunction: GeneratorFunctionConstructor;

interface Generator<T> extends IterableIterator<T> {
    next(value?: any): IteratorResult<T>;
    throw(exception: any): IteratorResult<T>;
    return(value: T): IteratorResult<T>;
    [Symbol.iterator](): Generator<T>;
    [Symbol.toStringTag]: string;
}

Looks good!

Got a little lost in the first post, but I'm going to write what I understood, and you guys can correct me if I'm wrong:

function *g () {
    var result: TNext = yield <TYield>mything()
}

g cannot contain the statement return.
All yield keywords must be treated as the same type (called TNext) that can be a union.
All calls to an ginst (an instance of g) of the form ginst.next(...) must pass a parameter of type TNext (assuming that's only if TNext is not null, I don't know if TNext can be null).
Any value on the right of the yield keyword must be of type TYield, and if ommitted is treated as the value undefined.
An instance of g can be typed as follows: var ginst: TYield* but then you must cast to an IterableIterator (or something similar) before calling ginst.next (just a note here - yuck?)

Is there anything important that I missed here?

Request:
A nicer way of defining generator types e.g. for a generator,

function* g(value: number) {
    while (true) {
        value+= yield value;
    }
}

something like:

var ginst: GeneratorInstance<number, number>

and

var gtype: *g(start: number)=>GeneratorInstance<number, number>;

For the following code:

ginst = g(0);
ginst.next(2);
gtype = g;

👍 for generators

edit: fixed putting *'s in all the wrong places.

... Also the lack of a return statement annoys me, I think it should be forced to have the same type as yield, and if it's a different type (and yield is being implicitly typed) the return type should force a change to the implicitly derived type for yield.
To summarise; In a generator function return is treated identically to yield.

This way I can have my generators actually end on a value that's not forced to be undefined (by Typescript).

Griffork

Griffork from what I understand, you can have return statements, just not return expressions - specifically, you can't return a value, but you can bail out from within the generator at any point.

This probably doesn't help your frustration in the return type being ignore; however, it would certainly help to get some use realistic cases for what exactly you'd like to return when a generator has terminated.

Daniel Rosenwasser (@DanielRosenwasser)

Daniel Rosenwasser (@DanielRosenwasser) not sure I understand.
I guess what you're calling a return expression is: return true;?
If that is the case, then how is a return statement different to a return expression?

Here's an example of the type of generator I was thinking of when I voiced my discomfort:

function* g (case) {
    while(true){
        switch(case) {
            case "dowork1":
                //do stuff
                case = yield "OPERATIONAL - OK";
                break;
            case "dowork2":
                //do stuff
                case = yield "OPERATIONAL - OK";
                break;
           case "shutdown":
               //do stuff
               return "COMPLETE";
        }
    }
}

Where it may execute an arbitrary amount of times, but at some point it's "completed" and it notify's it's caller that it's done.

My concern (which I have not yet researched) is that without the return statement, there might be garbage-collection problems on some systems (particularly since the whole function-state has to be suspended and resumed on a yield), which is bad if you're spawning a lot of similarly-structured generators/iterators.

It also makes the function read a lot more clearly in my opinion.

I guess what you're calling a return expression is: return true;?

That is a return statement, for which the return expression is true.

In other words, a return expression is the expression being returned in a return statement.

Where it may execute an arbitrary amount of times, but at some point it's "completed" and it notify's it's caller that it's done.

From what I understand of your example, you return "COMPLETE" to indicate that the generator is done, which I don't see as any more useful as the done property on the iterator result. We need some more compelling examples.

Though, now that I think about it, if there are multiple ways to terminate (i.e. shutdown or failure), that's when the returned value in a state-machine-style generator would be useful.

Daniel Rosenwasser (@DanielRosenwasser)

Daniel Rosenwasser (@DanielRosenwasser) got it, thanks for the clarification :).

I'd argue that a correct implementation would allow return expressions, and type them distictly from yield expressions.

Generators are commonly used in asynchronous task runners, such as co. Here is an example:

var co = require('co');
var Promise = require('bluebird');

// Return a promise that resolves to `result` after `delay` milliseconds
function asyncOp(delay, result) {
    return new Promise(function (resolve) {
        setTimeout(function () { resolve(result); }, delay);
    });
}

// Run a task asynchronously
co(function* () {
    var a = yield asyncOp(500, 'A');
    var ab = yield asyncOp(500, a + 'B');
    var abc = yield asyncOp(500, ab + 'C');
    return abc;
})
.then (console.log)
.catch (console.log);

The above program prints 'ABC' after a 1.5 second pause.

The yield expressions are all promises. The task runner awaits the result of each yielded promise and resumes the generator with the resolved value.

The return expression is used by the task runner to resolve the promise associated with the task itself.

In this use case, yield and return expressions are (a) equally essential, and (b) have unrelated types that ideally would be kept separate. In the example, TYield is Promise<string> and TReturn is string. There is no reason why they would be conflated into one type in a task runner.

Troy Gerwien (@yortus)

Troy Gerwien (@yortus) I'm not sure what you're asking for is at all possible, or if it makes any sense, I'll try to explain where I'm confused.

The only way to start or resume a generator is the generator's .next function. This function takes a single argument (which is supplied in place of the yield expression) and returns a single value (which is the value to the right of the yield expression).

The following Javascript:

function*g() {
    var a = yield "a";
    var b = yield a + "b";
    var c = yield b + "bc";
    return 0;
}
var ginst = g();

console.log(g.next() + g.next("a") + g.next("a"));
return g.next("");

Is the equivalent to

console.log(("a") + ("a" + "b") + ("a" + "bc"));
return 0;

But what happens if I try:

var done = false;
var value;
while (!done) {
    value = ginst.next(value);
    console.log(value);
}

I get:

"a"
"ab"
"abbc"
0

The last one is a number, meaning if ginst.next is to be called in a loop, the return type must be string|number or it may be incorrect.

It's important to note here that the proposal that yield and return are treated identically will work for co's consumption, and for Promises. If it will help I can write some example implementations.

Like that last suggestion:

interface Generator<TYield, TReturn, TNext> extends IterableIterator<TYield> {
    next(n: TNext): IteratorResult<TYield | TReturn>;
    // throw and return methods elided
}

Seems ok to lose the correctness of next when you subsume the generator into an iterable/iterator.

Does that solve drawback #3?
Not sure if I like T*, this looks clearer:

function *g(): Generator<number, string, any>  {
    yield 0;
    return "";
}
var a: Iterable<number|string> = g();

// lose correctness
var b: Iterable<number> = g();

// consider using *T for better symmetry instead of T*
var c: *number = g();

Troy Gerwien (@yortus)

Troy Gerwien (@yortus) Typescript lets you type Javascript. It only (so far) supplies semantics for describing how raw javascript works, not for describing how libraries work.
What your asking for is a) not required for the first implementation of generators (thus Jason Freeman (@JsonFreeman) telling you to create a new thread for this) and b) only describes one use of generators, without supporting any other uses of generators (e.g. what I described).

All of these libraries that do async that are common now (e.g. angular, co, etc.) currently all use promises, but that doesn't mean in the next year promises are going to be the most common way of doing async with generators, we don't know that yet.
What you would do is practically prevent other ways of using generators from being able to emerge, due to Typescript having built in support for promises (only), and no other ways.

Why, if you're going to support using generators with promises, can't I also insist that the Typescript team support how I'm going to use generators (because yes, it is possible, just not very feasible and not useful for more than that one way of using generators).

My initial points for async (which you quoted out of context) were in the context that async would be just as common (not more so) than iterators, and they should be supported equally. If you're going to argue support for a specific way of doing async, then I argue for support for any other way of doing async.
Which will (imo) will end up with an over-the-top bloated unmaintainable typing system.

After some discussion, here is the current plan:

For now, yield expressions will be required to have a common supertype. For additional discussion, let's use issue Consider using union types for function return expressions #921
For now, return expressions will be allowed, but ignored. When we have boolean literal types, we will track the return expression's type correctly, instead of hacking it temporarily. This is outlined in Boolean literal types and return type propagation for generators #2983
Yield expressions themselves will have type any, but we will also revisit this when we do the return expressions after boolean literal types. My plan is that we will allow the user to provide a parameter type for next, and all the yield expressions have to be that type.
I will temporarily remove the Generator type from es6.d.ts, as we will add a better one when we have boolean literal types.

As a result, I will add good support for generators as iterables for now. This is because it is possible to support that use case well now, whereas supporting the async use case should be built on top of boolean literals. Async use cases will still be possible, just not strongly typed. After boolean literals, we can better support async use cases.

Jason Freeman (@JsonFreeman)

Jason Freeman (@JsonFreeman) I'm curious, what was the reasoning behind ignoring return types vs using option 5 (special hack)?

Jason Freeman (@JsonFreeman)

Jason Freeman (@JsonFreeman) sounds like a good start. 'For now, yield expressions will be required to have a common supertype'. This means that for any of the async examples I've given in this thread to compile, they will have to be explicitly annotated with TYield=any, since their yield operands don't have a common supertype. Is that right? And all the yield expressions will have to be explicitly typed too for now. And TReturn too. Basically everything.

Griffork TypeScript would know nothing about promises under my proposal. Not sure why you think that. I wholeheartedly agree with your point, but it just doesn't apply to the technique I proposed.

The reasoning behind not doing the hack (option 5) is that we have a better long term solution that is not a hack. Doing the hack would give us some value in the short term and none in the long term. And while I think tracking the return type is important, I do not think it is urgent enough to warrant the hack that we will later remove.

For the common type issue, yes you must provide any or the union type that you're interested in. Again, issue #921 is relevant here. Btw, if your generator is contextually typed, then we do infer the union type, so if you pass it directly to co.wrap, you probably should be fine not supplying the type.

Yield expressions themselves will have to be explicitly typed inline for now, yes.

OK I can live with that for a version or two. Better yield modeling is a must in the longer term. Looking forward to that.

Jason Freeman (@JsonFreeman)

Jason Freeman (@JsonFreeman) yep, fair.
I like the contextual typing, that will make things easier.

I would love to have async/await compile to ES5 prioritized. Can you elaborate why generators/yield gets preference?

Carl in 't Veld (@cveld)

Carl in 't Veld (@cveld) because async/await is sugar around generators and promises. And, of course, generators is standard already and async/await not, hence subject to change (rare chances, but anyway).

Carl in 't Veld (@cveld)

And when do you expect that ES5 compilation for generators/yield will
become available?

2015-09-07 18:17 GMT+02:00 Arthur Stolyar notifications@github.com:

Carl in 't Veld (@cveld) https://github.com/cveld because async/await is sugar around
generators and promises. And, of course, generators is standard already and
async/await not, hence subject to change (rare chances, but anyway).

—
Reply to this email directly or view it on GitHub
#2873 (comment)
.

This issue has been handled by #3031. we should file a different issue for the remaining portions of this proposal that were not covered by #3031.

Carl in 't Veld (@cveld)

Carl in 't Veld (@cveld) there is no time line for this at the point.

Navigation Menu

Repository navigation

Proposal for generators design #2873

Basic support for generators

Type annotation on a generator

Inferring the type of a generator

The `*` type constructor

Drawbacks of this basic design

Advanced additions to proposal

82 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Proposal for generators design #2873

Description

Basic support for generators

Type annotation on a generator

Inferring the type of a generator

The * type constructor

Drawbacks of this basic design

Advanced additions to proposal

Activity

JsonFreeman commented on Apr 24, 2015

DanielRosenwasser commented on Apr 24, 2015

CyrusNajmabadi commented on Apr 24, 2015

Griffork commented on Apr 28, 2015

Griffork commented on Apr 28, 2015

DanielRosenwasser commented on Apr 28, 2015

Griffork commented on Apr 28, 2015

DanielRosenwasser commented on Apr 28, 2015

DanielRosenwasser commented on Apr 28, 2015

Griffork commented on Apr 28, 2015

yortus commented on Apr 28, 2015

Griffork commented on Apr 28, 2015

jbondc commented on Apr 28, 2015

82 remaining items

Griffork commented on May 1, 2015

JsonFreeman commented on May 1, 2015

Griffork commented on May 1, 2015

yortus commented on May 1, 2015

JsonFreeman commented on May 1, 2015

yortus commented on May 1, 2015

Griffork commented on May 1, 2015

cveld commented on Sep 7, 2015

NekR commented on Sep 7, 2015

cveld commented on Sep 7, 2015

mhegazy commented on Sep 8, 2015

mhegazy commented on Sep 8, 2015

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

The `*` type constructor