Typescript: Existential type?

[isiahmeadows]

Here's a case where I need a few existentials. It's for a definition file, where I need to have parameters for Binding and Scheduler, but it doesn't matter to me what they are. All I care about is that they're internally correct (and any doesn't cover this), and I'd rather not simulate it by making the constructor unnecessarily generic.

The alternative for me is to be able to declare additional constructor-specific type parameters that don't carry to other methods, but existentials would make it easier.

export interface Scheduler<Frame, Idle> {
    nextFrame(func: () => any): Frame;
    cancelFrame(frame: Frame): void;
    nextIdle(func: () => any): Idle;
    cancelIdle(frame: Idle): void;
    nextTick(func: () => any): void;
}

export interface Binding<E> extends Component {
    binding: E;

    patchEnd?(): void;

    patchAdd?(
        prev: string | E | void,
        next: string | E | void,
        pos: number,
    ): void;

    patchRemove?(
        prev: string | E | void,
        next: string | E | void,
        pos: number
    ): void;

    patchChange?(
        oldPrev: string | E | void,
        newPrev: string | E | void,
        oldNext: string | E | void,
        newNext: string | E | void,
        oldPos: number,
        newPos: number
    ): void;
}

export class Subtree {
    constructor(
        onError?: (err: Error) => any,
        scheduler?: type<F, I> Scheduler<F, I>
    );

    // ...
}

export class Root extends Subtree {
    constructor(
        component: type<E> Binding<E>,
        onError?: (err: Error) => any,
        scheduler?: type<F, I> Scheduler<F, I>
    );

    // ...
}

[rotemdan]

Hi again :),

I'll try my best to clarify what this means (hopefully my understanding isn't flawed - at least I hope). I took a simple example as a starting point: of a generic type, and a non-generic container type. The container contains a property content which accepts a value matching any instantiation of the generic type, as long as it follows its internal "shape":

interface MyType<T> {
    a: T;
    b: T[];
}

interface Container {
    content<E>: MyType<E>
}

Of course the above doesn't currently compile, but it demonstrates another approach to a possible syntax.

The idea is that the affected property or variable is "modified" by a type parameter, which is always inferred (for the 'write' direction it is conceptually similar to a generic setter method setContent<E>(newContent: MyType<E>) where E is always inferred when called). That type parameter can be passed to any secondary generic type, or even be used to define an anonymous generic type:

interface Container {
    content<E>: {
        a: E;
        b: E[];
    }
}

One thing to note is that if no constraint is imposed over E. It can always be matched with any, meaning that perhaps surprisingly, the following might work:

const c: Container = {
    content: {
        a: 12,
        b: ["a", 6, "c"]
    }
}

Since E can be substituted with any, any type with properties a and b and where b is an array can satisfy MyType<E>.

Even if E was constrained:

interface Container {
    content<E extends number | string>: MyType<E>
}

The above example can still be matched by E = number | string (Edit: or in practice technically also E = any as well, but I was just giving that as an illustration).

Maybe what we need is an "exclusive or" type constraint, that would constrain E to be either number or string, but not the possibility of both:

interface Container {
    content<E extends number ^ string>: MyType<E>
}

const c: Container = {
    content: {
        a: 12,
        b: ["a", 6, "c"]
    }
} // <- Error this time: can't match either `number` or `string` to unify with `MyType`

Another thing to note is that the resulting container type would probably be used mostly as an abstract one, to be inherited by classes or other interfaces, or maybe serve as a constraint for type arguments. When used on its own, trying to read content would return a value whose type always falls back to its existential types' constraints.

[isiahmeadows]

