Comparison Semantics

Development Semantics
1

I mentioned that there were historical ways to overflow the C stack besides the evaluator. Anything that uses C recursion could be a problem...so the internals of copying, molding, and comparison were some examples of that.

These overflows were guarded by the evil non-standard checks (that don't work in Wasm). So while they may not seem like a priority, they're things that have to be changed.

Revisiting code for these functions is a sensible time for reviewing the sanity of the model of how these things were being done. There's work involved in the stackless conversion, and it also helps break the monotony to think about another issue.

I decided to look at comparison this week--the core question of what it is, and how other languages approach it. It's really complicated and kind of overwhelming...so I'm looking to find a "good enough" answer that leaves room for future-forward improvements.

A Performance Observation

Consider an API for two-argument generic compare operation that can return one of three answers:

 >> compare 10 20
 == LT  ; Less-Than

 >> compare 0 0
 == EQ  ; Equal

 >> compare 30 4
 == GT  ; Greater-Than

Many languages provide something along these lines. For instance: C has strcmp() which will compare two strings and return -1 for the first less than the second, 0 for equal, and 1 for the first being greater than the second. This interface is enough that you can use it as the basis for your >, < and = operators...as well as your >=, <= and <> operators.

But...what if your datatype can very quickly determine if things are equal or not, and then there's a greater cost to checking the finer point of whether it is less than or greater than something? It might help if you passed the kind of comparison you wanted to do in as a three-argument operation. So that would be more like:

>> compare 'EQ 10 20
== #[false]

>> compare 'GE 30 4   ; Greater-or-Equal
== #[true]

Or you could just define six different entry points, instead of passing in the parameter of the operation you want. C++ is like that...each comparison operator (>, <, <=, >=, ==, !=) can be overloaded separately. This can be done even to the point of being internally contradictory...or just using the symbols, but not having anything to do with comparisons at all.

As a notable data point: Python2 used a single method on objects called __cmp__ that returned -1 or 0 or 1. This was changed in Python3 to allow six separate overloading entry points with "rich comparisons". Their motivation was not performance, but to break off the constraints of integer results so that NumPy arrays could do something along the lines of:

>> [10 2 0] < [3 4 0]
== [#[true] #[false] #[true]]

(This might not make sense for BLOCK! in Rebol, but perhaps it would make sense for VECTOR! or other types.)

Making Equality (Eq) and Ordering (Ord) Separate

Another thing to consider in designing comparison methodology into types is if it's best to separate out the characteristics of equality and ordering completely.

The place to look for thinking on this front is Haskell, which makes Eq and Ord "typeclasses" (which you can think of as something like "interfaces" in OOP, basically a list of supported functions that members of that typeclass must implement).

Rust followed along with its own Eq and Ord, and added something called "PartialEq" which relates to wanting to avoid some strange edge cases in floating point numbers.

(Rust's discernment is probably one worth weighing in, as they had the benefit of hindsight to make the decision on its importance: "Floating point values do not have a sensible notion of equality. Arguably, it is an error in Haskell that the expression even type checks.")

Comparing Types to Each Other vs. Other Types

Allowing different types to compare is a whole separate can of worms. You'll note that historically, Rebol is willing to do equality comparisons (and just consider unlike types to be not equal most of the time):

rebol2>> [] == <tag>
== false

rebol2>> 0 == none
== false

But the relative comparison operators were less tolerant:

rebol2>> [] < <tag>
** Script Error: Expected one of: block! - not: tag!

rebol2>> 0 < none
** Script Error: Expected one of: integer! - not: none!

But this intolerance makes the behavior of SORT seem suspect:

rebol2>> sort [[] <tag> 0 none]
== [none 0 <tag> []]

There clearly was some notion of ordering involved. It seems either that should also be an error, or the comparison should match what you'd get from a sort.

The plot thickens when you noticed R3-Alpha still errors on the comparison, but does the sort differently:

r3-alpha>> sort [[] <tag> 0 none]     
== [0 <tag> [] none]

And Red has yet another answer:

red>> sort [[] <tag> 0 none]
== [[] 0 none <tag>]

Putting all that aside for a moment :roll_eyes: we can imagine that letting types compare themselves to others could be a bit of a minefield. What if A and B are different types, and you say if A == B [...]... and ask A whether it's equal to B and says yes. But if you wrote it the other way and asked if B == A [...] the type for B said they weren't equal?

If you read that Python 3 Rich Types document I linked earlier, there's no fancy answer. They just say the object on the left gets first dibs to interpret its comparison to the right value. Then if the left says it doesn't know how to do the request (it can return None instead of a comparison result), the object on the right gets a chance to compare with the left.

(I'll mention that C++ puts the left type in charge for comparisons when they are declared as member functions, with no pre-defined system of delegating to the right...though you could invent one for your own types. However, it's also possible to do "global overloads" which can be registered for any pair of types. These don't belong to either the left or right hand side.)

The Role of Implicit Coercion in Comparison

Adding even more nuance into this whole mire, is the question of higher-level mechanics in the language which automatically convert values between types in order to make them comparable to each other. :-/ If these mechanics exist, then it means that two types might be able to compare with each other even when they don't have any specific methods for understanding the other type.

This plays a big part in C++. But Rebol would appear to not have such a mechanism, as it doesn't even let you pass INTEGER! to DECIMAL! parameters:

>> f: func [d [decimal!]] [print ["The decimal is:" d]]
>> f 10
** Script error: f does not allow integer! for its d argument

The reality is a bit more subtle, however... as you can compare integers and decimals. This actually comes from a coercion mechanic that is hard-coded specifically into the comparison operators.

R3-Alpha's Comparison Methodization was REALLY ad hoc

Compare_Values() -- which is the main entry point for the implementation of operators like >, <, =... is outright bizarre:

REBINT Compare_Values(REBVAL *a, REBVAL *b, REBINT strictness)

Compare 2 values depending on level of strictness.
NOTE: MODIFIES a and b args.

Strictness:
0 - coerced equality
1 - equivalence
2 - strict equality
3 - same (identical bits)

-1 - greater or equal
-2 - greater

The Compare_Values() routine does the kind of baked in higher-level coercion of numeric types described. Ultimately it decides if it needs to fall-through to a type specific method, which is a function named CT_XXX like CT_Object() or CT_Word(). Those functions are guaranteed that the two arguments have been coerced into the same typeclass--(e.g. both ANY-WORD!) but not necessarily the exact same type.

Using magic numbers makes the process somewhat obtuse. But the CT_XXX methods can return -1 if the comparison requested by "strictness" is not legal, 0 if it didn't match the constraint, and 1 if it did match. The method implementations are very scattershot, and I've started hammering them into a conventional and simple form so they still pass the tests...but can be looked at more clearly.

Rebol's Main Difference: "Levels" of Equality

A real curveball we see here is that Rebol is trying to methodize different kinds of equality. No other methodization of comparisons in other languages seems to have this.

(Note: Strict equality and Sameness are two levels people are familiar with. "Equivalence" refers to the EQUIV? operation, that could ask if two words were not just the same case-insensitive word but also bound to the same thing...Ren-C axed this fairly early on as there were no usages in the code, and it seemed to just confuse things. If it came up, someone could ask if they wanted by checking the bindings themselves.)

When other languages have a difference between equality and "strict" equality, the strict form merely limits what coercion is done. The phrasing for instance of JavaScript's === operator is "check BOTH value AND type". This could cover Rebol's difference between 1.0 == 1 and 1.0 = 1, but it wouldn't cover the case sensitivity aspect of the current string comparison behavior.

Have to go, so I'll cut this survey post short. But I'll close by saying:

  • It would be a simpler world if strict equality == (or is) had the simple definition like === in JavaScript:

      is: ==: func [a b] [
      did all [
          (type of :a) = (type of :b)
          :a = :b
      ]
  ]

    But that won't account for case-sensitivity. Which is a bummer.

  • I have an uneasy feeling about building comparison operators on top of method code that carries along a boolean "strict" argument. It seems like a kind of arbitrary and poorly-defined wart. I'm not sure what the alternatives are, however, if the current abilities are to be preserved.

  • My intuition is that it's probably better to build "downwards in formality" from the typeclasses of Haskell/Rust, as opposed to trying to build "upwards in formality" from something like Python's approach, just because I am skeptical of the organic comparisons that can so easily become inconsistent...e.g. by prioritizing the left side's answer in a comparison over the right.

  • Having done some surveying about what others do, it's probably a good next step to just kind of work through what actual user scenarios are that use comparisons...and how to make those scenarios work. I showed sort giving 3 different results on Red, R3-Alpha, and Rebol2 for a collection of unlike objects...which suggests there's a real need to lay out what a sensible minimal set of requirements are to make "real" sorting scenarios behave well.

Bottom line is there's a lot to think about, and I didn't even get to Unicode canonization vs. normalization as it relates to built in string compare concepts. :-/ Stay tuned...

2 Likes
2

Great summary of a messy topic.

3

In creating a chess game (or the like) there is a need to order the moves from better expectancy to lowest expectancy, or the other way, does not really matter as long as the moves get sorted. The generated move value is often the same for many moves depending on the complexity of the evaluation function.
Anyway the most algorithms for sorting are always sorting only the values not the objects they belong to. It would be helpful if such a service came with the language.

4

Another example of how Python users have exploited rich comparisons is SQLAlchemy. There, they make it so that comparisons of their types actually produce filters, e.g.:

model1.filter(model1.column <= model2.column)

...would result in a SQL query along the lines of:

select model1.*
from model1
left join model2 on model1.foreign_key == model2.primary_key
where
    model1.column <= model2.column

They could have done this in separate assignments:

filt = model1.column <= model2.column
model1.filter(filt)

I'm conflicted over how to think about this. We could argue that Python only needs such weirdness because they are more boxed-in when it comes to being able to use symbols like <= in a customized way. They can't make dialects and just inspect WORD!s structurally. They could solve this by taking a BLOCK! to your filter(), instead of burdening the evaluator with some odd overload of <=. (Though that wouldn't let them break the expressions out into variables, as with filt above.)

On the other hand...comparing vectors represents a more sympathetic case. comparisons: vector1 < vector2 does not have anything analogous to the filter() that is in control, and seems reasonable. So if one's goal is to make the most freeform language ever invented, then shouldn't < be hookable?

One way of looking at it could be if operators like < were a generic hookable function at a higher level than lesser?. So things like SORT would be based on the comparison mechanics, and what < did would be customizable through overloads...falling back to LESSER? if there weren't any.

5

Looking at it, I wonder if it might be in the comparison space as "not equal, but trivially convertible"? Maybe a nicer-to-look-at alternative to ~=

x: <foo>
y: "foo"

>> x = y
== #[false]

>> x <-> y
== #[true]

>> x ~= y  ; uglier...
== #[true]

The idea of it looking kind of like <> isn't necessarily that bad, because it's saying they're not actually equal.

In any case, I'm still rather opposed to the idea that:

rebol2>> (first [a]) = (first [a:])
== true

Case sensitivity is bad enough, but having the natural and easy-to-reach-for equality operator say a SET-WORD! and a WORD! are equal is a bridge too far. Also note:

rebol2>> [a] = [a:]
== false

Anyway, just wanted to mention the possibility of using a newly opened-up arrow word for a comparison purpose...