search

racket / rhombus

Rhombus programming language
Other
352 stars 62 forks source link

What do we do about equality? #16

Closed jackfirth closed 4 months ago

jackfirth commented 5 years ago

Racket newcomers are immediately confronted with four equality operators:

I think we should simplify this in racket2 Rhombus. Here's a hypothetical straw proposal:

Is this feasible? Can we do better?

AlexKnauth commented 5 years ago

It might be worth considering a notion of equality that recurs through immutable data structures like equal? does, but uses reference equality on mutable data structures.

Same idea as egal? from Rackjure and Equal Rights for Functional Objects

jeapostrophe commented 5 years ago

There's a syntax part of this, a semantics part, and a library part.

Regarding semantics of eq?, Robby has long advocated the idea that programs should have the same functional correctness if all (eq? x y) is replaced with #f. The idea is that eq? is purely a kind of optimistic optimization where the slow path is required to be present.

spdegabrielle commented 5 years ago

regarding eq? would same? be better? the racket reference uses same to describe eq?;

Return #t if v1 and v2 refer to the same object, #f otherwise.

https://docs.racket-lang.org/reference/booleans.html?q=eq%3F#%28def._%28%28quote._~23~25kernel%29._eq~3f%29%29

jackfirth commented 5 years ago

regarding eq? would same? be better? the racket reference uses same to describe eq?;

Return #t if v1 and v2 refer to the same object, #f otherwise.

https://docs.racket-lang.org/reference/booleans.html?q=eq%3F#%28def._%28%28quote._~23~25kernel%29._eq~3f%29%29

The name we pick for eq? ought to be longer / more complex than equal?, to nudge people towards using equal? by default. So while I like using the word "same" for this, I think same-object? (or something similar) would be much clearer than same?.

spdegabrielle commented 5 years ago

+1 for same-object?. Much better than same?.

sorawee commented 5 years ago
  1. Why don't we make it consistent: use =? instead of =? We do have things like free-identifier=? already anyway (yes, I'm also up for <?, <=?, etc.).
  2. Is there a case where (equal? a b) and (= a b) don't behave the same when a and b are numbers? If not, why don't we also merge them into one. I.e., in general use =? (which is currently equal?). If you want a contracted version, just prefix it: number=?, string=?, etc.
  3. object-equal? or reference-equal? also works for eq?'s new name. No need to invent a new name (same).
AlexKnauth commented 5 years ago

To answer (2), yes, for (equal? 1 1.0) => #f vs (= 1 1.0) => #t. Exact-integers and floats-that-happen-to-be-integers are different racket values, but are equivalent numbers under =

LiberalArtist commented 5 years ago

My primary use for eq? is with symbols, especially as keys in eq?-based hash-tables. My impression is that there is a notable performance benefit.

dedbox commented 5 years ago

My primary use for eq? is with symbols, especially as keys in eq?-based hash-tables. My impression is that there is a notable performance benefit.

Here, here. eq? (and intern) are in the original Scheme paper, and I'm having a hard time understanding (Jay's account of) Robby's idea.

Is he saying eq? is misused so often that it is effectively useless, or that it is actually useless for some technical reason?

jeapostrophe commented 5 years ago

eq? interferes with optimizations because it exposes pointer identities, so you cannot, for example, create copies of immutable objects. Similarly, it interferes with providing safety because you can tell the difference between an object and its chaperone.

gus-massa commented 5 years ago

Something that I think is weird is that an immutable string can be equal? to a mutable string, but an immutable hash can't be equal? to a mutable hash. (I understand the reason at the C implementation, but I think that the difference should not leak to the racket level.)

jackfirth commented 5 years ago

Mutable objects are a strange case. If I have two vectors v and w, it's very important to know whether or not they refer to the same underlying storage: meaning whether or not vector-set! on v changes the result of vector-ref on w. This is different from knowing if v and w are eq?, because a vector may not be eq? to its own chaperone but they both refer to the same storage. Today, equal? on mutable objects just considers whether they have the same contents - not the same identity (which, due to chaperones, is not the same as just being eq?). I think this is very confusing, and that we should change equal? on mutable objects to only return true if they refer to the same mutable storage. This would communicate that the identity of a mutable object is an important part of its semantics.

LiberalArtist commented 5 years ago

As another point in the design space, Pyret has several notions of equality. In summary:

Name Operator Partial Predicate Total Predicate Similar To
Equal Now =~ equal-now equal-now3 equal? (Racket) == (Python, Ruby)
Always Equal == equal-always equal-always3 = (Ocaml)
Identical <=> identical identical3 eq? (Scheme) == (Ocaml) === (JavaScript) is (Python) == (Java)

IIUC, Racket lacks a general "Always Equal" for mutable values: a test to identify that mutations to one value will also mutate the other. Currently, eq? can only say "yes" or "idk": it is foiled by chaperones and impersonators. The default equal? for opaque structs does this, but sacrifices "Equal Now".

LiberalArtist commented 5 years ago

Re @jeapostrophe's comment on eq?: I agree that we should avoid exposing pointer identities (at least in the safe/high-level language) and we should allow the implementation to be aggressive as it wants at optimizing storage for immutable objects. I hope we can find a way to do that without degrading performance for things that are now idiomatic and correct uses of eq?, particularly with symbols.

I have a vague notion that the cost of equal? vs. eq? is especially notable in hash tables. With a statically-visible symbol, equal? can just be optimized to eq?, but AIUI it triggers more expensive double hashing in hash tables.

Another use-case is weak eq?-based hash tables to cache expensive computations that might be repeated: if the hash-table lookup becomes more expensive, that might negate the benefit of using the cache in the first place.

But maybe we will come up with an equality test that avoids the problems with eq? but still has good performance.

rocketnia commented 5 years ago

eq? interferes with optimizations because it exposes pointer identities, so you cannot, for example, create copies of immutable objects. Similarly, it interferes with providing safety because you can tell the difference between an object and its chaperone.

For this reason exactly, I think it'd be good to introduce a prop:has-hashable-object-identity property that new user-defined data structures don't have to implement (even if every value up to now has done so).

And, uh, I think this would eventually motivate migrating to yet another list representation, this time using cons cells that are not mutable and do not have object identity. But maybe one step at a time...

With that in mind, this is how I figure the equality functions can be renamed and recontextualized:

jackfirth commented 5 years ago

I think in nearly all cases where eq?-based hash tables are used, they're used with quoted symbol keys. In these cases, instead of exposing pointer equality we can just point users to a special purpose data structure that assumes symbol-like keys such as Rebellion's records. This also makes it easier to optimize further than what is possible with a generic hasheq data structure that assumes nothing about its keys.

I really think we should avoid introducing additional equality operators and concentrate on changing or removing the existing ones. I'd much rather change equal? to treat mutable objects with different identity as unequal than introduce a new equality operator with this behavior. If I wanted to compare two mutable vectors on their contents alone, the first approach I'd reach for would be (equal? (vector->immutable-vector vec1) (vector->immutable-vector vec2)) rather than read through the docs on the various equality operators until I'm sure I have the one that does what I want.

AlexKnauth commented 4 years ago

For an equality function that uses structural equality on immutable values, but reference equality on mutable values, is chaperone-of? the function that currently does that?

I would propose making equal? more like Rackjure's egal? or Pyret's equal-always, while renaming the existing structural-on-mutable equal? to equal-now?.

However if chaperone-of? already behaves like an "equal-always" predicate, then that might be as simple as renaming chaperone-of? to equal? while renaming the old equal? to equal-now?. Is this right?

If chaperone-of? behaves like an "equal-always", then the only difference I can think of between chaperone-of? and egal? is on streams, where egal? says streams are egal if they have egal elements (potentially diverging on infinite streams), where chaperone-of? would return false.

(Edit: okay it wouldn't quite be that simple, there would also need to be chaperone-of-based hash-tables, renamed to equal-based hash-tables along with it) (Edit 2: apparently chaperone-of? isn't symmetric, so I suppose the new "equal-always" version of equal? should be equivalent to (or (chaperone-of? a b) (chaperone-of? b a)), except it shouldn't have to traverse the data twice) (Edit 3: so just or-flipping on the outside won't be enough, the or-flip needs to happen on every nested place because it could need different directions in different parts of the data) (Edit 4: so just or-fliiping-and-traversing won't be enough, because if x2 and x3 are both chaperones of x1, they're unrelated by chaperone-of? in both directions)

sorawee commented 3 years ago

In the current Rhombus:

I think this is not ideal.

My preference is:

mflatt commented 3 years ago