@rotemdan I see what you mean. That could work (provided it works for arguments, too). But how would something like this work? (My idea of type<T> Foo<T> similar to Haskell's forall a. Foo a has a similar potential issue, too.)

interface C {
  prop<T>: Array<T>;
}

let c: C = {prop: [2]}
let value = c.prop[0] // What type is this?

With the information provided, this is an opaque type AFAIK.

[rotemdan]

@isiahmeadows

My approach was just an intuitive instinct - a starting point. I can't say I'm an expert in this area but I thought it might be a meaningful contribution.

I felt it might look simple and aesthetically elegant to modify the identifier itself, though that approach still doesn't cover all possible use cases. It only covers:

Properties:

interface C {
  prop<E>: { a: E; b: E[] };
}

Variable declaration (const, let and var):

let c<E>: { a: E; b: E[] }

Function, method and constructor parameters:

function doSomething(c<E>: { a: E; b: E[] }, s: string);

interface I {
  doSomething(c<E>: { a: E; b: E[] }, s: string);
}

class C {
  constructor(c<E>: { a: E; b: E[] }, s: string);
}

This syntax doesn't provide a solution to introduce explicit existential-only type variables into other scopes like entire interfaces or classes, or functions. However since these scopes do allow for "universal" type parameters, these type parameters can be "wrapped" by existentials at the use site:

interface Example<T> {
  a: T;
}

let x<E>: Example<E>;

I'm reading about forall in Haskell (I don't think I understand it 100% at this point) and investigating the flexibility of an equivalent type <T> style syntax. I would be interested in seeing more examples for the scopes where type <T> can be used. Can it wrap arbitrary code blocks? can it wrap type aliases? entire constructors, getters and setters, etc?

[isiahmeadows]

@rotemdan I'd say the easiest way to understand existentials is through Haskell's version (Haskell/etc. normally leaves it implicit). Basically, it's a lot like Scheduler<any, any>, except it still validates you're implementing Scheduler with the right internal types.

As a special case, consider polymorphic functions as an existing common special case:

// TypeScript
type Flattener = <T>(arg: T[][]) => T[];
type Flattener = type<T> (arg: T[][]) => T[];

-- Haskell's equivalent
type Flattener = [[a]] -> [a]
type Flattener = forall a. [[a]] -> [a]

[rotemdan]

• In what code positions can type<T> be used? From your examples so far it seems like it could fit in variable declarations, properties, function and constructor parameters and type aliases. What about entire interfaces, methods, constructors?

• Since TypeScript has the any type and unions like number | string. How can the compiler decide whether a literal, say { a: 1, b: [1, "x", "y", 4] } is compatible with a polymorphic type, say type <E> { a: E, b: E[] } since E can always be unified with any? (or number | string etc).

_Edit: instantiation -> literal_

[rotemdan]

@isiahmeadows

I apologize I forgot to answer your question about:

interface C {
  prop<T>: Array<T>;
}

let c: C = {prop: [2]}
let value = c.prop[0] // What type is this?

When I mentioned that it is "mostly useful in the write direction" I meant that in general it improves type safety only when written to. When read from, the type falls back to a supertype based on the constraint for the existential type parameter (which here is not provided, so I guess can be assumed to be T extends any). So I believe the resulting type of c.prop[0] should be any, unfortunately, unless more sophisticated flow analysis is applied (which might be able to specialize the type only for the particular variable c).

Based on what I read about 'opaque' types so far, I believe this may qualify as one.

_Edit: my personal feeling about this is that it is just one more example that demonstrates the 'flakiness' of mutable variables. If all TS variables and properties were immutable, the compiler could easily keep track on the 'internal' types held within an entity bound to an existential type, since once it is first inferred, it cannot be changed anymore. Due to this and many other reasons I'm personally making an effort to come up with a plan to try to move away from mutable variables in my own programming.. ASAP :) ._

[rotemdan]

I'll try to demonstrate how this can work with type inference and flow analysis:

For the type:

interface C {
  prop<E>: {
    a: E;
    b: E[];
  }
}

An instance would provide a temporary instantiation, that would be determined by type inference and flow analysis, for example, when a literal is assigned:

let x: C = {
  prop: {
    a: 12,
    b: [1, 2, 3]
  }
}

