Generator: infer the type of yield expression based on yielded value

[Retsam]

Search Terms

generator, iterator, yield, type inference, redux-saga, coroutine, co, ember-concurrency

Suggestion

There are a number of JS patterns that require a generator to be able to infer the type of a yield statement based on the value that was yielded from the generator in order to be type-safe.

Since #2983 was something of a "catch-all" issue for generators, now that it has closed (🙌) there isn't a specific issue that tracks this potential improvement, as far as I can tell. (A number of previous issues on this topic were closed in favor of that issue, e.g. #26959, #10148)

Use Cases

Use Case 1 - coroutines

A coroutine is essentially async/await implemented via generators, rather than through special language syntax. [1] There exist a number of implementations, such as Bluebird.coroutine, the co library, and similar concepts such as ember-concurrency

In all cases, it's pretty much syntactically identical to async/await, except using function* instead of async function and yield instead of await:

type User = {name: string};
declare const getUserId: () => Promise<string>;
declare const getUser: (id: string) => Promise<User>;

const getUsername = coroutine(function*() {
    // Since a `Promise<string>` was yielded, type of `id` should be string.
    const id = yield getUserId(); 
    // Since a `Promise<User>` was yielded, type of `user` should be `User`
    const user = yield getUser(id);
    return user.name;
});

Currently, there really isn't a better approach than explicit type annotations on every yield statement, which is completely unverified by the type-checker:

const getUsername = coroutine(function*() {
    const id: string = yield getUserId(); 
    const user: User = yield getUser(id);
    return user.name;
});

The most correct we can be right now, with TS3.6 would be to express the generator type as Generator<Promise<string> | Promise<User>, string, string | User> - but even that would require every the result of every yield to be discriminated between string and User.

It's clearly not possible to know what the type of a yield expression is just by looking at the generator function, but ideally the types for coroutine could express the relationship between the value yielded and the resulting expression type: which is something like type ResumedValueType<Yielded> = Yielded extends Promise<infer T> ? T : Yielded.

Use Case 2 - redux-saga

redux-saga is a (fairly popular) middleware for handling asynchronous effects in a redux app. Sagas are written as generator functions, which can yield specific effect objects, and the resulting expression type (and the runtime behavior) depend on the value yielded.

For example, the call effect can be used analogously to the coroutine examples above: the generator will call the passed function, which may be asynchronous, and return the resulting value:

function* fetchUser(action: {payload: {userId: string}}) {
   try {
      const user = yield call(getUser, action.payload.userId);
      yield put({type: "USER_FETCH_SUCCEEDED", user: user});
   } catch (e) {
      yield put({type: "USER_FETCH_FAILED", message: e.message});
   }
}

The relationship between the yielded value and the resulting value is more complex as there are a lot of possible effects that could be yielded, but the resulting type could still hypothetically be determined based on the value that was yielded.

This above code is likely even a bit tricker than the coroutine as the saga generators aren't generally wrapped in a function that could hypothetically be used to infer the yield relationship: but if it were possible to solve the coroutine case, a wrapping function for the purposes of TS could likely be introduced:

// SagaGenerator would be a type that somehow expressed the relationship 
// between the yielded values and the resulting yield expression types.
function saga<TIn, TReturn>(generator: SagaGenerator<TIn, TReturn>) { return generator; }

const fetchUser = saga(function*() {
   //...
});

---

I imagine this would be a difficult issue to tackle, but it could open up a lot of really expressive patterns with full type-safety if it can be handled. In any case, thanks for all the hard work on making TS awesome!

---

[1] As an aside, to the tangential question of "why would you use a coroutine instead of just using async/await?". One common reason is cancellation - Bluebird promises can be cancelled, and the cancellation can propagate backwards up the promise chain, (allowing resources to be disposed or API requests to be aborted or for polling to stop, etc), which doesn't work if there's a native async/await layer.

[yortus]

For reference, there's some discussion and ideas about this in #30790 (e.g. #30790 (comment)).

[rbuckton]

This is not currently possible to model in the type system, as is mentioned in #30790, as it requires some mechanism to define a relationship between a TYield and a TNext to be preserved between separate invocations.

[treybrisbane]

Two additional use cases are:

• Emulation of Haskell's do syntax for sequencing monadic actions (example)
• Emulation of Algebraic Effects (explanation, and example)