One potential confusion with == as equal? is that 1 is not equal? to 1.0. (That's one reason why == isn't currently equal?.)

Maybe == could be numeric equality when both arguments are numbers and equal? otherwise.

jackfirth commented 3 years ago

What if instead of making == mean numeric equality on numbers, we just made numbers read as exact decimals by default? Then 1 == 1.0 would be true even if == means equal?.

sorawee commented 3 years ago

@jackfirth What should be the answer of

1 == exact_to_inexact(1)

?

jackfirth commented 3 years ago

I'd be fine with that being false, and telling people if they want to mix comparisons of exact and inexact values, they could use this:

is_numerically_equal(1, exact_to_inexact(1))

Exactness-insensitive numerical equality tests make up a very tiny fraction of all equality tests. I'm not too worried about them requiring some explicitness.

Metaxal commented 3 years ago

Hmm, I'm not too sure that's a good thing, as quite likely a large portion of the users (in particular students) will expect this result to be true. This can lead to serious silent bugs too.

I would be okay with 1 == exact_to_inexact(1) raising an exception instead.

jackfirth commented 3 years ago

I think of it as a type mismatch. Two things of different disjoint types can't be equal, similar to how some_number == some_string is allowed, but pointless. It's important that it's allowed so that things like x == some_gensym work correctly. But we could lean on static analysis to detect cases where equality tests are guaranteed to be false.

Metaxal commented 3 years ago

My current(*) personal preference:

Roughly based on the principle of least surprise: names should be intuitive enough and not do what you would not expect them to do (which is less stringent than "they should do what you expect them to do").

(*) Ask me next month for different answers.

jackfirth commented 3 years ago

=, ==, and equal? all having slightly different semantics is not a good state of affairs. I think there should only be one symbolic equality operator and it should have the same meaning as whatever is_equal means in Rhombus (which may or may not be the same as equal? in Racket.) Any other forms of equality should have descriptive names like is_numerically_equal or is_same_object and should not have symbolic operators associated with them. We want equality to have a single clear default meaning, with other notions of equality given names that say how they're different from the default meaning.

mflatt commented 3 years ago

What if instead of making == mean numeric equality on numbers, we just made numbers read as exact decimals by default?

That would definitely create surprises, given how much more expensive exact arithmetic is.

Exactness-insensitive numerical equality tests make up a very tiny fraction of all equality tests.

I'm not at all sure this is true, and I think this must depend on what kind of program you're writing.

While there are pitfalls to the convention that . means a floating point number and to conventions for implicit coercions between them, it's a pretty good compromise for the most part between performance and real arithmetic. I haven't seen the combination as a big source of bugs in our libraries. (It is a source of confusion for beginners in practically all languages, and this is one of those places where a different choice may be appropriate in a pedagogical language like BSL.)

More generally, I'm surprised at how often opinions in this thread dismiss the status quo, as if the only reason Racket has =, eq?, and equal? the way they are and in widespread use is because we've been too lazy to try anything else. Equality is tricky. Picking a small number of equality operators and allocating names to encourage the best ones — that sounds tractable and a good idea from our past experience. Trying to boil it down to just one equality operator seems at odds with experience across languages.

mflatt commented 3 years ago

My current(*) perference:

Meanwhile:

I still worry that the behavior of == as equal? on numbers will end surprising to some, but it's the least-bad effect I see in various compromises. Also, ending up with Racket's set of equality operators seems like a big benefit.

(*) Ask me again after you ask @Metaxal.

sorawee commented 3 years ago

In Discord (and above comments), @AlexKnauth has been advocating for == for egal? over equal?. egal? is probably not ergonomic unless most things are immutable (strings in particular), but it looks like we are heading in that direction anyway?

AlexKnauth commented 3 years ago

I've been calling it "equal always" to distinguish it from "equal now", and I was thinking of having 2 separate operators for them. So my current preference:

With == equal always being blessed as the preferred notion of equality, the default for list operations such as member and remove-duplicates, the one used to enforce chaperone compliance, and the one used for key comparison in the most convenient hash-tables / maps / dictionaries / sets.

Meanwhile:

AlexKnauth commented 3 years ago

More concretely, I would like == equal always to be defined such that:

a == b iff there exists a value v such that (chaperone-of? a v) and (chaperone-of? b v)

mflatt commented 3 years ago

