[swift-dev] Rationalizing FloatingPoint conformance to Equatable

[Xiaodi Wu]

On Wed, Oct 25, 2017 at 9:05 PM, David Zarzycki <dave at znu.io> wrote:

>
>
> On Oct 25, 2017, at 19:25, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
> I was proposing something different where Float and Int are both Equatable
>> and Substitutable, but neither Equatable nor Substitutable inherit from the
>> other. The former is mathematical and the latter is not (which allows it to
>> deal with NaN payloads, ±0, etc). Generic algorithms care mostly if not
>> completely about mathematics, while generic containers care mostly if not
>> completely about substitutability. They can live alongside each other and
>> get along peacefully/sanely. And if people need to care about both, then at
>> least they have an out.
>>
>
> The issue with this is similar to that in my reply earlier about bitwise
> comparison of floating-point values. Yes, you can propose some total
> ordering over floating-point values totally divorced from `==`, but I'm
> quite certain that people who invoke `sort()` on an array of floating-point
> values don't simply want *some* deterministic order, but rather an actual
> increasing order of numeric values.
>
>
> Hi Xiaodi,
>
> Of course, and the implementors of floating point data types would be
> expected to do just that. It isn’t hard. For example, in C:
>
> // Make floats sort reliably and sufficiently reasonably
> bool sortableLessThan(float x, float y) {
>   union {
>     int i;
>     float f;
>   } ux = { .f = x }, uy = { .f = y };
>   int high_bit = ~INT_MAX;
>   int x2 = ux.i >= 0 ? ux.i : (~ux.i | high_bit);
>   int y2 = uy.i >= 0 ? uy.i : (~uy.i | high_bit);
>   return x2 < y2;
> }
>
> Which the compiler vectorizes down to the following branchless code (which
> is debatably “reasonable” for sorting):
>
> c.o`sortableLessThan:
> c.o[0x0] <+0>:   vinsertps $0x10, %xmm1, %xmm0, %xmm0 ; xmm0 =
> xmm0[0],xmm1[0],xmm0[2,3]
> c.o[0x6] <+6>:   vmovlps %xmm0, -0x8(%rsp)
> c.o[0xc] <+12>:  vpmovsxdq -0x8(%rsp), %xmm0
> c.o[0x13] <+19>: vpcmpeqd %xmm1, %xmm1, %xmm1
> c.o[0x17] <+23>: vpcmpgtq %xmm1, %xmm0, %xmm1
> c.o[0x1c] <+28>: vpor   0x2c(%rip), %xmm0, %xmm2
> c.o[0x24] <+36>: vpxor  0x34(%rip), %xmm2, %xmm2  ; (uint128_t)
> 0x00007fffffff000000007fffffff0000
> c.o[0x2c] <+44>: vblendvpd %xmm1, %xmm0, %xmm2, %xmm0
> c.o[0x32] <+50>: vmovd  %xmm0, %eax
> c.o[0x36] <+54>: vpextrd $0x2, %xmm0, %ecx
> c.o[0x3c] <+60>: cmpl   %ecx, %eax
> c.o[0x3e] <+62>: setl   %al
> c.o[0x41] <+65>: retq
>

We already have a similar function in Swift (`isTotallyOrdered`) which
complies with IEEE requirements for total order, and we do not need to
invent another such algorithm.

As I have said, the same approach is not useful for what you call
"substitutability." What useful generic algorithms can be written that make
use of the bitwise _equality_ of two floating-point values?


> Likewise, when someone asks if an array contains a floating-point value
> (say, `10.0 as Decimal`), they generally want to know if *any*
> representation of that value exists.
>
>
> I’ve been thinking about the “contains” API argument a lot today, and I’m
> of the opinion now that we’re arguing about a problem that doesn’t exist.
>
> The “contains” question doesn’t make sense because of rounding errors that
> are inherent in floating point arithmetic. People would need to write
> “.contains(value: x, plusOrMinus: y)” and there is no way that the generic
> collection types are going to vend such an API. If anything, the “contains”
> API needs to be limited to types that conform to (hand waving) some kind of
> “PreciseValue” protocol (which floating point would not). For the exact
> same rounding-error reasons, I don’t think floating point types should be
> hashable either.
>

This is looking at it backwards. Collection vends a "contains" method and
it must do something for floating-point values. It would be exceedingly
user hostile to have it compare values bitwise. If people want to account
for rounding errors, there's `contains(where:)`, but it is entirely
legitimate to ask whether a collection contains exactly zero, exactly
infinity, or any of a variety of exactly representable values.

The point is that _what kind of substitutability_ matters, and the kind
> that people will expect for floating-point values is the very mathematical
> substitutability that is supposed to be guaranteed by Equatable, which
> simply does not accommodate NaN.
>
>
> Given that rounding errors make “contains” and “hashing” impractical to
> use with floating point types, I don’t see any holes with my (hand waving)
> “Substitutability” proposal. I could be missing something though. Can you
> think of anything?
>

By your argument, every generic use of `==` is impractical for
floating-point types. If you believe, then, that you don't need to consider
how these "impractical" APIs on Collection work with floating-point types
because they shouldn't be used in the first place, then why bother to make
any changes at all to the semantics of `Equatable`? The only changes we're
talking about here are to do with how these "impractical" APIs behave.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20171026/69483354/attachment.html>