The declared type of x would remain C but the actual one would be specialized to { prop: { a: number; b: number[] } } (I'm ignoring, for now, the issues with any inference I mentioned earlier).

Trying to assign:

x.prop.b[2] = "hi";

Should fail, however, reassigning x itself with a value implying a different instantiation might work, e.g.:

x = {
  prop: {
    a: "hello",
    b: ["world"]
  }
}

If x was declared with const then the "apparent" type of x would be permanently locked to { prop: { a: number; b: number[] } }.

This is at least how I imagine it could work.

_Edit: fixed code examples_

---

_Edit 2:_

After thinking about this for a while, I'm wondering whether prop should be allowed to be reassigned with a value representing a different instantiation as well, e.g.:

x.prop = {
    a: "hello",
    b: ["world"]
}

If that would be allowed (I mean, for both the cases where x was declared as let and const), then flow analysis might need to become more sophisticated as it would need to track the change of type for 'deep' properties in the object tree of x.

[zpdDG4gta8XKpMCd]

forgive my ignorance, isn't wrapping into a closure would be a commonly accepted answer to existential types problem?

[isiahmeadows]

Not in the case of declaration files, where you almost never see that.

[cameron-martin]

@isiahmeadows Surely the type of c.prop[0] in your example would be type<T> T with your proposed syntax?

[isiahmeadows]

@cameron-martin

Surely the type of c.prop[0] in your example would be type<T> T with your proposed syntax?

That is the correct understanding, but it was @rotemdan's proposed syntax, not mine - I was just translating a type between the two. The main question I had was this: what is type<T> T equivalent to?

[cameron-martin]

@isiahmeadows possibly Object?

[isiahmeadows]

@cameron-martin Can't be Object, since Object.create(null), an object by ES spec, should also be assignable to it, and Object.create(null) instanceof Object is false.

[pelotom]

For anyone interested in using existential types right now via the negation of universal types, the type annotation burden of doing so has been greatly reduced thanks to recent type inference improvements.

type StackOps<S, A> = {
  init(): S
  push(s: S, x: A): void
  pop(s: S): A
  size(s: S): number
}

type Stack<A> = <R>(go: <S>(ops: StackOps<S, A>) => R) => R

const arrayStack = <A>(): Stack<A> =>
  go => go<A[]>({
    init: () => [],
    push: (s, x) => s.push(x),
    pop: s => {
      if (s.length) return s.pop()!
      else throw Error('empty stack!')
    },
    size: s => s.length,
  })

const doStackStuff = (stack: Stack<string>) =>
  stack(({ init, push, pop, size }) => {
    const s = init()
    push(s, 'hello')
    push(s, 'world')
    push(s, 'omg')
    pop(s)
    return size(s)
  })

expect(doStackStuff(arrayStack())).toBe(2)

[cameron-martin]

@isiahmeadows I'm guessing what we're looking for here is a top type. Surely this can be build from a union of {} and all the remaining things that are not assignable to {}, e.g. {} | null | undefined.

However, it would be nice to have a top type built in.

[isiahmeadows]

@cameron-martin Look here

[jack-williams]

@isiahmeadows @cameron-martin

The main question I had was this: what is type<T> T equivalent to?

The existential is only (alpha) equivalent type<T> T. You can eliminate the existential to a skolem constant T, but that will only be equivalent to itself. An existential variable is assignable, but not equivalent, to Top.

Edit: An existential is assignable -> An existential variable is assignable

[isiahmeadows]

@jack-williams Yeah...I meant it as "what is the smallest non-existential type type<T> T is assignable to", not formal nominal equivalence.

[jack-williams]

Understood! By equivalence I wasn't sure if you wanted assignability in both directions.

[isiahmeadows]

@jack-williams Assignability the other way (let foo: type<T> T = value as {} | null | undefined) would just be application: just let T = {} | null | undefined. (That part was implied.)

[jack-williams]

@isiahmeadows

I think I was (am) confused on the syntax, and my early comment also missed a word. It should have read:

An existential variable is assignable, but not equivalent, to Top.

I read the earlier comment:

Surely the type of c.prop[0] in your example would be type<T> T with your proposed syntax?

and starting parsing type<T> T as just a variable, but the syntax should really mean exists T. T.

In that sense what I intend is: c.prop[0] should be type T and not type <T> T, and that T is assignable to Top but not the other way round.

When you write: let foo: type<T> T = value as {} | null | undefined) and mean that type <T> T is equivalent to Top then I agree.

TLDR; I agree that type<T> T is equivalent to top, but c.prop[0] would have type T, not type<T> T. I got muddled on syntax.

Apologies for confusion.

