Yet another Higher Kinded Types proposal in Typescript

[Wikiemol]

Suggestion

First, let me say that this proposal is different than #1213, although it achieves a similar goal. I am not proposing that type parameters be added to generic types, but rather, that classes be allowed to be instantiated like the objects that they are. I am proposing that Higher order types be added in the truest since, that is, there is a strict hierarchy of type orders, and that when one creates a class, one can assert the type of this class.

This proposal is meant to provide a somewhat easy mechanism for both implementing and understanding the expected behavior of this highly requested feature in the near future, which takes advantage of the typescript compiler's existing infrastructure, and also Javascript's prototype inheritance.

In addition, it covers the almost as old issue (if you include all of the tickets leading up to it) that abstract static methods be added to abstract classes and interfaces. #34516

We first note that currently, the following is valid typescript

interface Functor<Me extends Functor<Me, unknown>, Z> {
  fmap<Y>(f : (x : Z) => Y, w : Functor<Me, Z>) : Functor<Me, Y>;
}

class MyList<X> implements Functor<MyList<X>, X> {
  readonly xs: X[];
  constructor(xs : X[]) {
    this.xs = xs;
  }
  
  fmap<Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
    return new MyList(w.xs.map(f));
  }

}

We have effectively created a Functor interface, but on the wrong "level". We would like fmap to be static, but it is not. Moreover, in our Functor interface decleration, we cannot guaruntee that Z is a type paramater of Me.

The idea is to utilize this "almost" functor interface to make a real functor interface by only slightly changing the syntax.

We allow interfaces to be instantiated with some order. So for example,

interface^2 MyHigherOrderInterface {
     myHigherOrderMethod() : void;
}

This now represents a type of order 2. A normal class is automatically a type of order 1, and a value is a type of order 0. A class is asserted to be an inhabitant of MyHigherOrderClass in a similar way to the way all values are asserted to be an inhabitant of any type, with a :.

class MyLowerOrderClass : MyHigherOrderClass {
    static myHigherOrderMethod() { // Compiler error if this method isn't here and isn't static.
        console.log("Implemented");
    }
}

From an implementation standpoint, we are using almost (exactly in the case when there are no generics) the same code to type check that

class MyLowerOrderClass implements MyHigherOrderClass {
    myHigherOrderMethod() { 
        console.log("Implemented");
    }
}

does, but it is run on typeof MyLowerOrderClass instead of MyLowerOrderClass

Like extends, : can be used on generics, e.g.

interface^2 Functor<Me : Functor<Me, unknown>, Z> {
  fmap<Y, Input : Functor<Me, Z>, Result: Functor<Me, Y>>(f : (x : Z) => Y, w : Input) : Result;
}

Unlike extensions, specializing generics in a : heritage clause has restrictions. They must either be specialized with generics of the inhabitant class or the inhabitant class itself, and they must all be unique. With these restrictions we have a guarantee that generics will be specialized with the type parameters of its inhabitant class. For example

interface^2 Functor<Me : Functor<Me, unknown>, Z> {
  fmap<Y, Input : Functor<Me, Z>, Result: Functor<Me, Y>>(f : (x : Z) => Y, w : Input) : Result;
}

/**
 * By our rules for inhabitants of higher order types, 
 * we have no other choice but to have the first argument be MyList<X> 
 * and the second argument be X,
 * furthermore, Z must be specialized with MyList<W> thus fmap _must_ specialize in a form we expect
 * and anything that implements functor must indeed be a functor (modulo the functor laws).
 */
class MyList<X> : Functor<MyList<X>, X> {
  readonly xs: X[];
  constructor(xs : X[]) {
    this.xs = xs;
  }
  

/**
 * Here, generics of the inhabitant class are added to the generics of the method, since it is static.
 * This will be inferred from the input in this case and probably most cases, 
 * but in other cases it is a lot like having the input to the function X => MyList<X> be 'curried'
 */
  static fmap<X, Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
    return new MyList(w.xs.map(f));
  }

}

We could try to trick it,

/**
 * Here we are attempting to subvert the restriction that Y must be a paramater of X
 */
class MyTrick<W, X extends MyList<W>, Y> : Functor<X, Y> {...}  

But it won't work when we try to implement fmap, we note that the following is a compiler error in existing typescript

class MyTrick<X, Z extends MyList<X>, Y> implements Functor<Z, Y> {

  // Compiler error on fmap
  fmap<Y>(f: (x: Y) => Y,w: Functor<Z,Y>): Functor<Z,Y> {
    throw new Error("Method not implemented.");
  }
}

so it would be a compiler error with : instead of implements as well.

We can however use a version of this trick to implement multiple versions of a functor

/** 
 * The constraint is satisfied in current typescript, but thats okay, because map will 
 * get _statically_ specialized as a functor implementation for MyList, 
 * which is useful to have multiple functor implementations.
 */
class MyTrick<X, Z extends MyList<X>, Y> implements Functor<Z, X> {
  fmap<Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
  	throw new Error("Method not implemented.");
  }
}

Here is a Playground Link to these examples (which we can do because this is just existing behavior!)

Other miscellaneous things/concerns:

• Interfaces/classes can only implement/extend classes of the same order.

interface^2 Functor<Me : Functor<Me, unknown>, Z> {
  fmap<Y, Input : Functor<Me, Z>, Result: Functor<Me, Y>>(f : (x : Z) => Y, w : Input) : Result;
}

class MyList<X> implements Functor<MyList<X>, X> { // Compiler error, A Type of order 1 can only implement or extend another type of order 1
  readonly xs: X[];
  constructor(xs : X[]) {
    this.xs = xs;
  }
  

  fmap<Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
    return new MyList(w.xs.map(f));
  }

}

• The base types of Union/Intersection/Conditional/Product types must all be of the same order. I think there may be some fancy ways to lift this restriction in the future. For example, it may be fine to infer the order of a composite type like this to be the highest order among its leaf types, however, I am uneasy about the soundness of this.

• Ideally, typeof X would always have an order which is one level higher than the order of X. But I am not sure this would be compatible with how typescript currently works.

• My suggestion would be to first only allow higher order interfaces. But I could see something like static super being somewhat easily added to instantiate a higher order class, for example

abstract class^2 MyHigherOrderClass {
     abstract myHigherOrderMethod() : void;
     
     constructor(x : string) {
         console.log(x);
     }
}

class MyLowerOrderClass : MyHigherOrderClass {
    static super("hello world") // Compiler error if this isn't called
    static myHigherOrderMethod() { 
        console.log("Implemented");
    }
}

Now I will list the pros and cons of this approach:

Pros

• Adds two highly requested features at once
• Allows us to use existing typescript to understand the expected behavior of higher order types and their relationsionship with lower order types
  rather than having to reinvent the wheel.
• Seemingly pretty easy to implement . The key thing is that parsing ^n and adding the order to a node is very easy, parsing another heritage clause is very easy. Asserting that a typeof C implements the higher order class is essentially the same asserting that a class C implements an interface with some minor tweaks (adding class level generics to the static scope), just on typeof C instead of C itself.
• Easy to reason about its soundness from a type theoretical perspective. (However, I would like feedback from someone more familiar with all of the intricacies of the language)
• Makes the problem of constraints much less challenging, since we are just implementing a "higher order" version of stuff that already exists.
• Is actually more flexible than type classes in haskell in some ways, since you can decide which paramater should be 'the' paramater
  (in haskell, Something like Either<X, Y> could only be a functor on Y, not X, but here, you can provide both implementations), and higher orders we get for free

Cons

• Very Ugly. This is not as nice as the T<~> syntax proposed by others. However, I would argue that it is better to have something that is easy to implement to increase the likelihood of it being added to the language.
  Having a strong foundation makes it easier to add syntactic sugar later.
• I am not sure about typeof, it would need to be handled carefully. Ideally, typeof would always return a type of a higher order, but I am not certain this would break existing typescript code.
• Perhaps a bit tricky for the user to understand. The fact that Functor<Me extends Functor<Me, unknown>, X> in the example above is essentially equivalent to something like Functor me in a language like haskell is not immediately obvious. But again, hopefully syntactic sugar can help with this in the future.

🔍 Search Terms

Higher Order Types
Higher Kinded Types
Abstract static methods
static methods in interfaces

✅ Viability Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, new syntax sugar for JS, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

⭐ Suggestion

📃 Motivating Example

For me, the motivation for this was having static contracts for classes, inspired by this ticket #34516 (comment),
but then I realized that it could be used to implement Functors/Monads etc. See my comment #34516 (comment) for an example of a Parseable higher order type

