Discuss
  • ECMAScript Object equivalence classes proposal

ECMAScript Object equivalence classes proposal

# David Bruant (14 years ago)

This proposal is another attempt to address the DOM Element+EventTarget multiple inheritance issue in ECMAScript.

The main idea of my proposal is to introduce the concept of "object equivalence classes". First off, I'd like to say that I refer to a concept (en.wikipedia.org/wiki/Equivalence_class) which has nothing to do whatsoever with "classes" understood in a programming language inheritance context. The idea is to turn the == operator into an equivalence relation operator. The careful reader will instantly notice that actually, it already is (even if not explicitly stated in the spec). But the equivalence classes only contain one element each. So, the actual idea is to provide a mecanism to add new objects in an existing equivalence class. Each object would then have:

  • An identity (discriminable with ===)
  • An equivalence class (discriminable with ==) For the same reason Proxies shouldn't be able to redefine behavior of existing objects, the mechanism I'd like to introduce should not be able to change the equivalence class of an existing object. So, for the rest of this message, I'll expand my equivalence classes doing the following:

// Assuming o is an object already in the environment var o2 = Object.create(null, {}, o); // third argument is an object // The newly created object and o will be in the same equivalence class // If the third argument is omitted, the new object belongs to a new equivalence class.

We have:

  • o2 == o
  • o2 !== o
  • For all object a: o2 == a iff o == a (by transitivity by is in the definition of an equivalence class)

Implementing Element+EventTarget multiple inheritance Some properties we'd like to consider solving the problem. We'd like an object o such that:

  • o instanceof Element === true
  • o instanceof EventTarget === true
  • The built-in Element.prototype object is NOT in the built-in EventTarget prototype chain and vice versa

Imagining that "instanceof", was checking for object equivalence (==) (instead of same object reference, ===), then we could do the following (siblinghood is used as a metaphor for belonging in the same equivalence class):

var ElementProtoSibling = Object.create(null, {}, Element.prototype); var EventTargetProtoSibling = Object.create(ElementProtoSibling, {}, EventTarget.prototype); var e = Object.create(EventTargetProtoSibling, {});

We have:

  • e instanceof Element === true
  • e instanceof EventTarget === true These stand because instanceof would test equivalence instead of strict equality

If, instead of creating empty new objects, ElementProtoSibling and EventTargetProtoSibling were "own forwarding proxies" (concept explained here: esdiscuss/2011-March/013361) to respectively Element.prototype and EventTarget.prototype, then e would inherit from these objects the way we expect it to. (Of course, some notation would need to be introduce so that proxies can be added to an existing equivalence class. Proxy.create(handler, proto, eqClassObject)?)

Backward compatibility issues None for pure ECMAScript programs (since, as said, equivalence classes already exists but only contain one element by construction). There are going to be issues if current code using the DOM tests non-strict equality (==) after calls to Object.getPrototypeOf. But since DOM prototypes are the mess we're trying to get standardized in WebIDL, it may not be that big of a deal.

Implementation considerations This proposal affects Object initialisation and == testing. I don't see big issues in implementing equivalence classes in both time and space for these aspects.

Relationship to other parts of the spec If this proposal was considered, it might be worth checking all places in the spec where there is a strict comparison (same reference). Maybe that these tests could benefit from the definition of equivalence classes instead like instanceof do (as I propose).

# Brendan Eich (14 years ago)

On Apr 2, 2011, at 11:44 AM, David Bruant wrote:

Hi,

This proposal is another attempt to address the DOM Element+EventTarget multiple inheritance issue in ECMAScript.

That issue was resolved by putting EventTarget on the inheritance chain. See

dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#node

and

dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html 9.2 DOM Core

"Node now inherits from EventTarget."

In general, WebIDL is not spec'ing multiple "instanceof" inheritance any longer. It is explicitly linearizing to work best with JS.

The idea is to turn the == operator into an equivalence relation operator. The careful reader will instantly notice that actually, it already is (even if not explicitly stated in the spec).

No, == is not an e.r.

You must mean only in the cases where typeof a == typeof b, then a == b <=> a === b, and === is an e.r. But that does not mean == is an e.r.

For mismatching types, == is not transitive, so not an e.r. Also, for NaNs it is not reflexive (neither is ===).

// Assuming o is an object already in the environment var o2 = Object.create(null, {}, o); // third argument is an object // The newly created object and o will be in the same equivalence class // If the third argument is omitted, the new object belongs to a new equivalence class.

We have:

  • o2 == o
  • o2 !== o
  • For all object a: o2 == a iff o == a (by transitivity by is in the definition of an equivalence class)

What developers want, IMHO, is not Object.create and a specific object o to pass as a member of an existing e.c., in which to create a new object. That is tedious and painful, it requires a priori arrangements.

Rather, many developers wish == would work at least like so (same for <): [1, 2] == [1, 2]. Hence the tuples and records ideas in

brendaneich.com/2011/01/harmony-of-my-dreams

whereby #[1, 2] == #[1, 2] and #[1, 2] < #[1, 3].

More could be done, for sure. If Array users, say on a module by module basis, could "opt in" to better == and < semantics, that might be worth the trouble of adding such opt-in new operators.

But not just via Object.create.

And instanceof EventTarget is now a non-issue.