[cameron-martin]

In that sense what I intend is: c.prop[0] should be type T and not type <T> T, and that T is assignable to Top but not the other way round.

@jack-williams I don't see how it could be T - there is no T in scope at this point.

[isiahmeadows]

@jack-williams Edit: Clean this up so it's a little easier to digest.

1. I mean "structurally equivalent" in that both are assignable to each other, if that helps:

   type unknown = {} | null | undefined
   declare const source: any
   declare function consume<T>(value: T): void
   
   // Both of these check iff they are structurally equivalent
   consume<type<T> T>(source as unknown)
   consume<unknown>(source as type<T> T)
   

2. type<T> T is supposed to be "forall T. T", not exists T. T. True existentially quantified types would be essentially opaque, and there's not really a lot of use for that IMHO when unknown and the proposed nominal types would address 99% of use cases existentially quantified types could solve.

3. To clear up any remaining confusion regarding the syntax:

   • My proposal is adding a type<T> T as a type expression.
   • @rotemdan proposed here to instead use prop<T>: T as an object/interface property.
   • See my next comment for explanation on how these compare.

(I kind of followed the common miswording of "existential" instead of "universal", when it's really the latter. Not really something specific to TS - I've seen it in Haskell circles, too.)

[isiahmeadows]

@cameron-martin (re: this comment)

interface C {
  // @rotemdan's proposal
  prop<T>: T[];
  // My proposal
  prop: type<T> T[];
}

let c: C = {prop: [2]}
let value = c.prop[0] // What type is this?

Just thought I'd catch you out on this one and point out that c.prop itself is the quantified type, not members of it.

[jack-williams]

@cameron-martin : As @isiahmeadows says, the type of prop is quantified over. To access the array to you need to eliminate the quantifier, doing this introduces a fresh, rigid type variable T.

@isiahmeadows If type <T> T denotes forall then should that not be equivalent to bottom? My understanding was that forall T. T is the intersection of all types, and exists T. T was the union. What is the difference between 'true existential types' and the existential-like types that you get from the forall encoding?

[isiahmeadows]

@jack-williams

My understanding was that forall T. T is the intersection of all types, and exists T. T was the union.

Wait...you're correct. I got my terminology crossed up.

• forall T. T could be assigned to any type T, as it would just happen to be a particular specialization of it. (This makes it equivalent to never.)
• Any type could be assigned to exists T. T, as it would just specialize that type for that particular type. (This makes it equivalent to {} | null | undefined.)

Either way, you can still define that exists T. T in terms of forall T. T, using forall r. (forall a. a -> r) -> r, where a is existentially qualified. In my syntax, it'd look like this: type <R> (x: type <A> (a: A) => R) => R.

---

Note that for many cases, this is already possible in conditional types, where an infer keyword operator enables the common need to extract a return value from a function, like in here (which will become a predefined global type):

type ReturnType<T extends (...args: any[]) => any> =
    T extends (...args: any[]) => infer R ? R : any

[zhirzh]

@pelotom can you give a simpler snippet that highlights your implementation? perhaps one that doesn't have currying & HOFs mixed together?

[pelotom]

@zhirzh currying and HOFs are essential to encoding existential types in this way...

[zhirzh]

even so, isn't there a simpler way to showcase the approach?
i found one here but when it comes to examples, the more the merrier

[petejohanson]

I'm hitting this very issue w/ working on a binding for the upcoming V2 of jorgebucaran/hyperapp where you can optionally have a tuple like [SomeFunc<T>, T] where the T needs to be internally consistent, but shouldn't be exposed beyond that. Curious if there's any actual desire to implement this for TS.

[jcalz]

From #31894

Are these just named bounded existential types?

~In part, yes! When no implementation type exists, a placeholder type acts as a bounded existential type variable.~

Sorry I'm not sure what you're talking about. Please move along and don't write blog posts about how TypeScript is adding bounded existential types.

Hey, I think they're making fun of us!

[AnyhowStep]

So, not sure if this is the right place for it. If it isn't, just tell me and I'll hang my head in shame and leave quietly.

---

The problem

We are using a generic type, but do not care what concrete type it is.

There is no real safe or easy way to do this at the moment.