💻 Use Cases

What do you want to use this for?

I would love to see actual type classes and higher order types like functors and monads be in a more mainstream language.
If pure state monads became mainstream instead of "state managers" for the front end, that would be sweet :).

Moreover, there are many situations where static contracts are useful even for those who do not like functional style programming, for example, comparable classes when overrides are possible becomes an issue the way typescript handles assignability, because you can't gauruntee that they are all using the same comparison function without asserting that they all are exactly T (i.e. no subclasses).

Having a static contract on a class and having methods that take the class itself based on the kind ensures that you are sorting by the same comparison method, but also allows you to have multiple comparable implementations and to mix subclasses with their superclasses.
I.e. instead of

interface Comparable<X extends Comparable<X>> {
    ...
}

sort<T extends Comparable<T>>(ts : T[]);

You can write

interface Comparable<X : Comparable<X>> {
    ...
}

// We can have multiple implementations of Comparable<T>, but they aren't tied to a particular subclass
// In the future it would be cool to infer the second argument if there is only one implementation like in Haskell, 
// or specify a default one.
sort<T : Comparable<T>>(ts : T[], comparisonFunction : Comparable<T>) 

As I mentioned above, another usecase is type parsing. Parsing with JSON.parse incorrectly introduces no errors, having a class be "parseable" in such a way that ensures an exception is thrown if it does not conform to the type would be very useful.

What shortcomings exist with current approaches?

The shortcomings of the existing attempts to provide a mechanism for static contracts are elucidated very clearly by Ryan Cavanaugh here #34516 (comment).
The shortcomings of the existing attempts to provide a mechanism for "higher kinded types" is that they do not actually introduce true "kinds" or "orders" into the type system, and are thus very difficult to reason about. In order for any higher kinded type system to be sound, there needs to be an explicit heirarchy. The existing approaches also involve entirely new concepts.

This proposal only adds one new concept, which is that of orders. The other concepts are existing ones, since in Javascript you are already instantiating a new object when you create a class.
We are just imposing the same type system as the one that already exists on these objects. This adheres to the design goal of

... [using] the behavior of JavaScript and the intentions of program authors as a guide for what makes the most sense in the language.

[Wikiemol]

Hey everyone, sorry! I accidentally posted this before it was ready, so there was a time when there was no description. But reopening now that I am done with the full proposal. (@MartinJohns You were right to thumbs down, but I implore you to reconsider now that I have updated with more info)

[Wikiemol]

I would also like to add that I have successfully implemented this with no generics on abstract classes without concrete methods. But I would like to start over now that I have a better idea of how the code base works, and also start with interfaces instead of abstract classes to avoid implementing the static super syntax initially.

I really wanted to put up a forked branch to show people with this proposal, and was just sort of using this as a way to get my thoughts down but then I accidentally posted the issue before I was done Dx.

[RyanCavanaugh]

I have some questions after reading this.

It seems like every instance of

interface^2 A { foo; }
class B : A { static foo; }

is isomorphic in behavior to a hypothetical #33892:

interface A { foo; }
class B static implements A { static foo; }

Some clarification on what else is going on would be good.

The : syntax in generic constraints isn't clear to me - generic constraints and class implements checks are in reality quite different and I don't understand how I'm supposed to reason about them. There's no equivalent "static side" to a type parameter the way there is for a class. In general any proposal that claims to provide HKT should stand alone without class-based examples; this proposal seems very class-specific in a way that makes me skeptical it's actually doing HKT rather than static implements.

This proposal would be much simpler to understand if it didn't jump straight into the deep end with functors and fmap. What's the simplest version of this one could show to a person who wasn't a Haskell expert? Why do ^2 interfaces need to exist at all, in fact -- shouldn't a class be free to :-implement a type of any order?

[Wikiemol]

@RyanCavanaugh These are good questions. Generic constraints work exactly the same way that they do in other languages which have higher order types. The idea is that we are guaranteeing that we can call static functions of a certain kind on the type T.

Let me use the example of parsing to make it a bit less "abstract nonsense". The goal of this example is to avoid silent bugs when using JSON.parse() on some incoming data whose structure may have changed.

For example, lets say I am writing an app to search car models, and I am using some external open source API which provides me with car models, but the contract of the API changes regularly. I would like to take some action when I notice that the type returned from the API varies from the data structure I am parsing it into.