[falsandtru]

You need Rank-2 types: https://prime.haskell.org/wiki/Rank2Types

[itsMapleLeaf]

type TestAsyncGen = {
  next<T>(value: T): IteratorResult<Promise<T>, void>
}

function* test(): TestAsyncGen {
  const value = yield Promise.resolve(123)
}

I just tried this, currently it errors on Promise.resolve(123)

Type 'Promise<number>' is not assignable to type 'Promise<T>'.
  Type 'number' is not assignable to type 'T'.
    'number' is assignable to the constraint of type 'T', but 'T' could be instantiated with a different subtype of constraint '{}'.

Would it be possible to support this use case this way?

For the record, this currently works and is properly typechecked:

type TestNumberStringGen = {
  next(value: number): IteratorResult<string, number>
}

function* test(): TestNumberStringGen {
  const num = yield "123"
  return num
}

[rbuckton]

Would it be possible to support this use case this way?

No, it is not possible. Your definition of TestAsyncGen doesn't actually reflect what's happening in the generator. The definition next<T>(value: T): IteratorResult<Promise<T>, void> implies that calling next will with a value of T will produce a Promise<T>. However, what is actually happening is that you want the Promise<T> of one call to next to inform the T of a subsequent call to next:

function start(gen) {
  const result = gen.next();
  return result.done
    ? Promise.resolve(result.value)
    : Promise.resolve(result.value).then(value => resume(gen, value));
}
function resume(gen, value) {
  const result = gen.next(value);
  return result.done
    ? Promise.resolve(result.value)
    : Promise.resolve(result.value).then(value => resume(gen, value));
}

The type system has no way to handle that today.

What you would need is something like #32695 (comment), where calling a method can evolve the this type:

interface Start<R> {
  next<T>(): IteratorResult<Promise<T>, Promise<R>> & asserts this is Resume<T, R>;
}
interface Resume<T, R> {
  next<U>(value: T): IteratorResult<Promise<U>, Promise<R>> & asserts this is Resume<U, R>;
}

If such a feature were to make it into the language, then you would be able to inform the T of a subsequent call to next based on the return type of a preceding call to next.

[spion]

Is it possible to go for a simpler alternative? Something like having an second, richer model for generator functions:

Rough sketch:

interface BaseYieldType {
  (arg:any):any
}

interface Coroutine<
  Args extends any[],
  RetType,
  BaseCoroutineProduction,
  YieldType extends BaseYieldType
> {
  (...args:Args):Generator<BaseCoroutineProduction, RetType, any>
  __yield: YieldType; // replace with some TS only symbol maybe
}

Libraries would be able to specify the argument type, e.g.

type AwaitingYield = <T>(p:Promise<T>) => T;

declare function coroutine<Args extends any[], Ret>(
  genfn: Coroutine<Args, Ret, Promise<unknown>, AwaitingYield>
) : (...args:Args) => Ret;

which would cause TS to infer the type of yield expressions here:

// This type cast wont be necessary, instead the type will be
// inferred from the specified Coroutine<...> argument to coroutine()

let x = coroutine(function* f() {
  let a = yield Promise.resolve(1);
  let b = yield Promise.resolve(true);
  return Promise.resolve('a')
}) as Coroutine<[], Promise<string>, Promise<any>, AwaitingYield>)

[ccorcos]

I'm very interested in support for algebraic effects really just for one use-case:

I have a database that I want to be able to run async with a backend or sync in memory.

I believe coroutines / generators are a perfect way to do this. The types don't quite work out but I feel like its pretty close:

export type API = {
	get: {
		request: { type: "get"; id: string }
		response: { id: string; value: any }
	}
	set: {
		request: { type: "set"; id: string; value: any }
		response: void
	}
}

function syncApi<T extends keyof API>(
	request: API[T]["request"]
): API[T]["response"] {
	return {} as any
}

async function asyncApi<T extends keyof API>(
	request: API[T]["request"]
): Promise<API[T]["response"]> {
	return {} as any
}

// Define a custom IterableIterator class.
interface APIGenerator {
	next<T extends keyof API>(
		response: API[T]["response"]
	): IteratorResult<API[T]["request"], void>
	[Symbol.iterator](): APIGenerator
}