---

Existing Solutions

Use MyGenericType<any>

Pros:

• This lets MyGenericType<T> be assignable to MyGenericType<any>.

Cons:

• This lets MyGenericType<any> be assignable to every other MyGenericType<T> (unsafe)
• All reads returning T are unsafe
• All writes to T are unsafe

Here is a Playground demonstrating the MyGenericType<any> workaround and its pitfalls.

---

Use MyGenericType<ConstraintType>

Pros:

• All reads returning T are safe

Cons:

• All writes to T are unsafe
• Assigning to MyGenericType<ConstraintType> only works if T is only used in output positions
• May forget which type arguments are input, output, or both
• Cannot be used if T is both input and output
• Cannot be used if T is input

Here is a Playground demonstrating the MyGenericType<ConstraintType> workaround and its pitfalls.

---

Use MyGenericType<never>

Pros:

• All writes to T are safe

Cons:

• All reads returning T are unsafe
• Assigning to MyGenericType<never> only works if T is only used in input positions
• May forget which type arguments are input, output, or both
• Cannot be used if T is both input and output
• Cannot be used if T is output

Here is a Playground demonstrating the MyGenericType<never> workaround and its pitfalls.

---

Write a non-generic interface, IMyGenericType, to mimic MyGenericType<T>

1. When T is used as an output, substitute T with ConstraintType
2. When T is used as an input, substitute T with never

Pros:

• All reads returning T are safe (will just return ConstraintType)
• All writes to T are safe (can only write never)
• This lets MyGenericType<T> be assignable to IMyGenericType
• This does not let IMyGenericType be assignable to MyGenericType<T> (unless it's safe or T is any)

Cons:

• Creating an interface and manually substituting T can be tiresome; especially if done many times and for many libraries
• May forget which type arguments are input, output, or both

Here is a Playground demonstrating the IMyGenericType workaround and... It's lack of pitfalls (but it adds one new type per generic type we want to workaround)

---

Usually, one just uses MyGenericType<any> or writes an interface that is structurally similar to MyGenericType (or I do, at least).

---

Proposal

Introduce an existential type.

Based on @fatcerberus talking about his personal project

I'm leaning towards using the type keyword for it.
So, the solution would be,

MyGenericType<type>

In effect, it is the IMyGenericType workaround, but with far fewer cons.

Pros:

• All reads returning T are safe (will just return ConstraintType)
• All writes to T are safe (can only write never)
• This lets MyGenericType<T> be assignable to MyGenericType<type>
• This does not let MyGenericType<type> be assignable to MyGenericType<T> (unless it's safe or T is any)
• No need to manually substitute T for never or ConstraintType depending on input or output positions
• Will not forget which type arguments are input, output, or both
• Doesn't matter if T is covariant, contravariant, or invariant; it'll work and be safe

Cons:

• Requires introducing a new type!

---

Behaviour

• When used in input positions, type becomes never.
• When used in output positions and a constraint type exists, type becomes the constraint type.
• When used in output positions and no constraint type exists, type becomes unknown.

---

Use Cases

Dealing with that pesky global name!

Right now, it is declared as,

declare const name: never;

I would have preferred,

declare const name : unknown;

This would make reads safer.

---

However, we can use the existential type,

declare let name : type;
//Error, cannot assign `unknown` to `string`
const readNameError : string = name;
//Error, cannot assign `string` to `never`
name = "Hello, world";

//OK!
const readNameOk : string = name as string;
//OK!
name = "Hello, world" as never;

---

Using an arbitrary concrete type of a generic type safely

The whole reason we have this proposal in the first place.

---

TODO More use cases

[jack-williams]

If name is defined by const how can you assign to it? (or do you _want_ name defined by let?)

@AnyhowStep I think one thing that the proposal might benefit from is a comparison with inference sigils: MyGenericType<*> (#26242). What are the pros/cons between them. Is there space for both?

[AnyhowStep]

Yeah, I want name to be mutable.

I personally have never used window.name but I can certainly see use cases for letting it be mutable.

---

If they stick to const name, then making the type unknown would be way better (imo)

---

Okay, I admit that name example was... Contrived. But name really annoys me =(

[AnyhowStep]

With reference to #26242 , the two seem like different proposals.

So, it seems there is space for both.

---

It looks like partial type arguments will resolve T by attempting to infer it, or resolving to ConstraintType.

This existential type is a new type on its own (or behaves that way).
Writes to it will be never.
Reads to it will be ConstraintType (or unknown if no constraint type exists).
So, there is no type inference.

---

Also, it looks like the syntax for partial type inference means there's no new type introduced.

You cannot write the following,

declare let x : *;
declare let x : infer;
declare let x : auto;

and have TS infer the type of x based on usage.

But this proposal is an entirely new type and you could write,

declare let x : type;

And x will be unknown for reads, and never for writes.

---

Related to this,

@webstrand had a pretty cool idea,

Wouldn't it be neat if we could specify assignment rules by using the getter and setter syntax?

declare let name: {
  get this(): unknown;
  set this(value: never): unknown
};

Which reveals one pitfall of my current suggestion;
If type is used outside of a type parameter, then all reads to it will always be unknown.

I'm not too sure if that's a problem, though.
I can't think of a use case where we use it in a non-generic context and want writes to be never and reads to be a concreate type like string or Date.
Even if that idea might be cool.

---

I'm also not too attached to the idea of type being the keyword used.

My rationale was,

• It must be a valid identifier (Because I want to write declare let name : type)
• It should be an existing keyword

And type seemed to fit out of the list I found here

---

Oh, I was thinking it must be a valid identifier because of emit.

//.ts
type Foo<T> = { x : T };
export declare const foo : Foo<type>;

//.d.ts
export declare const foo : { x : type };

Since TS could arbitrarily expand a type alias, if we use an invalid identifier for the existential type, what happens during emit?

//.ts
type Foo<T> = { x : T };
//Assume we use `?` as the existential type
export declare const foo : Foo<?>;

//.d.ts
//Invalid identifier `?`
export declare const foo : { x : ? };

[fatcerberus]

@jack-williams Yeah, this is different from partial inference - this is a way to say “I need some kind of Foo<T> but it doesn’t matter what T is”. Foo<any> is the easiest way to accomplish that today (because we want to ignore variance for this purpose) but is very unsafe.

[jack-williams]

@AnyhowStep, your proposal has effectively been described here: https://github.com/microsoft/TypeScript/pull/30639#issuecomment-479283374

[AnyhowStep]

I tried reading that comment but got stuck at this part,

reading" permissive type and "writing" permissive type

I'm actually asking for a type that is reading and writing restrictive. So, you know the variable is of a certain type but you can't write to it (because it is never on write) and reading from it gives you unknown.

But maybe we describing the same thing with different words...

[jack-williams]

I think the difference between them is a one boolean negation of the initial variance.

[isiahmeadows]

Just ran into another issue where I need traditional existentials: typing pairs correctly. For instance, I have code that's roughly this:

type Receiver<T extends {}> = [keyof T, (value: T[keyof T]) => void]

I'm using this to represent pairs of [prop, callback] where callback is always called as callback(host[prop]) for some prop in host. So this type is actually completely incorrect. To properly type this, I need existential types that get propagated opaquely, because I want stuff like this to not error:

interface Event { a: string, b: number }

const receiver: Receiver<Event> = getReceiverSomehow()
const host: Event = getEventSomehow()

const [prop, callback] = receiver
callback(host[prop]) // currently errors

Edit: Wrong language tags for the code blocks.

[cwohlman]

Existential types would also be useful for arrays of generics.

Example:

type Job<T, R> = { isJob(param: unknown): param is T, run(param: T): R }
class JobsHandler {
  jobs: Job<unknown, unknown>[] = [] // This breaks because of the error listed below
  // jobs: Job<any, any>[] = [] // too loose
  // jobs: Job<T, R>[] = [] // with existential types
    runJob<T, R>(thing: T): R {
    const job = this.jobs.find(job => job.isJob(thing));
    if (!job) {
        throw new Error('No job')
    }
    return job.run(thing); // ts error here, even though thing is guaranteed to be T
  }
  addJob<T, R>(job: Job<T, R>) {
      this.jobs.push(job)
  }
}