Moreover, I have a lot of different objects which I am getting from this API, and I want it to be as painless as possible to add this validation, and I don't want to have to remember to use this, I want the compiler/linter to remind me. So I create a higher order class like this.

abstract class^2 Parseable<T : Parseable<T>> { 
    readonly dirnamePath : string; //Set to __dirname by the user
    readonly validate : (str : string) => void
    constructor(dirnamePath: string, t : typeof T) {
       this.dirnamePath = dirnamePath;
       this.validate = // lambda that gets auto generated JSON schema guaranteed unique combination of t.name and __dirname
    }
    
    public parse(str: string) : T {
           this.validate(str);
           return JSON.parse(str) as T;
    }
}

And a parsing function like this

function parse<T : Parseable<T>>(json: string, x : Parseable<T>) : T {
     return x.parse(json);
}

The key thing here is that the dirnamePath and validation function should not change instance to instance, it should always be the same.

Now, if my schema generator is set up, then I can write the following to easily have validation when parsing JSON to this class

class Car : Parseable<Car> {
        // Will get compiler error below if second argument is not Car, or if this constructor isn't here
        // Since Parseable can only be instantiated as a type (i.e. implemented by a class)
        // We know that if our schema generator is working properly, then either we will get an error 
        // at startup if the first argument is wrong or a compiler error if the second argument is wrong.
        static construct(__dirname, Car); 
        
}

Now when I want to parse the api response I can type

const car: Car = parse(json, Car)

And it will ensure that the validation and the type matches up. Moreover, if I ban JSON.parse with my linter then now I can effectively ensure that this validation will always take place on all incoming requests.

In languages like Haskell, we don't have to pass in the instance of Parseable, it just infers it if there is only one possible implementation of parse

// Haskell works like this, without having to pass in Car. It just knows to use parse from car since it only allows one static implementation
const car: Car = parse(json)

this is just the "typescript" way of accomplishing the same thing without inference, i.e. without having to add fancy inference logic to the type checker/transformer.

So the answer to your question about how to reason about : is essentially that x : Y means typeof x extends Y

function parse<typeof T extends Parseable<T>>(json: string, x : Parseable<T>) : T {
     return x.parse(json);
}

The above is not currently valid typescript syntax. It seems to me that, while these kinds of things are to some degree expressible, you often have to jump through hoops to enforce these kinds of constraints in typescript, and you never really feel totally secure that you got it right. Essentially you often have contracts you want enforced the same way on an entire class of objects, you don't want someone to be able to extend that class, and enforce the contract a different way. But then you also want to be able to use this "generically" in the same way that you use extends in generics. You can't use some "non override-able" keyword like final to accomplish this, because then you can't write the contract in the first place, since it wouldn't be overrideable.

To answer your question about the syntax only applying to classes, I would say that It applies to anything whose type has static fields. This is "classes" to some degree, but consider that everything in Javascript has fields.

If typeof T doesn't have the static fields your contract is requiring, then it simply won't conform to the constraint. If we wanted to add the ability to add higher order types to arbitrary types though, this could also be done with a simple extension of the syntax (this might be a bit harder to implement though).

type MyParseableType : Parseable<MyParseableType> = ..... {
... Implement static methods here
}

This would, in addition to creating a type on the compiler side, also be saying "I want to create an instance of Parseable corresponding to this type called MyParseableType", and the transpiler would just do that in exactly the same way you create a class with static methods.

Now for the last question, which is,

Why do ^2 interfaces need to exist at all, in fact -- shouldn't a class be free to :-implement a type of any order?