Like many, I find the idea of egal?/equal_always appealing. But adding it to Racket (everything done for equal? in parallel for a new equal-always?) would be significant work. I'd go for it if if it seemed clearly worthwhile... but when I try to think of situations where my code would be better with egal? instead of equal?, I'm having trouble finding good examples.

The closest I think think of is the same others have noticed: problems with keys in an equal_always map getting mutated would not happen. Then again, if I correctly remember the cases where that happened to me or someone I was helping, the code would have been more complicated to achieve the goal with equal_always hashing, and so the programmer would have almost certainly just opted for an equal_now map, anyway.

Along similar lines, it seems like the interaction with match and classes with mutable fields is more subtle. If the fields of a Posn are mutable, does Posn(0, 0) match Posn(0, 0) on the grounds that the pattern Posn(0, 0) means any Posn whose fields match 0 and 0? Or does it fail to match because separate Posn(0, 0) and Posn(0, 0) are distinct? The current implementation would say the former, probably, but I'm not sure it's consistent. Another possibility is to disallow mutable-class constructors in patterns, but that seems unhelpfully strict.

I've re-read the discussion here and on Discourse, and I'm missing the anecdoates for where equal_always could have been better. Does anyone (perhaps @AlexKnauth, the main advocate here) have concrete examples you can point at where equal_always instead of equal_now would have solved/avoided problems in practice?

AlexKnauth commented 3 years ago

Match patterns aren't values... they don't have a "reference" identity to compare against, of course they can match mutable values structurally.

jackfirth commented 3 years ago

I'd rather just implement gen:equal+hash with equal-always semantics for Rhombus data types than try and introduce a parallel equal-always? procedure. I don't think it's worth having two operators for this.

rocketnia commented 3 years ago

I do think the matching of pure-constructor-only patterns against the results of pure-constructor-only expressions should coincide with the default equality check, so I think @mflatt makes a good point there.

Constructors of mutable objects, like Posn here, are generative rather than pure. However, I'd say their generativity can be thought of in terms of a pure functions that takes an unused object identity as an argument. It's the creation of an unused object identity that's impure. In some languages, writing out new Posn(0, 0) with a new keyword would make the creation and passing-in of that object identity explicit.

In that case, the corresponding pattern would also be written out as new Posn(0, 0). The notion of new in expression position is to create a fresh identity, so the corresponding notion in pattern position would be to consume one. In order to be sure this is a fresh identity being consumed, the pattern has to verify (somehow) that there are no aliases of this identity that are accessible to the program. This may sound kind of impractical short of using linear types or global weak maps to track aliasing, but if it's impractical, that means new Posn(0, 0) probably shouldn't be a supported pattern in the first place.

Serendipitously, aliasing also helps explain what's going on with mutable state here. If a mutable value has aliases and we try to match it in a pattern like Posn(0, 0) or new Posn(0, 0), there can be awkward situations where concurrent modification happens in between accessing the x and the y of the Posn, or in between accessing these two values in the pattern and using them later on in the branch. If we only allow pattern-matches on mutable values to proceed if they're not aliased, then these awkward cases are eliminated. And since we know at construction time that a value isn't aliased, requiring it not to be aliased at pattern-matching time makes the pattern more neatly analogous to the corresponding expression, too. So it seems like the right semantics for the pattern, even if it's impractical again.

If the pattern were something other than the expression, such as now Posn(0, 0), then the semantics of this pattern wouldn't have to coincide with any expression semantics, and they could be allowed to be something more practical. These semantics could make it explicit that the match succeeds for any given object identity (even non-fresh ones), that the object identity is not bound to anything by the match, and that concurrent modification might throw a wrench in the x and y submatches' up-to-date-ness and mutual consistency.

I don't think this now Posn(0, 0) would make much sense in expression position. The pattern form discards information, and it's unclear where the expression form should procure it from. Because of this, I don't think a design where Posn(0, 0) means now Posn(0, 0) would make sense either.

However, I think in a world where object identities and concurrent modification are always considered accidents, the act of discarding this information is moot because well-behaved programs always discard it anyway. In that case, the expression now Posn(0, 0) can make sense and can be implemented to procure the information from anywhere we like, such as by using the same implementation as new Posn(0, 0). Collapsing these into the common notation Posn(0, 0) seems justifiable in that world.

Anyhow, getting to the point:

mflatt commented 3 years ago

From @AlexKnauth:

Match patterns aren't values... they don't have a "reference" identity to compare against, of course they can match mutable values structurally.

Ok, I buy that. I'm probably too used to a world with quote, where quote patterns are explicitly defined in terms of equal?, and where there is the possibility of 3-D syntax (or historically worse), and that has muddied my thinking here. I also appreciate @rocketnia's point that we can have different kinds of patterns if something about them is meant to connect to values and equal?.

From @jackfirth:

I'd rather just implement gen:equal+hash with equal-always semantics for Rhombus data types than try and introduce a parallel equal-always? procedure. I don't think it's worth having two operators for this.

I don't yet buy this, because I'm not convinced that equal_now is rare or that equal_always is definitely useful. There also seems to be an idea here of sealing off Rhombus from Racket datatypes, which which is not obviously practical in terms of interoperability and performance; having separate equal_now and equal_always, in contrast, seems to have a good story on those fronts.

We should put this on the agenda of the bi-weekly Zoom meeting soon, maybe just after data structures.

mflatt commented 2 years ago

For now, I've updated the prototype to use == as equal?, === as eq?, .= as numeric =, := as set!, and = as a delimiter for use by things like fun. This isn't set in stone, obviously, but it seems like an improvement over the previous state.

AlexKnauth commented 2 years ago

I've made a branch and a draft PR to implement equal-always? for Racket: https://github.com/racket/racket/pull/4076

countvajhula commented 2 years ago

To provide another perspective here, some time ago I wrote a library providing an equality relation, =. It encodes my belief that a single equality relation is all we need in order to express any notion of equivalence. In the docs for the library I drew a distinction between the notion of "equality" and the notion of "identity," corresponding to the traditional distinction in Lisp (and in philosophy). But I think only the former is really needed.

The Main Idea

I'm not a professional mathematician, but I'll do my best to articulate what is essentially a mathematical point of view. The basis for it is the following idea, which intentionally has some handwaving, to be made precise later:

Any notion of equivalence can be expressed as a function. Objects that are mapped to the same target value by the function are equivalent under the notion of equivalence that the function represents.

For instance, two strings "apple" and "APPLE" are equivalent under the function string-upcase because they map to the same value.

One way to think about this is that the defining function f maps inputs values considered "equal" to a common representative, as "APPLE" was in the string-upcase example.

More precisely, For any equivalence relation "==" on a set E and a primitive notion of equivalence "=", there exists a set M and a function f : E → M such that x == y is equivalent to f(x) = f(y). Proof. By the results "I don't wanna prove it" and "I really feel like this is true," Q.E.D. Also, this closely corresponds to, but isn't exactly, a standard result on equivalence relations. If we feel a proper proof is necessary, we could tackle this later.

Primitive Equivalence and the Defining Function

Parsing the above carefully, we glean that the implementation motivated by this idea requires two things: (1) a primitive notion of equivalence "=", and (2) that the high-level equivalence relation "==" being defined should accept a function argument ("the defining function"). We could make this argument optional, so that if none is provided it is essentially the same as using the identity mapping, i.e. values, and then "==" and "=" are the same relation.

Re: (1) the primitive notion of equivalence, I think this could be any "sufficiently expressive" idea of equivalence. This notion of equivalence should, for instance, accept inputs of any type, and be able to distinguish between values of the same type (returning false if the inputs are of different types). For this primitive equality relation, we could potentially use one of the existing relations (such as equal?) or a combination of them, based on the following considerations:

What does "sufficiently expressive" mean? How should numbers be treated? How should immutable vs mutable values be handled?

Sufficiently expressive means that the primitive equivalence relation must be more discriminating than any notion of equivalence that we are likely to want in practice. So for instance, if it were to treat "abc" as equal to "ABC" then that's not good, because there are cases where we want to be case-sensitive. Another example: if it were to treat 1.0 as different from 1.00 -- that would be OK, since it is more discriminating than we typically need. Likewise, it should probably always treat immutable values as different from mutable values, if this distinction is one we are ever likely to care about in practice. Of course if all values were immutable, as Sorawee foreshadowed above, this would be a non-issue, but resolving it isn't a precondition to being able to define the equivalence relation here.

As an example, if we were to use equal? for the primitive relation "=", and considering the sign "==" to represent the new high-level equality relation, then in order to compare numbers the way the built-in numeric equality relation "=" does, in this scheme, we would need to use something like relation/type's ->float as the defining function, e.g. (== #:key ->float a b), to use Racket syntax. I don't know a lot about how floating point numbers are modeled in Racket and whether conversion to float is a reliable way to do the comparison or not, but the point is that we would need to map the input numbers to the "appropriate" representation that is able to treat 0.125 as the same as 1/8, if we happen to be interested in decimal equivalence.

If Primitive Equivalence Should be "More Discriminating," Shouldn't We Use eq?

For eq?, every value is equivalent to itself but nothing else at all. It would seem that this is "sufficiently expressive" and the "most discriminating," and therefore seemingly a good choice. Yet, it doesn't feel right. What defining function could we use to treat two distinct strings "hello" and "hello" as equal? It would need to somehow map both of these values to the same object in memory, while also implementing the criterion we wish to use to assert the equivalence of these two values. I think the issue is that while eq? is the most discriminating, it is this way by virtue of arbitrary criteria rather than by actual analysis of the objects being compared. That is, objects are the same or distinct based on where they are, not what they are. So it may be that the real criterion is not just "most discriminating" but more specifically, "most discriminating based on inherent properties of the objects," and we cannot use eq? here.

How to handle identity vs equality?

In many cases in practice, we prefer to use eq? rather than equal?. For instance, when comparing structs, the latter does a recursive comparison of fields (as I understand it), and likewise for lists, making it expensive. While the former is a constant time check. We may still like to have a dedicated notion of "identity" for such cases. For this, we could simply use (== #:key eq-hash-code a b) i.e. use a function that maps an object to its memory address. So same? proposed above becomes a thin facade on == and replaces eq? while retaining its performance profile.

Likewise, the equal-always? proposed above is the default behavior of =, but we could get less discriminating behavior with another thin facade, equal-now?, via the defining function, ->immutable. For objects that we know are mutable, it falls to us as developers to use same? rather than ==.

Equality-based interfaces and structures

There are many implicit equality-based interfaces (like remove, member, ...) and structures (like hashes). For these, at the moment in Racket there are parallel sets of interfaces and structures, each employing a particular notion of equality (e.g. eq? or equal? or eqv? etc.). With the new defining-function-based equality relation, we would only need to have a single set of interfaces and a single set of structures that implicitly employ ==. All of these interfaces and structures must also accept an optional function argument, just as == itself does, to be able to specialize the definition of equality as we have seen.

User-supplied equality functions

Racket interfaces often accept an optional equal-proc argument (e.g. assoc), allowing the user to supply a function to use in place of equal? or eq? etc. The claim with == is that all notions of equivalence can be modeled by it. It would be good to try and find counter-examples to this claim: cases where we need to supply a (binary) equality function, where a (unary) defining function is inadequate.

Counterexamples

One possible counter-example is the relation of being "approximately equal." We could define this as "a = b means a and b are within 0.5 of each other." We cannot express this as a defining function with ==, since the notion of equality here relies on a difference between two values, and therefore is a function of both values and cannot be determined by projection of a single value alone. It would seem that == is done for! But on closer inspection, we see that 4.7 ~= 5.0 and 5.0 ~= 5.3. Yet, 4.7 ~= 5.3 is not true. Mathematically, notions of equivalence must be transitive, meaning a = b and b = c implies a = c. The relation of "approximate equality" violates this, so we could say, no bueno, and in that case, == is OK. Do we want to consider this a legitimate definition of equivalence, even though mathematically it isn't valid? Philosophically (rather than mathematically), I am not unsympathetic to this view, for certain reasons that we needn't get into, but personally, I think the mathematical criteria should prevail here, and == is still good, since otherwise, for instance, it would make things weird with hashtables where hashing would be ambiguous! E.g. if our hashtable represents buckets of 100m sprint times with a tolerance of 0.5s, then 5.0 could either be hashed under 4.7 or 5.3 (or both).

Caveat Emptor

In the tradition of Knuth, I'll qualify all this by saying, "beware of bugs in the above -- I've only proved it true, not tried it." If we can come up with other counterexamples for consideration, that would certainly help reveal whether == is viable.

By the way, the = relation from relation/equivalence is roughly a proof of concept for some of the behavior above, but it differs from == in some ways -- e.g. handling of numbers, and I'm not sure if the implementation of the hash-code is sound for the purposes of using it in a hash/dictionary. The above discussion should be treated as taking precedence over any of the decisions in relation/equivalence. But you're welcome to try it to get a sense of how == might work.

AlexKnauth commented 2 years ago

The kind of "key" function you can imagine that can pick a single representative for its equivalence class, used to map to a more primitive operation eq?, sounds like what interning does, with datum-intern-literal.

However, there are good reasons why something like (== x y) wouldn't implemented as just (eq? (datum-intern-literal x) (datum-intern-literal y)). For one thing, just checking equality between two objects shouldn't require finding-or-allocating a 3rd object to be the "representative" for their equivalence class. The equality operation also shouldn't require using a table to look up that representative if it exists already, since that table itself would need the equality operation anyway.

I've been thinking about this because it would also a bad idea to implement my (equal-always? x y) as just (chaperone-of? x (remove-all-chaperones y)), for similar reasons. Rather than trying that, in my implementation referenced above I'm mostly using the existing implementation of chaperone-of? and equal?, just adding a new mode in the same traversals.

countvajhula commented 2 years ago

The kind of "key" function you can imagine that can pick a single representative for its equivalence class, used to map to a more primitive operation eq?, sounds like what interning does, with datum-intern-literal.

That could be useful, except I don't think eq? is the primitive equivalence relation we need. It would rather be more like equal? except that it treats mutable/immutable more strictly -- similar to your equal-always?, I think (but I am not too concerned with the details of this aside from it being more discriminating than what we need in practice). The defining function also does not mean a specific function. It's just that given any notion of equivalence that we seek to model, there always exists some function (or several) that we could use to express it.

For one thing, just checking equality between two objects shouldn't require finding-or-allocating a 3rd object to be the "representative" for their equivalence class.

For performance reasons, or something else?

The equality operation also shouldn't require using a table to look up that representative if it exists already, since that table itself would need the equality operation anyway.

I don't think I suggested a lookup table for this purpose. Did I implicitly assume one? I believe the proposed primitive equivalence operator = addresses possible circularity here.

LiberalArtist commented 2 years ago

Re https://github.com/racket/rhombus-brainstorming/issues/16#issuecomment-979582271:

What if instead of making == mean numeric equality on numbers, we just made numbers read as exact decimals by default? Then 1 == 1.0 would be true even if == means equal?.

It's a tangent, but this comment prompted me to think that, regardless of equality, an advantage of having numbers read as exact by default is that a macro—perhaps even #%datum—could transform them to inexact numbers with no loss of precision, whereas, if read produces inexact numbers, the reverse transformation wouldn't work.

Personally, most of the time, exact arithmetic is worth the price for me: either what I'm doing isn't very numerically intensive, or it's important enough that I want to avoid floating-point headaches. I also think the numeric tower is a fairly distinctive inheritance from the Scheme tradition worth spreading to the world. On the other hand, as Matthew said, having good floating-point performance when you do want it is also a feature, and being surprisingly slow could be a poor first impression.

AlexKnauth commented 2 years ago

The places eq? is seemingly encouraged in educational material for beginners, such as a very memorable page in Realm of Racket, you know the one where they shave the guy and the other argument is also shaved... would be better off replaced by equal-always? in their new versions in Rhombus, at the very least.

My preference would be that equal-always? semantics would be the go-to equality operation in the new language, and another function with equal-now? semantics would be off to the side in another operator such as =~... but,

Even if people don't like having my preference:

I wonder if those other people would like something like:

instead?

To be clear I'd rather have == as equal-always... but a version where equal-always at least exists under some name would be better than being left with just eq

mflatt commented 2 years ago

A reminder: So far, there have been 0 concrete examples reported where equal_always instead of equal_now would have solved/avoided problems in practice. We could use some examples.

samth commented 2 years ago

For those interested, Henry Baker's original paper proposing egal? (the same as equal_always) is here: https://dl.acm.org/doi/10.1145/165593.165596.

However, it doesn't describe any concrete examples where equal_now causes problems; the arguments made are primarily that it's bad to have a non-referentially-transparent equality predicate, and that it is bad to have a bunch of them that programmers have to choose between. (There's also discussion of why providing traditional eq? semantics on immutable data is problematic especially in the presence of distributed computing, but I don't think that has a clear bearing on this issue.)

AlexKnauth commented 2 years ago

I think you might be misunderstanding my purpose. I don't think there are that many problems in existing Racket programs using equal? that would be fixed by switching to equal-always?. (Mostly because mutation is rare enough in Racket that it doesn't matter much, and people who do use mutation in Racket usually know enough to know when to use eq? instead of equal? for mutable data.)

However, there are more problems in existing Racket programs using eq? that would be fixed by switching those to equal-always?. Both from beginners who might think eq? is just a convenient shorthand, and from more knowledgeable people who use eq? because of its properties wrt mutable data, but get burned by chaperones and the like not counting as eq.

An equal-always? would also be a useful middle-ground that would suffice to replace most uses of both eq? and equal?-used-in-functional-programs, making it a good choice to condense the many various equality operators in Racket currently, into just one or two to simplify it.

mflatt commented 2 years ago

However, there are more problems in existing Racket programs using eq? that would be fixed by switching those to equal-always?.

I had indeed not understood that motivation from the preceding discussion. Thanks for the clarification. So, we're looking for examples where eq? has gone wrong and would be fixed by equal_always but not equal_now?

I can remember a places where eq? was used to recognize procedures and it interactedly badly with chaperones, as you say. It was the notify-on-change method of style-list%. But using equal? there was a fine start at a correction, because it wasn't really trying to check the mutability of a procedure. Also, there was more to the change. (See the documentation for that method.)

The problem that people some reach for eq? because it's shorter than equal? seems less relevant. As we pick new operators, we're aiming for the reverse, at a minimum.

But place where eq? was used to recognize mutable things and interacted badly with chaperones sounds relevant, and I'm curious to hear more.

countvajhula commented 2 years ago

Just a friendly check-in -- has there been any consideration of my proposal above? Please let me know if I can provide additional examples or clarification to illustrate it further.

In my humble opinion, it is the simplest possible equality interface a language could provide as it is essentially just one equality relation (==, which reduces to = in the naive case). It is intuitive for users due to its simplicity, and also minimizes the maintenance work required for core developers, since it provides a simple standard for all equality-based interfaces in the entire language ecosystem - that is, they expose an optional key argument to be passed through to ==. Contrast that with the present state of affairs, where there is sometimes a key argument expected, sometimes a binary comparison predicate, sometimes it isn't exposed at all for customization, and sometimes there are parallel sets of interfaces. The "key" argument can be used in all cases, and even for order relations such as < and > (relation/order is a proof of concept here, if you'd like to try it).

I'd like to highlight that this 2-level scheme is more along the lines of the original issue description re: exposing a smaller interface. It is agnostic wrt the specific choice of =, modulo the considerations I mentioned, and for instance, something resembling equal-always? would be fine here - just ideally one that is efficient for all types of comparisons, including numeric comparisons.

mflatt commented 2 years ago

From @countvajhula:

Just a friendly check-in -- has there been any consideration of my proposal above?

I haven't seen any more discussion than above, so I'll offer some thoughts that might prod further discussion.

The good part that I see is that parameterizing over one function to find a representative value is conceptually cleaner than parametering over separate equality functions, hashing functions, and perhaps other functions. With your strategy, it's not possible to, say, have an equality and hashing function that are out-of-sync. Also, whether an operation or data structure uses hashing is completely hidden.

The big drawback, as I think you've alluded to, seems to be the cost. Converting a large tree to make sure the leaves are immutable would be expensive, for example, as a prerequisite to discovering that the big tree is not equal to #f. Separate conversions over pieces of an otherwise shared data structure could also lead to asymptotically worse space consumption or time, depending on whether a representative is retained as a key. Even for data that's consistently small so that there's no asymptotic-performance question, the difference between a direct equality comparison and going through a synthesized intermediate value can involve a significant constant factor, and a constant factor on a common operation adds up.

On a somewhat related note, eq-hash-code doesn't work as a way to find a representative for eq? comparison, because eq-hash-code is just a hash function (i.e., it loses inforamtion). Pinning down an address for each object creates all sorts of fragmentation issues, whether the address is the actual one (so fragmentation at the main memory allocator) or just allocated from a conceptual space (i.e., a new kind of allocator that must keep track of allocated addresses, even if there's no payload, making eq? more expensive).

countvajhula commented 2 years ago

This is great @mflatt , I appreciate your taking the time. On the face of it, I feel at least some of these concerns can be favorably addressed. I'll give it more thought and share my findings soon.