// Some helpers
function get(id: string): API["get"]["request"] {
	return { type: "get", id }
}

function set(id: string, value: any): API["set"]["request"] {
	return { type: "set", id, value }
}

// Reusable logic that works for both sync and async code.
// It appears to typecheck, but the return value from yield doesn't resolve.
function* logic(): APIGenerator {
	const x = yield get("1") // const x: API[T]["response"]
	x.id // 💥
	x.value // 💥
	const y = yield set("2", 3) // const y: API[T]["response"]
}

// Here's how we can evaluate both sync and async
function runSync() {
	const gen = logic()
	let request = gen.next() // 🤔 what do we pass here?
	while (request.value !== undefined) {
		request = gen.next(syncApi(request.value))
	}
}

async function runAsync() {
	const gen = logic()
	let request = gen.next() // 🤔 what do we pass here?
	while (request.value !== undefined) {
		request = gen.next(await asyncApi(request.value))
	}
}

playground

Two problems:

1. the return type from yield isn't quite inferred correctly.
2. its unclear what to pass to the generator the first time calling .next().

I understand that there is an internal technical limitation for this to work, but I thought I'd add my use-case here to try to motivate why it would be useful!

[ccorcos]

I came up with a simpler way to do it that involves a type-cast helper function. Seems like macros would be useful here.

