the typeclass model offers superior extensibility

[shelby3]

Subclassing inheritance is an anti-pattern (see also this and this and this).

For those who aren't familiar with nominal typeclasses in for example Rust and Haskell, they conceptually (without getting into details and caveats yet) are a way of adding implementation to existing nominal types without modifying the source for those existing nominal types. For example, if you have an instance of existing nominal type A and your want to invoke a function that expects a nominal type B input, typeclasses conceptually enable you to declare the implementation of type B for type A and invoke the said function with the said instance of type A as input. The compiler is smart enough to automatically provide (the properties dictionary data structure or in ECMAScript the prototype chain) to the function the type B properties on the type A instance.

The has efficiency, SPOT, and DNRY advantages over the alternative of manually wrapping the instance of A in a new instance which has B type and delegate to the properties of A. Scala has implicit conversion to automate, but this doesn't eliminate all the boilerplate and solve the efficiency (^{_{and tangentially note Scala also can implement a typeclass design pattern employing implicits}}). This disadvantage of wrapping with new instances compared to typeclasses is especially significant when the instance is a collection (or even collection of collections) of instances (potentially heterogeneous with a union type), all of which have to be individually wrapped. Whereas, with typeclasses only the implementations for each necessary pair of (target, instance) types need to be declared, regardless of how many instances of the instance type(s) are impacted.

And afaics this typeclass model is what the prototype chain in EMCAScript provides.

When we construct a new instance, the A.prototype of the constructor function A is assigned to the instance's protoype, thus providing the initial implementation for the instance (of type A) of the properties of type A. If we want to add an implementation of constructor function B (i.e. of type B) for all instances of type A, then we can set A.prototype.prototype = B.prototype. Obviously we'd like to type check that A is already implemented for B, so we don't attempt to implement B for A thus setting B.prototype.prototype = A.prototype creating a cycle in the prototype chain.

That example was a bit stingy thus contrived, because actually we'd want a different implementation of type B for each type we apply it to. And afaics this is exactly what typeclasses model.

I am very sleepy at the moment. When I awake, I will go into more detail on this proposal and try to justify its importance, relevance to TypeScript's goals, and important problems it solves.

Note I had recently discovered in my discussions on the Rust forum in May what I believe to be a complete solution to Wadler's Expression Problem of extensibility (the O in SOLID), which requires typeclasses and first class unions (disjunctions) and intersections (conjunctions).

There are 500+ detailed comments of mine (and @keean) over there (~335 of which are private) I need to reread and condense into what I want to say in this issue proposal. And it was to some extent and unfinished analysis that I had put on the back burner. I have elevated this priority seeing that TypeScript has the first-class unions and intersections and seeing that upcoming 2.1 is supposed to look into the nominal typing issue for #202.

I have mentioned typeclasses in a few of my recent comments on TypeScript issues.

[shelby3]

@shelby3 wrote:

And do note that even on the untyped (uni-typed) ECMAScript, the prototype chain is form of heritage of objects since it is global to all constructed instances which didn't override the prototype as constructed (and even retroactively so which is the point I want to explore modeling with typeclasses for potentially amazing benefits in productivity and extensibility).

---

@shelby3 wrote:

@isiahmeadows wrote:

I'd recommend not trying to force nominal types into TypeScript in a way that requires frequent explicit casting in the meantime, though. If you focus on the data instead of the interface, you'd be surprised how far duck typing actually gets you.

I intend to convince[1] that subclassing is a non-extensible anti-pattern and typeclasses is the superior paradigm for nominal typing.

[1] See the THE COVARIANCE OF GENERICS section and the link back to a TypeScript issue.

[SimonMeskens]

I literally have no idea what you're talking about here, simple code sample? It sounds like you want to advocate changing an object's prototype. This is unfortunately discouraged in modern Javascript engines, as it disables a lot of optimizations. Hopefully this can be remedied in the future.

Do you want something like this?

class A <T> extends <T> {}

You can already type it, though it's somewhat clunky, like this:

class A {
    someProperty: string
}

class B {
    otherProperty: string
}

interface IC {
    newProperty: string
}

class C extends A {
    newProperty: string
}

let c: A = new C();

Object.setPrototypeOf(c, new B());

let newC: B & IC = <B & IC>c;

I agree that typescript could use a few new ways to correctly type mutating prototypes. I think my first code sample makes the most sense in that regard.

[svieira]

If I understand you correctly, you want to use compile-time prototype chain injection to provide the syntactical equivalent of Scala / Rust's typeclasses? In a project using the equivalent of scalaz / cats wouldn't that generate wildly deep prototype chains?

Also, wouldn't it make interop with JavaScript as painful syntactically as working with Scala is from Java? The compiler would have to re-write all of the names of all of the methods in the prototype chain to avoid collisions, which would mean JavaScript consumers would get to call things like someObject.$typeLookup(SomeNominalNéePrototype).someMethod() at best and at worst would have to do something like anotherUniverse.$x1z724_q3() // SomeNominalPrototype.someMethod as of yesterday.

[gcnew]

@SimonMeskens @svieira

In hindsight the idea of Type Clasess is a very easy/obvious one, but it was not when they were first conceived. The basic problem they are focused at is extending existing types with additional functionality. As they were targeted to solve problems in a functional language (Haskell) there were no classes or objects in the sense of Java, but only pure non-hierarchical types and values. None the less, people using this language wanted a principled way to extend a type with additional functionality. They came up with the idea of specifying an interface (called a Type Class) and implementing this very interface. The difference with other, more mainstream languages is that the instance (implementation) is not carried in an implicit class, but is actually a separate dictionary (to some extent parallels can be made with Extension methods in C#). Now, wherever something is declared to depend on that dictionary (e.g. a function that uses a type of specific Type Class), the compiler rewrites both the (function) definition and the call sites. The function definition is extended to accept the dictionary as a parameter while the call-sites are rewritten using type-directed emit to pass the appropriate dictionary.

For instance, lets say we want to be able to stringify arbitrary objects. We may come up with the following Type Class:

class Stringify a where
    stringify :: a -> String

Which in typescript terms corresponds to

type Stringify<a> = { stringify: (x: a) => string }

As an example we can implement this Type Class for string and number

instance Stringify Int where
    stringify = show

instance Stringify String where
    stringify = id

-- should be read as, a function accepting a value of generic type `a`
-- (which is also Stringify-able) that returns a string
appendX :: (Stringify a) => a -> String 
appendX x = (stringify x) ++ "X"

example = appendX (4::Int) ++ appendX "2"

const StringifyNumber: Stringify<number> = { stringify: x => String(x) }
const StringifyString: Stringify<string> = { stringify: x => x }

function appendX<a>(dict: Stringify<a>, x: a) {
    return dict.stringify(x) + "X";
}

const example = appendX(StringifyNumber, 4) + appendX(StringifyString, '2')

PS: see https://en.wikipedia.org/wiki/Type_class

[SimonMeskens]

@gcnew We are well aware of the concept of Type Classes, we are just confused as to why editing the prototype chain would in any way facilitate writing them in Javascript. Javascript, unlike Self seems to have advocated embedding over changing delegation from the very start and modern engines like V8 have only pushed this further by focusing optimizations on embedding. If the new setPrototypeOf gets significant use, I assume this will change.

I'm not against this suggestion, as I don't quite understand what's being suggested. The theory is not the problem, I understand how type classes are useful, especially for higher kinded polymorphism. I would just like to see some examples of real Javascript code that can't be typed today and how editing the prototype chain would make this possible.

[gcnew]

@SimonMeskens Well, in this case, I want to join you as well, because I'm also confused :). What's more, I don't see how Type Classes can be implemented in TS without breaking the stated Goals/Non-goals.

[SimonMeskens]

@gcnew I also think, with Javascript being more expressive than Haskell, type classes might not be the perfect fit, like they are for Haskell. It seems that certain concepts that can only be typed as higher kinds in Haskell can be flattened and typed more directly using prototypes; on the other hand, more complex behavior can be written in Javascript, that can not be typed in Haskell (I think, my Haskell knowledge is far from deep, even though I love the language). There's a few important gaps in Typescript at the moment that are less than perfect for doing things like currying (which enables a lot of these higher kinds to become useful) though.

The concept is intriguing for sure, I just don't get the suggestion made here 😄

[shelby3]

I will soon come back to this issue to elaborate. I am catching up on other discussion (and sleep). Thank you for the curiosity and discussion.

@shelby3 wrote:

@aluanhaddad wrote:

I would definitely be curious to see your formal type class proposal.
...
Walking the prototype chain and doing reference comparisons is far from reliable.

I think that as you have yourself stated, a different language, one targeting a type aware VM may well be the only way to achieve your goals.

To the extent that TypeScript can embrace unreliability of expected structural (interface and subclassed) types at runtime (even possibly with optional runtime nominal and structural checks that exception to a default or error case), I think perhaps the similar level of typing assurances can be attained with typeclasses. Typeclasses would only make sense nominally, as otherwise they are same as the structural interfaces we have already.

And I believe typeclasses are much more flexible for extension, compared to subclassing. I intend to attempt to explain that soon in the issue thread I created for that.

If we are going to add some nominal capabilities that are compatible with JavaScript's existing paradigms, such as instanceof, then typeclasses would give us the flexibility of extension we get with structural types. Note that instanceof may become much more reliable.

P.S. you are referring to the comment I made about Google's SoundScript and that if they succeed to accomplish runtime soundness, I believe it will essentially be a much different language.

---

@shelby3 wrote:

@spion wrote:

I was not referring to subclassing. That was only the mechanism via which I illustrated the problem with nominal types.

Afaics, the problem you are concerned with only applies to subclassing.

Typeclasses only solve the initial step where you have to convince the owner to implement your nominal interface; you no longer need to do that - you can write your own instance. However, you still have to convince the first author as well as existing library writers to adopt your typeclass i.e. write their code as follows:

function f(x:TheNominalInterface) { ... }

rather then write their functions against the original nominal type written by the first author:

function f(x: TheNominalOriginalPromise) { ... }

Anyone can implement the typeclass for any preexisting data type. There is no owner any more with typeclasses. The data type can still encapsulate (via modules and/or class) any facets it wishes to, so there is an owner in that respect, but anyone can implement a typeclass interface employing the public interface of any type. It is all about composability and we build new interfaces on top of existing ones. Afaics, the main difference from subclassing is that we are encouraged to invert the hierarchy of inheritance, such that we don't implement a fixed set of interfaces conflated together in one class, but rather implement an unbounded future number of interfaces separately for any class. We change the way we design and think about our interfaces.

And this allows us many benefits, including being able to add an interface to collection of instances and feed it to a function without having to manually rebuild the collection wrapping each instance in a new delegate wrapper shell instance (or in the case of a dynamic runtime, add properties manually to each instance...messing with the prototype chain is more analogous to typeclasses afaics).

[shelby3]

@shelby3 wrote:

@spion wrote:

I don't deny that typeclasses are better and more flexible than subclassing-based interfaces. But the problem doesn't just apply to subclassing.

Here is an instance of the problem in Haskell where despite having typeclasses, the community still haven't been able to fix the fragmentation that resulted from String, ByteString, ByteString.Lazy, Textand Text.Lazy. Libraries simply aren't adopting one common nominal interface: most still just use Text/String/ByteString directly, others implement their own personal and incompatible typeclass, and so on.

With structural types, you can implement the entire interface of an existing type and make all libraries that utilise the exiting type compatible with the new implementation. Without those libraries doing any changes whatsoever.

Per @SimonMeskens's suggestion, please continue this discussion in the issue thread I started for discussing typeclasses. I copied this reply over there. Thanks.

The problem you refer to (as well as Haskell's inability to do first-class unions) is because Haskell has global type inference. So this means that if we implement a data type more than one way on the same typeclass target, then the inference engine can't decide which one to apply. That problem is not with typeclasses, but with Haskell's choice of a globally coherent inference. Haskell's global inference has some benefits, but also has those drawbacks.

To enable multiple implementations (each for a specific typeclass) of the same data type on the same typeclass, we can support declaring typeclasses that extend other typeclasses. TypeScript's existing interfaces can serve this dual role I think. Then at the use site, we can provide a mechanism for selecting which implementation (i.e. sub-interface) is to be used. We can get more into the details in the future.

Suffice it to say that they are just as flexible as structural typing in terms of extensibility. The differences are they provide the ability to group structure nominal at any granularity we choose as an API designer. And to distinguish between equivalent structure that has a different name (nominal type).

[spion]

Then at the use site, we can provide a mechanism for selecting which implementation (i.e. sub-interface) is to be used.

Please do get into more details now. If the author of the Q promise library has written a function like so:

function doSomethingWithPromises(p:NominalTypeImplementedByQPromise) { ... }

How are you going to make this function work with a different promise library (say, Bluebird) without altering it, and without introducing a dependency between Bluebird and Q?

[shelby3]

So I had the thought that one facet which distinguishes typeclasses from subclasses is that the object of member implementations (aka properties) for the instance this is either orthogonal (dynamic at use site) or bound (static at declaration site) to the data respectively. With subclasses, the aforementioned implementations object dictionary is static for the life of the instance and with typeclasses that object can change depending on use site need.

For JavaScript we can think of subclassing's static interfaces as the constructor function's default prototype chain.

For JavaScript we can place such implementations of the prototype chain at will, adding or removing implementations for all existent instances of the constructor function. For a statically compiled language, the compiler can manage this prototype chain to make sure the required implementations are presented for the need, e.g. for an instance supplied as an argument to a function which requires a specific typeclass interface. If any implementations are ever removed then employing a global prototype chain for all instances is not thread re-entrant nor event queue (e.g. asynchronous programming) compatible. A compiler would prefer to have a separate dictionary pointer supplied on use site need orthogonal to the instance pointer, which could also be simulated with JavaScript but perhaps isn't idiomatic. But JavaScript's per-instance prototype chain can I think suffice assuming implementations are only added and never removed.

I don't know to what extent this pattern of altering the prototype of properties post-construction has been used in the JavaScript ecosystem?

---

Another related issue is that type parametrized collections/containers (e.g. List or Array) whose element type is a heterogeneous collection of subclasses have been handled historically by subsuming to the greatest lower bound common type (which I also mentioned upthread) and relying on virtual inheritance so that all types in the collection are subsumed to a supertype of common methods and calling those methods using dynamic dispatch to call the implementation for the method of the concrete subtype. This pattern is extensible in one axis of Wadler's Expression Problem because we can add new subtypes to our collection without recompiling the source code for the supertype (interface) and without reconstructing a copy of pre-existing instance of the collection and its existing contained instances. However, it is not extensible in the other axis of the Expression Problem because we can't add a new method to the base class (supertype inteface) without recompiling the source code and reconstructing instances.

By employing first-class disjunctions a.k.a. unions (and anonymous unions which are a feature of TypeScript, eliminates a lot of boiler plate) for the aforementioned container class's type parameter, the concrete types of the heterogeneous collection are not subsumed (not lost); and that heterogeneous union type is applicable to any typeclass interface need (e.g. a function argument) if there exists an implementation of that typeclass interface for every concrete type in that said union. In this way we can have extension in both axes of Wadler's Expression Problem without recompiling and reconstructing the existing instances and their sources. Solving Wadler's fundamental Expression Problem maximizes extensibility.

However, there remains a problem in that any pre-existing instance pointer for the said heterogeneous collection will be invalid if a new concrete type is added to the container's type parameter, because a reference to number | string is not compatible with a concrete instance of type of number | string | Array<number|string>. Afaics, this problem can solved in two possible ways in lieu of cloning (but not deeply) the container. First, the container can be designed so that when a new concrete type is added, it returns a new reference to the new container type and this new reference is isolated from any external pre-existing references to container. Meaning that somehow the container's code has an internal state which tracks which issued references refer to which subsets of contained concrete types. The other solution I envision is the the compiler is smart enough to do some form of lifetimes tracking such as in Rust, and will insure that the pre-existing external references are invalidated when the new concrete type is added.