the typeclass model offers superior extensibility

Keean Schupke (@keean)

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 Schupke (@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.

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.

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.

Simon Meskens (@SimonMeskens)

Simon Meskens (@SimonMeskens) Sean Vieira (@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

Marin Marinov (@gcnew)

Marin Marinov (@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.

Simon Meskens (@SimonMeskens)

Simon Meskens (@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.

Marin Marinov (@gcnew)

Marin Marinov (@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:

Aluan Haddad (@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 (@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 (@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 Simon Meskens (@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).

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?

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.

I feel like you need to write up some code samples. While I love talking type theory shop, without some real code samples, this discussion is too abstract for me. Could you create a toy sample?

Sean Vieira (@svieira)

Sean Vieira (@svieira) wrote:

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()

If the compiler could manage removing implementations after each use site need, then without multi-threading and asynchronous programming, we wouldn't have the problem you lament. But we need asynchronous programming, so we can't be sure the instance won't be referenced in multiple contexts simultaneously (unless we resorted to something like Rust lifetime's tracking which IMO is major pita). It seems to do this properly we need a separate implementations object dictionary for each use site (i.e. it's methods would consume an input for the instance and the instance's prototype chain wouldn't be used), then we could use the prototype chain of that object. Afaics, this would avoid your stated problem via locality and the compiler's knowledge about no conflicting names at the use site.

That's backporting emit, that doesn't count, you should show us what it does with an ES2015 target instead.

Simon Meskens (@SimonMeskens)

Simon Meskens (@SimonMeskens) wrote:

That's backporting emit, that doesn't count, you should show us what it does with an ES2015 target instead.

You moved the goalposts to some arbitrary case, which is aliasing error (point sampling a different point depending on which argument you want to make). Is there only one version of JavaScript in the wild? I will repeat:

shelby3 wrote:

I think the distinctions you are making are arbitrary (pigeonholed) in a holistic sense, and thus I don't see what is the utility of your distinctions.

And I will repeat some holistic justification might be helpful to some:

If anyone cares to clearly explain the utility and objectiveness of TypeScript's design philosophy, I think that might help readers and perhaps even myself.

In short, WTF is the point ???

Apologies for questioning what is the rationale for the orderly orderliness which is unsound and doesn't provide reliable contracts. Hopefully you can discern that I am trying to leave now as soon as you let me.

Edit: I suppose the goal is to have a trajectory that aims to look like how one would typically code in a future version of ECMAScript, except with typing hints. But for example, instead of checking the structural type to remain consistent, the community apparently decided to just trust a human to instruct (and thus potentially fool) the typing system as to what a type should be, breaking the internal consistency of the typing system while also not emitting code that checks the structural type; and checking the structural type in the absence of a nominal Symbol tag with instanceof is what I would expect to be a more idiomatic JavaScript design pattern. I don't know what to call this sort of typing system. Apparently many adhoc vectors. I won't pretend I can wrap my mind around all the corner cases of this typing system when all its features are mixed into code. Am I missing the point? What point?

async / await is indeed the only place where type-directed emit occurs. This is only considered OK because a) this is a huge value add, perhaps the highest emit value prop in the language and b) we can be sure that the async types required do not require loading other user-code files. Nothing else has met that bar and probably nothing else will.

This thread has gotten too long for anyone to read in a reasonable length of time, and the proposal under discussion has shifted substantially. It seems like we've elucidated some key constraints in TypeScript and if anyone wants to take this idea to a place where we could actually emit it, that'd be welcomed in a new issue. Closing this one (note that closing does not prevent new comments and people are welcomed to continue discussion here if needed in order to reach proper clarity for a new proposal).

Yeah, I'd gather up a proposal from this thread, but I don't see how type classes would work without polymorphic functions. Maybe we can come back to this if we ever get extension methods, maybe type classes are the way to go about extension methods. Not sure.

You may find interesting or useful this summary of variance issues w.r.t. to subclassing, typeclass objects, and my new union solution to the Expression Problem.

shelby3

shelby3 I'd like to clarify that the private fields proposal is
theoretically transpilable (with acceptable performance) to ES6, but it can
only be accomplished with WeakMaps, and thus can't go down to ES5.1 without
native weak bindings (like node-weak in Node or java.util.WeakHashMap in
Rhino or Nashorn).

On Sat, Sep 17, 2016, 22:12 shelby3 [email protected] wrote:

Simon Meskens (@SimonMeskens) https://github.com/SimonMeskens wrote:

you're showing the world

Hyperbole.

You're not holding a mirror up

I am also not blind in both eyes.

Any objects that share the same delegation object are of the same type

{ ... } undifferentiated from Object.prototype is uni-typing. As I wrote,
"sometimes..."

As for TypeScript not being a superset, how is it not?

I have a different definition of superset. I can't take any TypeScript
code and run it on JavaScript without compiling. It is a useless point that
TypeScript can compile JavaScript.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#10844 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AERrBMHpTM_QRM5eYy-ahJHQHQzTbiK0ks5qrJ4mgaJpZM4J52xn
.

without native weak bindings

Note that WeakMap can be fully polyfilled in ES5. I still think that the proposed private fields could be fully down emitted to ES5.

Kitson Kelly (@kitsonk)

Kitson Kelly (@kitsonk) I was mainly referring to the memory characteristics. (Using a
pair of backing arrays is technically spec conforming, although it's highly
memory inefficientc.) And the existing userland "polyfill" that is mostly
weak is not truly weak IIRC.

On Fri, Sep 23, 2016, 05:19 Kitson Kelly [email protected] wrote:

without native weak bindings

Note that WeakMap can be fully polyfilled in ES5. I still think that the
proposed private fields could be fully down emitted to ES5.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#10844 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AERrBBA-Qo8degAhkqoVADdw896wcV4dks5qs5mGgaJpZM4J52xn
.

And the existing userland "polyfill" that is mostly weak is not truly weak IIRC.

I don't believe the core-js polyfill is leaky (though there maybe a few edge cases... I know there were some changes to deal with frozen/sealed keys which would leak). Actually one of the changes of the spec, before it was final (removal of WeakMap.prototype.clear()) was specifically to make it possible to make it polyfillable with similar GC features to native.

Kitson Kelly (@kitsonk)

Kitson Kelly (@kitsonk) You're right. I was wrong. (I had to read the source.)

So apparently, the ES private fields proposal is transpilable down to ES5, complete with weak semantics, just using a WeakMap polyfill if necessary.

(I'm the one who pointed out in the proposal's repo before it was migrated to TC39 that its semantics could actually be transpiled to ES6 using WeakMaps, which is why I commented in the first place. The proposed spec change itself uses WeakMaps to specify it, although engines really shouldn't actually use those to implement it.)

The original idea of this thread, becomes the fast track hack to get typeclasses into TypeScript via my proposal to have ZenScript transpile to TypeScript. Thoughts?

shelby3

With much respect to all involved, this thread is far too long and contains far too many edits and digressions to be able to parse out a proposal for type classes. shelby3 or someone else who is the primary proponent of this, would you be so kind as to post a new issue with a concrete proposal distilled from this discussion?

Navigation Menu

Repository navigation

the typeclass model offers superior extensibility #10844

111 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

the typeclass model offers superior extensibility #10844

Description

Activity

shelby3 commented on Sep 12, 2016

SimonMeskens commented on Sep 12, 2016

svieira commented on Sep 13, 2016

gcnew commented on Sep 13, 2016

SimonMeskens commented on Sep 13, 2016

gcnew commented on Sep 13, 2016

SimonMeskens commented on Sep 13, 2016

shelby3 commented on Sep 13, 2016

shelby3 commented on Sep 14, 2016

spion commented on Sep 14, 2016

shelby3 commented on Sep 15, 2016

SimonMeskens commented on Sep 15, 2016

shelby3 commented on Sep 15, 2016

111 remaining items

SimonMeskens commented on Sep 18, 2016

shelby3 commented on Sep 18, 2016

RyanCavanaugh commented on Sep 19, 2016

RyanCavanaugh commented on Sep 19, 2016

SimonMeskens commented on Sep 19, 2016

shelby3 commented on Sep 23, 2016

dead-claudia commented on Sep 23, 2016

kitsonk commented on Sep 23, 2016

dead-claudia commented on Sep 23, 2016

kitsonk commented on Sep 23, 2016

dead-claudia commented on Sep 23, 2016

shelby3 commented on Sep 24, 2016

masaeedu commented on Oct 25, 2016

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions