Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Order dependence for equality #15

Open
bakkot opened this issue Jun 6, 2019 · 16 comments

Comments

Projects
None yet
7 participants
@bakkot
Copy link

commented Jun 6, 2019

From the readme:

if they have the same values stored and inserted in the same order, they will be considered strictly equal

This is surprising to me. Contrast python dicts or Purescript records.

It's also just a weird path-dependence in values: I would not expect it to matter if I construct something by doing (const { a: 0 }) with .b = 1 or (const { b: 1 }) with .a = 0

@rricard

This comment has been minimized.

Copy link
Owner

commented Jun 6, 2019

I got some other negative feedback on the order. Basically it's there to be "mindful" of the engines so we have something that remotely looks like the hidden class implementation optimization. But I think that last consideration could be brought up later... I'm gonna make an another pass on the proposal text at some point soon I'll ping that issue when I do!

@tolmasky

This comment has been minimized.

Copy link

commented Jun 6, 2019

Another interesting consideration is that I expect object with .key = object.key to be a no-op. However, if key ordering matters, then wouldn't object with .key push key's "order" to last, and thus (object with .key = object.key) !== object in many occasions?

@rricard

This comment has been minimized.

Copy link
Owner

commented Jun 6, 2019

If order matters then yes, and I agree it'll generate a lot of confusion. I was trying to be mindful of the engine before the user, it'll get updated!

@Jamesernator

This comment has been minimized.

Copy link

commented Jun 7, 2019

I think it would be better if instead for const objects enumeration order was in alphabetic order (or at least a consistent ordering). e.g. Object.keys(const { x: 10, y: 20 }) would be the same as Object.keys(const { y: 20, x: 10 }).

@ljharb

This comment has been minimized.

Copy link

commented Jun 7, 2019

Sets, Maps, and objects (roughly) all follow insertion order for enumeration - that seems the precedent to follow.

Insertion order isn’t likely to matter when comparing two Sets in the Set method proposal - so I’d assume that’s the precedent to follow for comparison too.

@Jamesernator

This comment has been minimized.

Copy link

commented Jun 7, 2019

If we did have Object.keys returning different sequences for those two objects but === still holding do we think this is a bad thing?

There's a related (but inverse) example in the language already where NaN !== NaN despite the fact NaN will act identically in all cases.

For this case it'd be the opposite way, two objects could be === but not behave identically in all situations. In which case would we need Object.is(const { x: 10, y: 20 }, const { x: 20, y: 10 }) to return false?

@Jamesernator

This comment has been minimized.

Copy link

commented Jun 7, 2019

To clarify we currently have these rules that hold true:

  • === implies you can use either the LHS or RHS and the behaviour will be identical
    • But !== doesn't imply the reverse because of NaN
  • Object.is implies two values are the same in all circumstances including NaN and you can pick either and get the same behaviour in all cases

But making const { x: 10, y: 20 } === const { x: 20, y: 10 } would break the first implication. This might be okay but my feeling is we'd never want to break the Object.is implication as well though.

@isiahmeadows

This comment has been minimized.

Copy link
Contributor

commented Jun 7, 2019

Order dependence can be removed if you're willing to allow some extra complexity that ranges from O(n) best case, O(n log n) to O(n^2) worst case (depending on implementation), and average case being somewhere in the middle. It's worth noting that Clojure, which uses immutable hash maps for nearly everything, also uses an order-independent equality algorithm for its maps and sets and does not have any significant performance issues from doing that. (I don't think it even offers a native order-dependent equality algorithm for its hash map data type.) They do not guarantee order, but I'm not sure how much of an effect that has on their algorithm.

@bakkot

This comment has been minimized.

Copy link
Author

commented Jun 7, 2019

@ljharb, you can't both have insertion order for iteration and make insertion order not matter for equality comparison. I'm with @Jamesernator - alphabetic order, possibly with nonnegative integer keys first, is the way to go.

(The set methods proposal isn't adding an "equals" method, so I'm not sure what you're referring to there, but in any case that would be a very different thing from two things being ===. The horrible edge case that is -0 aside, === implies that the left and right are the same value, which means they should not be distinguishable under any circumstances.)

@isiahmeadows

This comment has been minimized.

Copy link
Contributor

commented Jun 7, 2019

@bakkot You can't avoid being able to distinguish them as long as you can iterate them - even if the iteration order is undefined, you'll still be able to tell many === records apart by iteration order. And === doesn't always imply "same value":

  • NaN !== NaN, one of my biggest criticisms of IEEE-754.
  • An embedder might choose to expose a pointer to a JS object handle to JS code as a number, and if this handle happens to be a string, two pointers to a === string might still be !==. (It's a similar story with bigints.)

As for the stated semantics, it's intended to express non-coercing equality, not necessarily complete indistinguishability. Checking that is the goal for Object.is, not ===.

Edit: Filed #20 to ask about this.

@bakkot

This comment has been minimized.

Copy link
Author

commented Jun 7, 2019

@isiahmeadows

You can't avoid being able to distinguish them as long as you can iterate them - even if the iteration order is undefined

Only if the iteration order is undefined, which it should not be. If it is defined purely in terms of which keys are present, then iterating would not allow you to distinguish them.

NaN !== NaN, one of my biggest criticisms of IEEE-754.

I'm familiar with equality semantics in JS, but "=== implies same value" does not mean "!== implies not same value".

An embedder might choose to expose a pointer to a JS object handle to JS code as a number

Technically this is not forbidden by the spec, but the spec should not be built on the assumption that engines are going to do so.

Checking that is the goal for Object.is, not ===.

The fact that === uses different semantics from Object.is is one of the worst parts of the language. We are not going to add any new values for which the two are not equivalent.

@rricard

This comment has been minimized.

Copy link
Owner

commented Jun 8, 2019

I think the way this is going to end up is the following:

  • Order will not matter for comparison
  • Enumeration is still in insert order

This might change or e reviewed later on as we get closer to actual implementation (if that proposal ever goes that far)

@tolmasky

This comment has been minimized.

Copy link

commented Jun 8, 2019

I feel that many of the listed goals for value types will not actually be upheld if that is the case. A lot of the stated goals I feel fundamentally rely on the idea that:

Given a pure function f, and value types A and B, if A === B, then f(A) === f(B)

However, if A and B can ===, but return different results for Object.keys() (another way of saying that their iteration order is different), then no guarantees can bee made about f anymore. As such, many algorithms that want to rely on being able to "early return" when data is cheaply compared to be equal, will not actually be able to rely on === to do so. As a trivial example, simply imagine a React view that creates a list from the keys and values of an object. If this iteration is not guaranteed, then you can't simply say "I don't need to re-render if old-model === new-model".

@rricard

This comment has been minimized.

Copy link
Owner

commented Jun 8, 2019

That's a good point: I removed all ordering considerations for now from the proposal and we can keep discussing in that issue

@rricard

This comment has been minimized.

Copy link
Owner

commented Jun 11, 2019

We decided to have a stable key ordering: @rickbutton is working on it now!

@rickbutton

This comment has been minimized.

Copy link
Collaborator

commented Jun 11, 2019

speaking of! #25

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.