# Brendan Eich (14 years ago)

On Apr 2, 2011, at 12:16 PM, Brendan Eich wrote:

You must mean only in the cases where typeof a == typeof b, then a == b <=> a === b, and === is an e.r. But that does not mean == is an e.r.

Forgot typeof a == "object" above, to be precise.

For mismatching types, == is not transitive, so not an e.r. Also, for NaNs it is not reflexive (neither is ===).

The desire for < (partial order) as well as a true e.r. is strong, though, so thanks for raising this issue.

The big question remains: Is some modular opt-in to better == (and <) for objects worth the complexity?

# David Bruant (14 years ago)

Le 02/04/2011 21:30, Brendan Eich a écrit :

On Apr 2, 2011, at 12:16 PM, Brendan Eich wrote:

You must mean only in the cases where typeof a == typeof b, then a == b <=> a === b, and === is an e.r. But that does not mean == is an e.r. Forgot typeof a == "object" above, to be precise.

Indeed, I considered == to be an e.r. only in the contexts of objects. Sorry for the inaccuracy. Behavior when one side isn't an object would remain the same.

For mismatching types, == is not transitive, so not an e.r. Also, for NaNs it is not reflexive (neither is ===). The desire for < (partial order) as well as a true e.r. is strong, though, so thanks for raising this issue.

The big question remains: Is some modular opt-in to better == (and <) for objects worth the complexity? What developers want, IMHO, is not Object.create and a specific object o to pass as a member of an existing e.c., in which to create a new object. That is tedious and painful, it requires a priori arrangements.

Rather, many developers wish == would work at least like so (same for <): [1, 2] == [1, 2]. Hence the tuples and records ideas in

brendaneich.com/2011/01/harmony-of-my-dreams

whereby #[1, 2] == #[1, 2] and #[1, 2] < #[1, 3].

More could be done, for sure. If Array users, say on a module by module basis, could "opt in" to better == and < semantics, that might be worth the trouble of adding such opt-in new operators.

