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 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
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_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.)
=== 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
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
sortgiving 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...