(no playground link because it hadn't upgraded to 3.6 yet)

Code

// Algebraic Effects API.
//
// The goal here is to define a sync API and an async API for a database without having
// to duplicate logic.
//
// It seems to come with the overhead of duplicative syntax.
//

// The two sync API datase API functions
function get(args: { id: string }): { id: string; value: any } {
	return {} as any
}

function set(args: { id: string; value: any }): {} {
	return {} as any
}

const api = { get, set }
const apiNames = Object.keys(api) as Array<APIName>

type API = typeof api
type APIName = keyof API

type APIRequest<N extends APIName = APIName> = Parameters<API[N]>[0]

type APIResponse<N extends APIName = APIName> = ReturnType<API[N]>

// Generator yields Messages that the handler will process
type APIMessage<N extends APIName = APIName> = {
	apiName: N
	request: APIRequest<N>
}

// API handlers that service requests.
function syncApiHandler<N extends APIName>(
	message: APIMessage<N>
): APIResponse<N> {
	return {} as any
}

async function asyncApiHandler<N extends APIName>(
	message: APIMessage<N>
): Promise<APIResponse<N>> {
	return {} as any
}

/**
 * Using Typescript 3.6 Generator type.
 * - yields `Message`
 * - returns `any`
 * - next argument is `APIResponse`
 *
 * Note: we cannot define a type in Typescript that lets us infer:
 *
 * 	const result: APIResponse<T> = yielded (message as Message<T>)
 *
 * Thus, we use `n` and `m` helpers below.
 *
 */
type LogicGenerator = Generator<APIMessage, any, APIResponse>

/**
 * Helper function to narrow the response type from `yield`.
 * Needs to be used with the same `keyof m`.
 */
declare const n: {
	get(response: APIResponse): APIResponse<"get">
	set(response: APIResponse): APIResponse<"set">
}

/**
 * Helper to construct messages passed to `yield`.
 * Needs to be used with the same `keyof n`.
 */
declare const m: {
	get(request: APIRequest<"get">): APIMessage<"get">
	set(request: APIRequest<"set">): APIMessage<"set">
}

// Reusable logic that works for both sync and async code.
function* logic(): Generator<APIMessage, any, APIResponse> {
	// Plumbing is required to effectively `await` a sync or async interface using `yield`.
	const setRequest: APIRequest<"set"> = { id: "hello", value: "world" }
	const message: APIMessage<"set"> = m.set(setRequest)
	// After yield does not infer APIResponse<"message">
	const response: APIResponse = yield message
	// This is a cast so it's important that `n.[apiName]` is the same as `m.[apiName]`.
	const setResponse: APIResponse<"set"> = n.set(response)

	// We can chain these together to make it easier to read.
	const a = n.set(yield m.set({ id: "hello", value: "world" }))
	const { id, value } = n.get(yield m.get({ id: "hello" }))

	// prettier-ignore
	// Using custom indentation helps group together all of the redundant `set` that is
	// prone to human error.
	const b = n.set(
			yield m.set({ id: "hello", value: "world" }))

	// Ideally we could define a type for Generator that `yield` would understand how to infer.
	// Then we could get away with the code below.
	const c = yield m.set({ id: "hello", value: "world" })
}

// Here's how we can evaluate both sync and async
function runSync() {
	const gen = logic()
	let request = gen.next()
	while (request.value !== undefined) {
		request = gen.next(syncApiHandler(request.value))
	}
}

async function runAsync() {
	const gen = logic()
	let request = gen.next()
	while (request.value !== undefined) {
		request = gen.next(await asyncApiHandler(request.value))
	}
}

[ccorcos]

I just ran into this limitation again. @RyanCavanaugh what are your thoughts on implementing typed algebraic effects. Is this something that is realistically not going to happen anytime soon? As an avid TypeScript user, this issue as well has higher-kinded types are the only real roadblocks I've run into. But it sounds like it might be a fundamental limitation of the way TypeScript was designed...

[evelant]

Another popular library that runs into this issue is mobx-state-tree. Asynchronous state updates are modeled with generators. This issue combined with #35105 causes a bunch of any to creep into your MST actions quite easily without anyone noticing.

[pqnet]

While having a strong typechecking on the executor part would be great, the biggest limitation for implementing coroutines at the moment is that yield expression can't be polymorphic, i.e. in the expression
const x = yield y
the type of x is univocally determined by the type of the generator, and cannot depend in any way from the type of y.

On the executor side I would be happy to have a method next(value: never): unknown which I need to explicitly cast to the expected type if I could express that inside the function* body the yield expression is typed according to a certain polymorphic function type such as <T>(yielded: MyPromise<T>): T.

While this would have messier code on the executor side, the "client" side for coroutine libraries would stay clean.
For now the best you can do is this:

function* unwrap<T>(yieldExpr: MyPromise<T>): Generator<MyPromise<T>, T, T> {
    const unwrapped = yield yieldExpr;
    return unwrapped;
}
function* mygen(): Generator<unknown, void, never>{
    const x = yield* unwrap(MyPromise.resolve(5));
    const y = yield* unwrap(MyPromise.resolve('hello'));
}

There are three issues, as a DSL developer, that I have with this:

1. the aestetics of having to use a more intricated syntax
2. nothing preventing the use of yield expression, that can generate never typed variables
3. the unwrap function appears to be able to transform any MyPromise<T> into T values synchronously, while it actually only works if it is invoked with the previous syntax on the proper executor

[pqnet]

Also note that the type of next is already broken on executor side, since it can always be invoked without parameters although for generators which have a NextT it is legal to do so only the first time it is invoked.

[arcanis]

I've opened a proposal for a fix here: 💡 Yield Overrides #43632

It goes the other way around (the yielded expression includes the returned type, rather than the generator driving it), but I think it's a reasonable approach that mirrors the preexisting ThisType API, and solves most of the relevant use cases. An implementation is available in a branch as well, see the thread for details.

[scorbiclife]

Here's something that's type-safe and compatible with current Typescript.
Is it possible to make a decorator that infers a normal generator into this more specific type?
(+ type inference when the user writes the generator too)

// Increment / Decrement from:
// https://stackoverflow.com/questions/54243431/typescript-increment-number-type

// We intersect with `number` because various use-cases want `number` subtypes

type ArrayOfLength<N extends number, A extends any[] = []> =
    A["length"] extends N ? A : ArrayOfLength<N, [...A, any]>;
type Inc<N extends number> = number & [...ArrayOfLength<N>, any]["length"]
type Dec<N extends number> = number & (ArrayOfLength<N> extends [...infer A, any] ? A["length"] : -1);

type RangeType<Start extends number, End extends number> =
    number & (
        Start extends End
        ? never
        : Start | RangeType<Inc<Start>, End>);


// Generator definition

type Yield<YieldValue, NextValue> = (_: YieldValue) => NextValue
type AnyYield = Yield<never, unknown>
type YieldValue<Y extends AnyYield> = Y extends Yield<infer YV, unknown> ? YV : never;
type NextValue<Y extends AnyYield> = Y extends Yield<never, infer NV> ? NV : never;

interface SpecificGenerator<Ys extends AnyYield[], R>
    extends Generator<YieldValue<Ys[number]>, R, NextValue<Ys[number]>> {
    // `next<I extends 0>(): ...` is also valid,
    // I just used an optional param because it gives better intellisense.
    next<I extends 0>(value?: any): IteratorYieldResult<YieldValue<Ys[0]>>;
    next<I extends RangeType<1, Ys["length"]>>(value: NextValue<Ys[Dec<I>]>):
        IteratorYieldResult<YieldValue<Ys[I]>>;
    next<I extends Ys["length"]>(value: NextValue<Ys[Dec<I>]>): IteratorReturnResult<R>;
    next<I extends number>(value: NextValue<Ys[Dec<I>]>): IteratorResult<YieldValue<Ys[I]>, R>;
    [Symbol.iterator](): this;
}


// Example 1

type ExampleGenerator = SpecificGenerator<[(_: number) => string, (_: number) => number], string>
const g = function* () {
    const a = (yield 3) as string;
    const b = (yield a.length) as number;
    return a + b.toString();
} as () => ExampleGenerator;

const gRunner = function (egf: () => ExampleGenerator) {
    const eg = egf();
    const { value: n } = eg.next<0>();
    const { value: m } = eg.next<1>("a".repeat(n));
    const { value: result } = eg.next<2>(m);
    return result;
}

// Example 2

// From https://curiosity-driven.org/monads-in-javascript#do

// Monad

type Monad<T> = {
    bind<U>(f: (t: T) => Monad<U>): Monad<U>
}

type MonadInnerType<MT extends Monad<any>> = MT extends Monad<infer T> ? T : never;


// Maybe

interface Maybe<T> extends Monad<T> { };

class Just<T> implements Maybe<T> {
    value: T;

    constructor(value: T) {
        this.value = value;
    }

    bind<U>(f: (value: T) => Monad<U>): Monad<U> {
        return f(this.value);
    }

    toString() {
        return `Just(${this.value})`;
    }
}

const Nothing = {
    bind<U>(_: (value: never) => Monad<U>): Monad<U> {
        return this as Monad<U>;
    },

    toString() {
        return "Nothing";
    },
} as Maybe<never>;


type MonadUnwrappers<Vs extends any[]> = { [I in keyof Vs]: (_: Monad<Vs[I]>) => Vs[I] };

function doNotation<Vs extends any[], T>(genFunc: () => SpecificGenerator<MonadUnwrappers<Vs>, Monad<T>>) {
    const gen = genFunc();
    function step<I extends number>(value: Vs[Dec<I>]): Monad<T> {
        const result = gen.next<I>(value);
        if (result.done) {
            return result.value;
        }
        type V = Vs[I];
        return result.value.bind<T>((v: V) => step<Inc<I>>(v));
    }
    return step<0>(undefined);
}

const sampleDoBody = function* () {
    var value = (yield new Just(5)) as number;
    var value2 = (yield new Just(6)) as number;
    return new Just(value + value2);
} as () => SpecificGenerator<[(_: Just<number>) => number, (_: Just<number>) => number], Monad<number>>;

const result = doNotation(sampleDoBody);

[SamB]

@rbuckton wrote (#32523 (comment)):

However, what is actually happening is that you want the Promise<T> of one call to next to inform the T of a subsequent call to next:

Dang, and for a moment there I thought what we were missing was a way to parameterize Generator with the relationship between those two types, but you're right, those aren't even related to the same call.

Is there a programming language that can handle that?

[rixtox]

When you define a generator function in JavaScript, the semantics of the yield operator is determined at call site. For example, if the caller is an async-runner like co, then yield would work like await. This makes the yield semantics to be determined like how a function call inherits the this value.

We already have a way to type this in a way like it's part of the function's parameters. Maybe we can make a similar mechanism to type yield.

type Awaiter = <T>(value: T) => Awaited<T>;
function* example(yield: Awaiter) {
    const value1 = yield Promise.resolve(1); // infer typeof value1 = number
    const value2 = yield Promise.resolve('hello'); // infer typeof value2 = string
}
await co(example);

You can still explicitly type the generator type or rely on type inference to determine its type. The example above has inferred type Generator<Promise<number> | Promise<string>, void, unknown>.

Update: found out about #36967 which is proposing exactly this.