Are there other use cases than this one (#[1,2]...)? If not, then tuples are the right solution and it leaves the room for objects to define their own ==. I'm surprised by the idea that == could be defined on a per-value comparison basis on objects (Array as you give it as an example). It doesn't make the relation last throughout the program lifetime (which is what I was trying to do and requires a priori arrangements). I would expect an equivalence relation to last throughout the program. Like === does. With the defintion I tried to give to ==, I admit that it does not open the door for a < to be defined on objects.

# Brendan Eich (14 years ago)

On Apr 2, 2011, at 1:58 PM, David Bruant wrote:

I'm surprised by the idea that == could be defined on a per-value comparison basis on objects (Array as you give it as an example). It doesn't make the relation last throughout the program lifetime (which is what I was trying to do and requires a priori arrangements). I would expect an equivalence relation to last throughout the program. Like === does.

The use-cases are "operators", generally. Python supports unstratified operator meta-programming, so you can write __-delimited methods to change the meaning of programs. This is in the Harmony agenda but not for ES.next:

strawman:value_types, strawman:value_proxies Pythons API Virtual Values for Language Extension

It needs more baking. The value proxies idea is nearest but stratifed and constrained, aimed at efficient implementation of new numeric types. The ability to add operators to existing objects is not well-explored yet.

# Brendan Eich (14 years ago)

On Apr 2, 2011, at 1:58 PM, David Bruant wrote:

I'm surprised by the idea that == could be defined on a per-value comparison basis on objects (Array as you give it as an example). It doesn't make the relation last throughout the program lifetime (which is what I was trying to do and requires a priori arrangements). I would expect an equivalence relation to last throughout the program.

For a non-operator-syntax proposal to add lexically scoped methods as extensions to standard objects, using weakmaps under the hood (but observably in that the extended object could be frozen), see

strawman:scoped_object_extensions

(This page needs to be linked from strawman:strawman still.)

The advantage is that independent modules can cooperate without a prior arrangements or collisions.

# David Bruant (14 years ago)

Le 02/04/2011 23:40, Brendan Eich a écrit :

On Apr 2, 2011, at 1:58 PM, David Bruant wrote:

I'm surprised by the idea that == could be defined on a per-value comparison basis on objects (Array as you give it as an example). It doesn't make the relation last throughout the program lifetime (which is what I was trying to do and requires a priori arrangements). I would expect an equivalence relation to last throughout the program. Like === does.

The use-cases are "operators", generally. Python supports unstratified operator meta-programming, so you can write __-delimited methods to change the meaning of programs. This is in the Harmony agenda but not for ES.next:

strawman:value_types, strawman:value_proxies Pythons API docs.python.org/reference/datamodel.html#emulating-numeric-types Virtual Values for Language Extension www.soe.ucsc.edu/research/report?ID=1595

It needs more baking. The value proxies idea is nearest but stratifed and constrained, aimed at efficient implementation of new numeric types. The ability to add operators to existing objects is not well-explored yet. For a non-operator-syntax proposal to add lexically scoped methods as extensions to standard objects, using weakmaps under the hood (but observably in that the extended object could be frozen), see

strawman:scoped_object_extensions

(This page needs to be linked from strawman:strawman still.)

The advantage is that independent modules can cooperate without a prior arrangements or collisions.

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address. Equivalence classes through == and instanceof tweak were just one idea to address it.

It's not the first time that I try to address multiple inheritance and that no one really answers on this particular question, so I think I should ask the question directly instead of proposing ideas on the topic:

Is multiple inheritance a use case that TC39 intends to address in a generic manner?

If so, what are the current tracks? If not, I promise, I won't bother on the topic anymore :-)

,

# Brendan Eich (14 years ago)

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address.

Why? I mean, given the WebIDL and DOM changes.

Is multiple inheritance a use case that TC39 intends to address in a generic manner?

No.

# David Bruant (14 years ago)

Le 03/04/2011 02:11, Brendan Eich a écrit :

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address. Why? I mean, given the WebIDL and DOM changes.

Because people want it; Node+EventTarget wasn't the only use case. I'll take the number of article that pop up when typing "multiple inheritance javascript" on Google as a proof. Basically, people all do mixins which prevents them from using instanceof. They often acknowledge that it is the only limitation [1] [2] [3]. I have even seen people implementing an isInstanceOf function [2] [3]. My initial proposal was an attempt to address this issue.

Is multiple inheritance a use case that TC39 intends to address in a generic manner? No.

It clarifies things. Thank you.

David

[1] webreflection.blogspot.com/2009/06/wait-moment-javascript-does-support.html [2] www.polyglotinc.com/AJAXscratch/Class/InterfacesFromScratch.html [3] www.steinbit.org/words/programming/multiple-inheritance-in-javascript Taken from the 6 first Google search results for "multiple inheritance javascript"

# David Bruant (14 years ago)

Le 03/04/2011 10:12, David Bruant a écrit :

Le 03/04/2011 02:11, Brendan Eich a écrit :

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address. Why? I mean, given the WebIDL and DOM changes. Because people want it; Node+EventTarget wasn't the only use case. I'll take the number of article that pop up when typing "multiple inheritance javascript" on Google as a proof. Basically, people all do mixins which prevents them from using instanceof. They often acknowledge that it is the only limitation [1] [2] [3]. I have even seen people implementing an isInstanceOf function [2] [3].

With the ability to trap all prototype-climbing traps, proxies will be used to implement multiple inheritance [4]. Yet, instanceof won't be of any help to detect the multiple inheritance.

My initial proposal was an attempt to address this issue.

Is multiple inheritance a use case that TC39 intends to address in a generic manner? No. It clarifies things. Thank you.

David

[1] webreflection.blogspot.com/2009/06/wait-moment-javascript-does-support.html [2] www.polyglotinc.com/AJAXscratch/Class/InterfacesFromScratch.html [3] www.steinbit.org/words/programming/multiple-inheritance-in-javascript Taken from the 6 first Google search results for "multiple inheritance javascript" [4] journal.stuffwithstuff.com/2011/02/21/multiple-inheritance-in-javascript

# Brendan Eich (14 years ago)

On Apr 3, 2011, at 1:29 AM, David Bruant wrote:

Le 03/04/2011 10:12, David Bruant a écrit :

Le 03/04/2011 02:11, Brendan Eich a écrit :

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address. Why? I mean, given the WebIDL and DOM changes. Because people want it; Node+EventTarget wasn't the only use case. I'll take the number of article that pop up when typing "multiple inheritance javascript" on Google as a proof. Basically, people all do mixins which prevents them from using instanceof. They often acknowledge that it is the only limitation [1] [2] [3]. I have even seen people implementing an isInstanceOf function [2] [3]. With the ability to trap all prototype-climbing traps, proxies will be used to implement multiple inheritance [4]. Yet, instanceof won't be of any help to detect the multiple inheritance.

It's possible we want to trap instanceof too. We definitely discussed it, and prior to the WebIDL/DOM changes, Andreas Gal proposed we trap it precisely for those former DOM use-cases.

People use "swiss inheritance" (copying non-initial superclass or mixin properties) today in JS and instanceof is no help, so they need a method specific to their class/mixin system.

This does not argue for multiple inheritance in JS, though. Self has multiple prototypes (parents) and can do strictly more than JS, but no one is proposing adding multiple prototype chain links per object to JS.

So this seems more like a proxy issue than a general one, for now. Curious to hear from Tom if he has thoughts.

# Allen Wirfs-Brock (14 years ago)

On Apr 2, 2011, at 5:11 PM, Brendan Eich wrote:

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address.

Why? I mean, given the WebIDL and DOM changes.

Is multiple inheritance a use case that TC39 intends to address in a generic manner?

No.

Inheritance-based instanceof testing for the purpose of dynamic classification of objects is most appropriate in statically typed subclasing===subtyping languages. Multiple inheritance (at least for interfaces) is almost essential in such languages. That isn't is the case for dynamically typed subclassing!==subtyping languages. There is lots of experience with such languages that shows that dynamic classification via class or superclass inclusion testing is a poor practice. This is because it is possible (and often even necessary) to create behaviorally substitutable classes that don't participate in an inheritance relationship. By using such a test you are forcing downstream developers to fit into your implementation hierarchy and there may be strong reasons to do otherwise.

instanceof testing is very familiar to programmers coming from a Java-like language background. But like a number of other statically-typed language practices, instanceof testing is not a good idiom to use in JavaScript. If an "EventTarget" must have specific behavioral characteristic, then define those characteristics such that any object that needs to be an "EventTarget" can implement them, regardless of what is on its [[Prototype]] chain. If it is important to be able to dynamically test if an object can serve as an "EventTarget" then define a property that provides that characterization and make it part of the specified behavior of an "EventTarget". Just don't require that EventTarget.prototype is somewhere on the [[Prototype]] chain.

Practically speaking, large parts of JavaScript community are just starting to use the language to build rich "class" libraries. Many of them don't have experience with dynamically typed OO languages so they naturally follow the practices they are familiar with. We really need to guide them towards using the best practices that have been proven effective for dynamic OO languages rather than facilitating continued use of static OO idioms that are a poor fit to JavaScript.

# Tom Van Cutsem (14 years ago)

I largely agree with Allen's point of approaching classification in a dynamically typed language. I'm also a proponent of divorcing object classification entirely from the inheritance hierarchy. In our traits.js library, we decoupled traits from types, leaving the task of classifying trait-composed objects to the end-user.

One downside of the simple "object marking" scheme using public properties is that it doesn't work for use cases that require a "high-integrity" type test. WeakMaps could help here: a type T can be represented by a WeakMap M. To classify an object as type T, store it as a key in M. To test whether an object o is of type T, look it up in M. If write access to M is properly encapsulated, no object should be able to fool this type test, not even if it's a proxy.

Re. proxies & instanceof: no doubt proxies will give rise to a variety of multiple inheritance implementations, but I'm not convinced that the Proxy API should go too much out of its way to be able to emulate concepts that do not exist in the core language. The current strawman (< strawman:proxy_instanceof>) seems to

strike a good balance between flexibility and safety. BTW, that strawman would also make it possible to implement syntactically pleasant high-integrity type tests: a type T could be represented by both a WeakMap M and a function proxy F. To test whether an object o is of type T, one can then write the familiar |o instanceof F|, which triggers F's hasInstance trap, which can look up o in M.

Cheers, Tom

2011/4/3 Allen Wirfs-Brock <allen at wirfs-brock.com>

# David Bruant (14 years ago)

On Apr 2, 2011, at 5:11 PM, Brendan Eich wrote:

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address. Why? I mean, given the WebIDL and DOM changes.

Is multiple inheritance a use case that TC39 intends to address in a generic manner? No. Inheritance-based instanceof testing for the purpose of dynamic classification of objects is most appropriate in statically typed subclasing===subtyping languages. Multiple inheritance (at least for interfaces) is almost essential in such languages. That isn't is the case for dynamically typed subclassing!==subtyping languages. There is lots of experience with such languages that shows that dynamic classification via class or superclass inclusion testing is a poor practice. This is because it is possible (and often even necessary) to create behaviorally substitutable classes that don't participate in an inheritance relationship. By using such a test you are forcing downstream developers to fit into your implementation hierarchy and there may be strong reasons to do otherwise.

I am highly interested by all what is in this paragraph. Would you have articles talking about that you could refer me to?

instanceof testing is very familiar to programmers coming from a Java-like language background. But like a number of other statically-typed language practices, instanceof testing is not a good idiom to use in JavaScript. If an "EventTarget" must have specific behavioral characteristic, then define those characteristics such that any object that needs to be an "EventTarget" can implement them, regardless of what is on its [[Prototype]] chain. If it is important to be able to dynamically test if an object can serve as an "EventTarget" then define a property that provides that characterization and make it part of the specified behavior of an "EventTarget". Just don't require that EventTarget.prototype is somewhere on the [[Prototype]] chain.

So in a way, are you saying that the DOMCore/WebIDL decision is a bad one? If so, how would you solve the Element+EventTarget problem?

One interesting aspect I see in having all the things you inherit from in the [[Prototype]] chain is that you may be able to communicate with all other instances in a way. It may be a completely stupid idea, I don't know.

Practically speaking, large parts of JavaScript community are just starting to use the language to build rich "class" libraries. Many of them don't have experience with dynamically typed OO languages so they naturally follow the practices they are familiar with. We really need to guide them towards using the best practices that have been proven effective for dynamic OO languages rather than facilitating continued use of static OO idioms that are a poor fit to JavaScript.

I don't think I am familiar enough with dynamically typed OO languages to fully grasp how they work and best practices, but if other people are, maybe they should weigh in for another decision for the Element+EventTarget issue. It would be a great occasion to guide the JavaScript community toward using good practices, wouldn't it?

I also came from a C/Java background and learnt JS by myself. I'd be happy to learn best practices of dynamic OO languages. As for the first paragraph, if you have articles to share on the topic, I would be happy to read them.

# David Bruant (14 years ago)

I largely agree with Allen's point of approaching classification in a dynamically typed language. I'm also a proponent of divorcing object classification entirely from the inheritance hierarchy. In our traits.js library, we decoupled traits from types, leaving the task of classifying trait-composed objects to the end-user.

One downside of the simple "object marking" scheme using public properties is that it doesn't work for use cases that require a "high-integrity" type test. WeakMaps could help here: a type T can be represented by a WeakMap M. To classify an object as type T, store it as a key in M. To test whether an object o is of type T, look it up in M. If write access to M is properly encapsulated, no object should be able to fool this type test, not even if it's a proxy.

Re. proxies & instanceof: no doubt proxies will give rise to a variety of multiple inheritance implementations, but I'm not convinced that the Proxy API should go too much out of its way to be able to emulate concepts that do not exist in the core language. The current strawman (strawman:proxy_instanceof) seems to strike a good balance between flexibility and safety. BTW, that strawman would also make it possible to implement syntactically pleasant high-integrity type tests: a type T could be represented by both a WeakMap M and a function proxy F. To test whether an object o is of type T, one can then write the familiar |o instanceof F|, which triggers F's hasInstance trap, which can look up o in M.

I agree. That's how I would implement an hasInstance trap too. Not finding a "better" idea is what worries me about this strawman. Currently, instanceof and [[HasInstance]] actually check an "is instance" version in the sense that the object checks whether it has a given object in its prototype chain. What you're describing is an "has instance" in the sense that the constructors looks up to see if it "has an instance" of the object (WeakMap lookup in your example). What I'm worried about is the memory cost of such an implementation. The current [[HasInstance]] implementation has a constant memory cost. Keeping references has a linear memory cost in terms of instance number. My favorite real-world memory-intensive use case is the one-page Standard HTML (www.whatwg.org/specs/web-apps/current-work). Right now, it contains 125684 DOM Elements. If trying to implement EventTarget [[HasInstance]] internal method, it would require as many entries in the WeakMap. Maybe that ES implementors can provide data to say if it sounds like a realistic approach or not, but I'm pessimistic. Depending on the underlying WeakMap implementation, it could also have a noticeable impact on time performance as well. I agree on the flexibility and safety of the approach as you say, but I'm worried about scalability.

Unless we find "smarter" ways to implement the hasInstance trap, it might be a dead-end. If I try to find all the info we can get from an object to test something on it within the hasInstance trap, I can only list:

  • identity
  • own properties
  • [[Prototype]]
  • [[Extensible]] Storing identities is the WeakMap idea, own properties cannot be relied on to test inheritance, [[Prototype]] is plain old inheritance and it would be silly to provide [[Extensible]] two completely unrelated semantics. Since I don't really know what other information we could extract from an object to test against within the hasInstance trap, I don't really see how it could be used in practice. In a way, my original proposal was an attempt to add another item to the list which would be "equivalence class".
# Kam Kasravi (14 years ago)

On Apr 5, 2011, at 1:38 PM, David Bruant <david.bruant at labri.fr> wrote:

On Apr 2, 2011, at 5:11 PM, Brendan Eich wrote:

On Apr 2, 2011, at 4:19 PM, David Bruant wrote:

I have the feeling that none of these can help out with multiple inheritance. This is the problem I want to address. Why? I mean, given the WebIDL and DOM changes.

Is multiple inheritance a use case that TC39 intends to address in a generic manner? No. Inheritance-based instanceof testing for the purpose of dynamic classification of objects is most appropriate in statically typed subclasing===subtyping languages. Multiple inheritance (at least for interfaces) is almost essential in such languages. That isn't is the case for dynamically typed subclassing!==subtyping languages. There is lots of experience with such languages that shows that dynamic classification via class or superclass inclusion testing is a poor practice. This is because it is possible (and often even necessary) to create behaviorally substitutable classes that don't participate in an inheritance relationship. By using such a test you are forcing downstream developers to fit into your implementation hierarchy and there may be strong reasons to do otherwise. I am highly interested by all what is in this paragraph. Would you have articles talking about that you could refer me to?

Yes I am as well. Allen, were you thinking of adding a required attribute to the property MOP (this may be similar to traits)? The type signature would then be some encoding of all required properties.

# Allen Wirfs-Brock (14 years ago)

I''ve been a bit pinch for time the last couple days, but here are some preliminary responses to a few points below.

On Apr 5, 2011, at 1:38 PM, David Bruant wrote:

On Apr 2, 2011, at 5:11 PM, Brendan Eich wrote (except the this is really quoting Allen Wirfs-Brock):

Inheritance-based instanceof testing for the purpose of dynamic classification of objects is most appropriate in statically typed subclasing===subtyping languages. Multiple inheritance (at least for interfaces) is almost essential in such languages. That isn't is the case for dynamically typed subclassing!==subtyping languages. There is lots of experience with such languages that shows that dynamic classification via class or superclass inclusion testing is a poor practice. This is because it is possible (and often even necessary) to create behaviorally substitutable classes that don't participate in an inheritance relationship. By using such a test you are forcing downstream developers to fit into your implementation hierarchy and there may be strong reasons to do otherwise. I am highly interested by all what is in this paragraph. Would you have articles talking about that you could refer me to?

Much of the technology and best practices of object-oriented design were developed in the 1990's in the context of developing complex applications and frameworks using Smalltalk. a dynamically typed, single inheritance class based language. There is a large body of work on this topic although most of it is in the guise of Smalltalk. A good resource is stephane.ducasse.free.fr/FreeBooks.html which has digitized copies of a number of out of print Smalltalk related books. Pay particular attention to the style guides and patterns related books. You can probably skip the parts the address specific Smalltalk programming idioms (and pitfalls) but pay attention to the parts that are more directly generalizable to other dynamic languages. A highly regarded book that isn't on this site is Kent Beck's Smalltalk Best Practices Patterns. However, with some web searching you may be able to find prepub. drafts that are still floating around the web.

For books and articles about OO design methods that were highly influenced by Smalltalk best practices see the work of the other Wirfs-Brock: wirfs-brock.com/Resources.html For a book length treatment read: Object Design: Roles, Responsibilities, and Collaborations.

Lots of other stuff on the web if you search.

instanceof testing is very familiar to programmers coming from a Java-like language background. But like a number of other statically-typed language practices, instanceof testing is not a good idiom to use in JavaScript. If an "EventTarget" must have specific behavioral characteristic, then define those characteristics such that any object that needs to be an "EventTarget" can implement them, regardless of what is on its [[Prototype]] chain. If it is important to be able to dynamically test if an object can serve as an "EventTarget" then define a property that provides that characterization and make it part of the specified behavior of an "EventTarget". Just don't require that EventTarget.prototype is somewhere on the [[Prototype]] chain. So in a way, are you saying that the DOMCore/WebIDL decision is a bad one? If so, how would you solve the Element+EventTarget problem?

The EventTarget interface specifies 3 methods addEventListner, removeEventListener, and dispatchEvent. Any object that implements these three methods in conformance to the appropriate DOM spec. conforms to this interface. It doesn't matter if the implementation was inherited or directly implemented on the object. The method that seems to be most essential is dispatchEvent. If I need to test if an object is an EventTarget, I would do it by: if (obj.dispatchEvent) {/* this is an event listener */ ...

If you are afraid that somebody might coincidentally implement a method named "dispatchEvent" define a function: function isEventTarget(obj) {return (obj.isDispatchEvent && obj.addEventListner && obj.removeEventListner0 ? true: false)} //personally, I'd seldom, if ever, go to that extreme

One interesting aspect I see in having all the things you inherit from in the [[Prototype]] chain is that you may be able to communicate with all other instances in a way. It may be a completely stupid idea, I don't know.

Finding all instances is typically an expensive operations that requires runtime support. It is seldom needed. If you find that you do need it, it is probably a good idea to go back and revisit the design decisions that led to the necessity.

# David Bruant (14 years ago)

Le 06/04/2011 08:14, Allen Wirfs-Brock a écrit :

I''ve been a bit pinch for time the last couple days, but here are some preliminary responses to a few points below.

On Apr 5, 2011, at 1:38 PM, David Bruant wrote:

On Apr 2, 2011, at 5:11 PM, Brendan Eich wrote (except the this is really quoting Allen Wirfs-Brock):

Inheritance-based instanceof testing for the purpose of dynamic classification of objects is most appropriate in statically typed subclasing===subtyping languages. Multiple inheritance (at least for interfaces) is almost essential in such languages. That isn't is the case for dynamically typed subclassing!==subtyping languages. There is lots of experience with such languages that shows that dynamic classification via class or superclass inclusion testing is a poor practice. This is because it is possible (and often even necessary) to create behaviorally substitutable classes that don't participate in an inheritance relationship. By using such a test you are forcing downstream developers to fit into your implementation hierarchy and there may be strong reasons to do otherwise. I am highly interested by all what is in this paragraph. Would you have articles talking about that you could refer me to?

Much of the technology and best practices of object-oriented design were developed in the 1990's in the context of developing complex applications and frameworks using Smalltalk. a dynamically typed, single inheritance class based language. There is a large body of work on this topic although most of it is in the guise of Smalltalk. A good resource is stephane.ducasse.free.fr/FreeBooks.html which has digitized copies of a number of out of print Smalltalk related books. Pay particular attention to the style guides and patterns related books. You can probably skip the parts the address specific Smalltalk programming idioms (and pitfalls) but pay attention to the parts that are more directly generalizable to other dynamic languages. A highly regarded book that isn't on this site is Kent Beck's /Smalltalk Best Practices Patterns/. However, with some web searching you may be able to find prepub. drafts that are still floating around the web.

For books and articles about OO design methods that were highly influenced by Smalltalk best practices see the work of the other Wirfs-Brock: wirfs-brock.com/Resources.html, wirfs-brock.com/Resources.html For a book length treatment read: Object Design: Roles, Responsibilities, and Collaborations.

Lots of other stuff on the web if you search.

instanceof testing is very familiar to programmers coming from a Java-like language background. But like a number of other statically-typed language practices, instanceof testing is not a good idiom to use in JavaScript. If an "EventTarget" must have specific behavioral characteristic, then define those characteristics such that any object that needs to be an "EventTarget" can implement them, regardless of what is on its [[Prototype]] chain. If it is important to be able to dynamically test if an object can serve as an "EventTarget" then define a property that provides that characterization and make it part of the specified behavior of an "EventTarget". Just don't require that EventTarget.prototype is somewhere on the [[Prototype]] chain. So in a way, are you saying that the DOMCore/WebIDL decision is a bad one? If so, how would you solve the Element+EventTarget problem?

The EventTarget interface specifies 3 methods addEventListner, removeEventListener, and dispatchEvent. Any object that implements these three methods in conformance to the appropriate DOM spec. conforms to this interface. It doesn't matter if the implementation was inherited or directly implemented on the object. The method that seems to be most essential is dispatchEvent. If I need to test if an object is an EventTarget, I would do it by: if (obj.dispatchEvent) {/* this is an event listener */ ...

If you are afraid that somebody might coincidentally implement a method named "dispatchEvent" define a function: function isEventTarget(obj) {return (obj.isDispatchEvent && obj.addEventListner && obj.removeEventListner0 ? true: false)} //personally, I'd seldom, if ever, go to that extreme

One interesting aspect I see in having all the things you inherit from in the [[Prototype]] chain is that you may be able to communicate with all other instances in a way. It may be a completely stupid idea, I don't know.

Finding all instances is typically an expensive operations that requires runtime support. It is seldom needed. If you find that you do need it, it is probably a good idea to go back and revisit the design decisions that led to the necessity.

Sorry I was inaccurate in what I said. What I meant is here: gist.github.com/905301 c1 and c2 (and all objects created through getInstance) can "communicate" through their prototype: in this case, only with an access to c1 (from anywhere in the program), I can create a "c" property available in all other "instances". And it doesn't require to know any other instance (nor all instances consequently). If created with a constructor, it wouldn't even require access to the contructor itself. Calls to Object.getPrototypeOf are enough (one call in my example, but the technique could scale up as you can imagine). In this "prototype-based communication pattern", the prototype chain shape matters a lot. If all EventTarget instances have their methods as own, you can't climb the prototype chain to implement the mechanism I have just exposed.

Thanks for all the readings,

# Brendan Eich (14 years ago)

On Apr 3, 2011, at 11:12 AM, Allen Wirfs-Brock wrote:

On Apr 2, 2011, at 5:11 PM, Brendan Eich wrote:

Is multiple inheritance a use case that TC39 intends to address in a generic manner?

No.

Inheritance-based instanceof testing for the purpose of dynamic classification of objects is most appropriate in statically typed subclasing===subtyping languages. Multiple inheritance (at least for interfaces) is almost essential in such languages. That isn't is the case for dynamically typed subclassing!==subtyping languages. There is lots of experience with such languages that shows that dynamic classification via class or superclass inclusion testing is a poor practice.

Thanks for filling in after my terse "No."

The countervailing force here is the DOM being implemented in C++ (or C in the old days) in browsers. Such implementations use nominal subtyping and it leaked right through into JS.

This is not just an accident of history: implementors want fast is-a testing in the host programming language. Nevertheless, we are working on self-hosting the DOM, which should help dispel concerns about performance and scalability.

I don't see a lot of instanceof checks in modern JS, even DOM-based JS, so I believe the "nominal subtyping for performance" argument is overstated. However, there are currently C++-implemented internal-to-the-DOM-and-browser code paths that do such is-a tests (e.g., event dispatch and bubbling). These need to be self-hosted, and the whole system benchmarked.

We'll keep this list apprised of results.

# Brendan Eich (14 years ago)

On Apr 5, 2011, at 2:19 PM, David Bruant wrote:

What I'm worried about is the memory cost of such an implementation. The current [[HasInstance]] implementation has a constant memory cost. Keeping references has a linear memory cost in terms of instance number. My favorite real-world memory-intensive use case is the one-page Standard HTML (www.whatwg.org/specs/web-apps/current-work). Right now, it contains 125684 DOM Elements. If trying to implement EventTarget [[HasInstance]] internal method, it would require as many entries in the WeakMap.

First, there's no free lunch. Either the DOM objects need internal fields (vptrs in C++ sense, plus static shared vtbls) or brands or trademarks, which is per-object overhead. Or we need an entry in a weakmap for each object, which can be quite efficient (better if the map were a set, but still).

Second, although the details do matter, the asymptotic space complexity is the same, ignoring static or singleton costs which amortize to epsilon: k*n for constant k and n objects, or O(n).

The time complexity to test is-a would be O(1), but of course as David Bacon likes to point out, small constant factors can matter: a field load and compare beats a hashtable lookup. A C++ virtual call to QueryInterface or the like is slower than a well-implemented hashtable lookup.

Again, big-O does not distinguish even if some benchmarks run on different implementations could tell.

# P T Withington (14 years ago)

On 2011-04-07, at 13:27, Brendan Eich wrote:

On Apr 5, 2011, at 2:19 PM, David Bruant wrote:

What I'm worried about is the memory cost of such an implementation. The current [[HasInstance]] implementation has a constant memory cost. Keeping references has a linear memory cost in terms of instance number. My favorite real-world memory-intensive use case is the one-page Standard HTML (www.whatwg.org/specs/web-apps/current-work). Right now, it contains 125684 DOM Elements. If trying to implement EventTarget [[HasInstance]] internal method, it would require as many entries in the WeakMap.

First, there's no free lunch. Either the DOM objects need internal fields (vptrs in C++ sense, plus static shared vtbls) or brands or trademarks, which is per-object overhead. Or we need an entry in a weakmap for each object, which can be quite efficient (better if the map were a set, but still).

Second, although the details do matter, the asymptotic space complexity is the same, ignoring static or singleton costs which amortize to epsilon: k*n for constant k and n objects, or O(n).

The time complexity to test is-a would be O(1), but of course as David Bacon likes to point out, small constant factors can matter: a field load and compare beats a hashtable lookup. A C++ virtual call to QueryInterface or the like is slower than a well-implemented hashtable lookup.

Again, big-O does not distinguish even if some benchmarks run on different implementations could tell.

An oldie, but a goodie, perhaps relevant to this discussion:

www.cs.purdue.edu/homes/jv/pubs/oopsla97.pdf

# Allen Wirfs-Brock (14 years ago)

On Apr 8, 2011, at 11:40 AM, P T Withington wrote:

An oldie, but a goodie, perhaps relevant to this discussion:

www.cs.purdue.edu/homes/jv/pubs/oopsla97.pdf

Absolutely! We used this technique quite effectively in Instantiations' Jove whole program optimizer for Java (www.wirfs-brock.com/allen/things/jove). However, it uses tables that are precomputed based upon a static classification lattice and probably wouldn't be very effective in an environment like JavaScript with a highly dynamic set of set of potential classifications. However, it probably could be applied to something like DOM objects that had a fixed static "class" structure. Also, I believe that there is also related work on incrementally updating the necessary tables.

# David Bruant (14 years ago)

Le 07/04/2011 19:27, Brendan Eich a écrit :

On Apr 5, 2011, at 2:19 PM, David Bruant wrote:

What I'm worried about is the memory cost of such an implementation. The current [[HasInstance]] implementation has a constant memory cost. Keeping references has a linear memory cost in terms of instance number. My favorite real-world memory-intensive use case is the one-page Standard HTML (www.whatwg.org/specs/web-apps/current-work). Right now, it contains 125684 DOM Elements. If trying to implement EventTarget [[HasInstance]] internal method, it would require as many entries in the WeakMap.

First, there's no free lunch. Either the DOM objects need internal fields (vptrs in C++ sense, plus static shared vtbls) or brands or trademarks, which is per-object overhead. Or we need an entry in a weakmap for each object, which can be quite efficient (better if the map were a set, but still).

Second, although the details do matter, the asymptotic space complexity is the same, ignoring static or singleton costs which amortize to epsilon: k*n for constant k and n objects, or O(n).

I agree. I'd like to point out that WebIDL/DOMCore solution (EventTarget.prototype in Node.prototype chain) is a third solution for which there may be no further memory cost since the prototype chain has to be here anyway.

The EventTarget example was only here for illustration purposes. People may create several constructors (with an hasInstance+WeakMap inheritance) having several tens of thousands of instances each (implementors may have encounter people creating millions of instances sometimes?). Can ES engines handle that? If they can, then everything is fine. If they cannot, we may question the hasInstance trap. Usual inheritance has a constant memory cost since the prototype chain is shared. Tell me if I'm wrong, but the DOM inheritance has a limited memory footprint due to the fact that several constructors can share the same internal fields and it's in C++. It may be a different story when people will create constructors with one WeakMap each.

The time complexity to test is-a would be O(1), but of course as David Bacon likes to point out, small constant factors can matter: a field load and compare beats a hashtable lookup. A C++ virtual call to QueryInterface or the like is slower than a well-implemented hashtable lookup.

Again, big-O does not distinguish even if some benchmarks run on different implementations could tell.

I'll agree that as long as it's fast enough for real life uses, the actual big-O or multiplicative constants are of no interest. For instance, the current inheritance has a O(n) complexity (prototype chain traversing), but in real life, I've never seen a prototype chain with 10 elements.

# Brendan Eich (14 years ago)

On Apr 8, 2011, at 12:59 PM, David Bruant wrote:

I'll agree that as long as it's fast enough for real life uses, the actual big-O or multiplicative constants are of no interest. For instance, the current inheritance has a O(n) complexity (prototype chain traversing), but in real life, I've never seen a prototype chain with 10 elements.

See under sss.cs.purdue.edu/projects/dynjs,

sss.cs.purdue.edu/projects/dynjs/pldi275-richards.pdf

Figure 6 attached below shows some tall chains for gmail.

I'm told the Closure Compiler's optimizations tend to lengthen prototype chains, but I don't know more than that. Arv may ;-).

# Erik Arvidsson (14 years ago)

On Fri, Apr 8, 2011 at 13:24, Brendan Eich <brendan at mozilla.com> wrote:

On Apr 8, 2011, at 12:59 PM, David Bruant wrote:

I'll agree that as long as it's fast enough for real life uses, the actual big-O or multiplicative constants are of no interest. For instance, the current inheritance has a O(n) complexity (prototype chain traversing), but in real life, I've never seen a prototype chain with 10 elements.

See under sss.cs.purdue.edu/projects/dynjs,

sss.cs.purdue.edu/projects/dynjs/pldi275-richards.pdf

Figure 6 attached below shows some tall chains for gmail.

I'm told the Closure Compiler's optimizations tend to lengthen prototype chains, but I don't know more than that. Arv may ;-).

That is not true. The compiler doesn't do this as far as I know. I know it didn't do this when it was first released and things might have changed but I highly doubt that we would do such a thing.

I think the confusion comes from the inherit pattern in Closure Library [1]. I've seen people misunderstanding how that works, thinking that it adds another object in the prototype chain.

[1] www.google.com/codesearch/p?hl=en#9XMP1FG0vX8/trunk/goog/base.js&q=goog\.inherits&sa=N&cd=1&ct=rc&l=1141