The original intention here is communication. Having used languages with higher order types, it is extremely natural to have a strict separation of kinds, and I think people coming from other languages with higher order kinds would expect it to be this way. I.e. Using precedent from other languages, typeclasses (e.g. functors) in haskell aren't types, they are something different, they can't be used in the same way that types can be used, and there is a strict hierarchy of them enforced in the compiler (although you can't go higher than order 2 as far as I know). More practically, Parseable, in the example above, simply does not make sense when being extended (or in general implemented) by the things which need to be parsed. Extending parseable would be a mistake, even though it might be many people's first instinct. static implements gives people the ability to do this, but nothing about the Parseable class above would communicate that they are supposed to do this instead of just implementing it, which simply would not be right. When you get to higher levels of abstraction than these simple examples, I could see this being very confusing.

An example of this is a comparable interface, and a sort function. You can easily express that you want the input to the sort function to be a list of comparables, but you can't easily express that you need them all to implement compare in the same way. Which a sort function needs to enforce. If you just have static implements without adding constraints to generics, you still do not have the ability to easily enforce this.

This I think, is just scratching the surface. I am not aware of languages that have successfully implemented higher kinded types without this strict seperation between types and higher kinded types, so its a bit hard to provide explicit examples, but there is a reason they are called higher kinded types, its because they are of a completely different sort, and have to be handled with care when mingling with the other types, otherwise logical paradoxes start to arise from a type theoretical perspective. Mathematically, when you have "types of types" you end up with a lot of logical paradoxes if you aren't very careful. The easiest way of being "very careful" is to enforce a strict hierarchy. There are other ways, but this is the one that has had the most success.

But I think this is at the heart of why people are somewhat uncomfortable with the existing ways of implementing static contracts, its that they aren't really static contracts, they are just contracts, and the user of the contract chooses to implement them statically, regardless of whether or not it was written to be this way, and you can't straightforwardly abstract over this, you can't straightforwardly express with the type system that "this function works for all types implementing this contract statically, but not necessarily types implementing this contract non statically".

[olee]

@Wikiemol actually your proposal is nothing else than another syntax for defining static properties on interfaces.

The following example you provided:

interface^2 MyHigherOrderInterface {
     myHigherOrderMethod() : void;
}

could in fact be represented by the following syntax quite more understandable:

interface MyHigherOrderInterface {
     static myHigherOrderMethod() : void;
}

But the issues with this type of interface have already been discussed in detail which is why imho it does not make sense to continue such exotic syntax and try to argue for static properties on interfaces instead (which I also thought at first would be nice but after reading #33892 (comment) I quickly noticed why this would not be a great idea).

Also, your proposal never even makes use of interface^3 which shows again why it would not make sense to go for such a syntax.

[Wikiemol]

@olee

This

interface MyHigherOrderInterface {
     static myHigherOrderMethod() : void;
}

and this

interface^2 MyHigherOrderInterface {
     myHigherOrderMethod() : void;
}

are not the same thing.

The idea is that an interface of order 2 still cannot have static fields. The fields are not static. Rather, it can only be implemented statically by types of order 1.
I did not give explicit examples of types of order 3, but the same idea applies. Interfaces of order 3 can only be implemented statically by types of order 2 etc.

This does not have the same downsides outlined in the linked comment. It can still be used "like" a type, instances of it can be created and passed into methods etc. It simply cannot be implemented or extended by types of order 1. It cannot be intersected with types of order 1, etc.

This is exactly like typeclass in Haskell and trait in Scala. To a lesser extent, instances of a higher order interface are very much like Class<X> in java. I.e. as interfaces, they specify the structure of a type like a higher kinded type, and their instances would likely be passed into methods for type coercion, for reflection, etc.

As instances, they have the power to turn generic types into runtime objects at the programmer's discretion (again very much like Class<X> in Java, but more flexible, since you can define Class itself).

[RyanCavanaugh]

FWIW, it's unlikely we would ever make forward progress here if the answer to all questions is "Do what Haskell / Scala do with it" with no elaboration. TS isn't those languages and we need answers that are concrete in our own type system. Without actual examples of code showing these things in action, it's impossible to meaningfully discuss what behavior is being proposed.

[Wikiemol]

@RyanCavanaugh Sorry, I tried to provide code examples above, implementing a parseable interface. Was that not what you were asking? That example wasn't really a haskell/scala thing at all, but something that I face as a working backend programmer and one of the usability reasons I wouldn't use typescript for my backend over , say Java. I need to validate incoming data in complicated and uniform ways, and in typescript it's really hard to do that uniformly and enforce this over an entire codebase (which is necessary for security reasons).

I think there may have been a confusion. The second comment was replying to Olee, not you. See my previous comment for a code example.

[Wikiemol]

@RyanCavanaugh Furthermore, I mention Haskell/Scala only to do what the guidelines say, which is

If relevant, precedent in other languages can be useful for establishing context and expected behavior

If this is a criticism, then I think this should be removed from the guidelines. I am really not a dogmatic person about this functional stuff, I just think functional programming languages are really the only ones doing both abstract static function implementations and higher kinds, so its really the only place I can go to set precedent .