Do std::min(0.0, 1.0) and std::max(0.0, 1.0) yield undefined behavior?

Question

The question is pretty clear. The following gives the reason why I think these expressions might yield undefined behavior. I would like to know whether my reasoning is right or wrong and why.

Short read:

(IEEE 754) double is not Cpp17LessThanComparable since < is not a strict weak ordering relation due to NaN. Therefore, the Requires elements of std::min<double> and std::max<double> are violated.

Long read:

All references follow n4800. Specifications of std::min and std::max are given in 24.7.8:

template<class T> constexpr const T& min(const T& a, const T& b);
template<class T> constexpr const T& max(const T& a, const T& b);
Requires: [...] type T shall be Cpp17LessThanComparable (Table 24).

Table 24 defines Cpp17LessThanComparable and says:

Requirement: < is a strict weak ordering relation (24.7)

Section 24.7/4 defines strict weak ordering. In particular, for < it states that "if we define equiv(a, b) as !(a < b) && !(b < a) then equiv(a, b) && equiv(b, c) implies equiv(a, c)".

Now, according to IEEE 754 equiv(0.0, NaN) == true, equiv(NaN, 1.0) == true but equiv(0.0, 1.0) == false we conclude that < is not a strict weak ordering. Therefore, (IEEE 754) double is not Cpp17LessThanComparable which is a violation of the Requires clause of std::min and std::max.

Finally, 15.5.4.11/1 says:

Violation of any preconditions specified in a function’s Requires: element results in undefined behavior [...].

Update 1:

The point of the question is not to argue that std::min(0.0, 1.0) is undefined and anything can happen when a program evaluates this expression. It returns 0.0. Period. (I've never doubted it.)

The point is to show a (possible) defect of the Standard. In a laudable quest for precision, the Standard often uses mathematical terminology and weak strict ordering is only one example. In these occasions, mathematical precision and reasoning must go all the way.

Look, for instance, Wikipedia's definition of strict weak ordering. It contains four bullet points and every single one of them starts with "For every x [...] in S...". None of them say "For some values x in S that make sense for the algorithm" (What algorithm?). In addition, the specification of std::min is clear in saying that "T shall be Cpp17LessThanComparable" which entails that < is a strict weak ordering on T. Therefore, T plays the role of the set S in Wikipedia's page and the four bullet points must hold when values of T are considered in its entirety.

Obviously, NaNs are quite different beasts from other double values but they are still possible values. I do not see anything in the Standard (which is quite big, 1719 pages, and hence this question and the language-lawyer tag) that mathematically leads to the conclusion that std::min is fine with doubles provided that NaNs are not involved.

Actually, one can argue that NaNs are fine and other doubles are the issue! Indeed, recall that there's are several possible NaN double values (2^52 - 1 of them, each one carrying a different payload). Consider the set S containing all these values and one "normal" double, say, 42.0. In symbols, S = { 42.0, NaN_1, ..., NaN_n }. It turns out that < is a strict weak ordering on S (the proof is left for the reader). Was this set of values that the C++ Committee had in mind when specifying std::min as in "please, do not use any other value otherwise the strict weak ordering is broken and the behavior of std::min is undefined"? I bet it wasn't but I would prefer to read this in the Standard than speculating what "some values" mean.

Update 2:

Contrast the declaration of std::min (above) with that of clamp 24.7.9:

template<class T> constexpr const T& clamp(const T& v, const T& lo, const T& hi);
Requires: The value of lo shall be no greater than hi. For the first form, type T shall be Cpp17LessThanComparable (Table 24). [...]
[Note : If NaN is avoided, T can be a floating-point type. — end note]

Here we clearly see something that says "std::clamp is fine with doubles provided that NaNs are not involved." I was looking for the same type of sentence for std::min.

It's worth taking notice of the paragraph [structure.requirements]/8 that Barry has mentioned in his post. Apparently, this was added post-C++17 coming from P0898R0):

本文档中定义的任何概念的必需操作不一定是全部功能；也就是说，某些必需操作的参数可能导致无法满足所需语义。[示例：StrictTotallyOrdered概念（17.5.4）的必需<运算符在NaN上运行时不满足该概念的语义要求。—结束示例]这不会影响类型是否满足该概念。

这是解决我在此处提出的问题的明确尝试，但是是在概念的上下文中（正如Barry所指出的，Cpp17LessThanComparable不是一个概念）。另外，恕我直言，该款也缺乏精度。

Answer 1

在新的[concepts.equality]中，在稍微不同的上下文中，我们具有：

表达式是平等保留给定相等的输入，以相等的输出表达式的结果，如果，。表达式的输入是表达式操作数的集合。表达式的输出是表达式的结果以及该表达式修改的所有操作数。

对于给定的表达式，并非所有输入值都必须有效。例如，对于整数a和b，a / b当bis 时表达式的定义不明确0。这并不排除表达式a / b保持相等。表达式的域是要求为其明确定义表达式的一组输入值。

尽管在整个标准中都没有完全表达一个表达域的概念，但这是唯一合理的意图：语法要求是类型的属性，语义要求是实际值的属性。

更笼统地说，我们也有[structure.requirements] / 8：

本文档中定义的任何概念的必需操作不一定是全部功能；也就是说，某些必需操作的参数可能导致无法满足所需语义。[？示例：在s 上<操作时，StrictTotallyOrdered概念的必需运算符（[concept.stricttotallyordered]）不满足该概念的语义要求NaN。-？最终示例？]这不会影响类型是否满足该概念。

这是专门指概念，而不是诸如Cpp17LessThanComparable之类的已命名需求，但这是理解库打算如何工作的正确精神。

当Cpp17LessThanComparable给出语义要求时

< 是严格的弱排序关系（24.7）

违反此规则的唯一方法是提供一对违反严格弱排序要求的值。对于喜欢类型double，这将是NaN。min(1.0, NaN)是未定义的行为-我们违反了算法的语义要求。但是，对于浮点没有NaN，< 是一个严格的弱序-这样的罚款...你可以使用min，max，sort，所有你喜欢。

展望未来，当我们开始编写使用的算法时operator<=>，这种域概念是表达语法要求ConvertibleTo<decltype(x <=> y), weak_ordering>错误的原因之一。有x <=> yBE partial_ordering是好的，它只是看到一对值，其中x <=> y是partial_ordering::unordered不是（至少我们可以诊断，通过[[ assert: (x <=> y) != partial_ordering::unordered ]];）

Answer 2

Disclaimer: I do not know the full C++ standard, I did research a bit about what was said about floats. I do know about IEEE 754-2008 floating-point numbers and C++.

Yes, you are right, this is undefined behavior by the C++17 standard.

Short read:

The standard does not say that std::min(0.0, 1.0); is undefined behavior, it says constexpr const double& min(const double& a, const double& b); is undefined behavior. It means, it's not applying the function that is not defined, it's the function declaration itself that is undefined. As is the case mathematically : a minimum function isn't possible on the full range of IEEE 754 floating-point numbers, as you have noted.

But undefined behavior does not necessarily mean a crash or compiling error. It just means it is not defined by the C++ standard, and specifically says it may "behaving during translation or program execution in a documented manner characteristic of the environment"

Why you shouldn't use std::min on doubles:

Because I realize the following long read section can get boring, here is a toy example of the risk of NaNs inside comparisons (I don't even try sorting algorithms…):

#include <iostream>
#include <cmath>
#include <algorithm>

int main(int, char**)
{
    double one = 1.0, zero = 0.0, nan = std::nan("");

    std::cout << "std::min(1.0, NaN) : " << std::min(one, nan) << std::endl;
    std::cout << "std::min(NaN, 1.0) : " << std::min(nan, one) << std::endl;

    std::cout << "std::min_element(1.0, 0.0, NaN) : " << std::min({one, zero, nan}) << std::endl;
    std::cout << "std::min_element(NaN, 1.0, 0.0) : " << std::min({nan, one, zero}) << std::endl;

    std::cout << "std::min(0.0, -0.0) : " << std::min(zero, -zero) << std::endl;
    std::cout << "std::min(-0.0, 0.0) : " << std::min(-zero, zero) << std::endl;
}

When compiling on my macbookpro with Apple LLVM version 10.0.0 (clang-1000.10.44.4) (I make the precision, because, well, this is undefined behavior, so this may in theory have different results on other compilers) I get:

$ g++ --std=c++17 ./test.cpp
$ ./a.out
std::min(1.0, NaN) : 1
std::min(NaN, 1.0) : nan
std::min_element(1.0, 0.0, NaN) : 0
std::min_element(NaN, 1.0, 0.0) : nan
std::min(0.0, -0.0) : 0
std::min(-0.0, 0.0) : -0

Which means that contrary to what you might assume, std::min is not symmetric when NaNs are involved, or even -0.0. And NaNs do not propagate. Short story: That did provoke me some pain on a previous project, where I had to implement my own min function to correctly propagate NaNs on both sides as was required by the project specification. Because std::min on doubles is not defined!

The IEEE 754:

As you have noted, IEEE 754 floating-point numbers(or ISO/IEC/IEEE 60559:2011-06, which is the norm used by C11 standard see below, which more or less copies IEEE754 for the C language) does not have a strict weak ordering, because NaNs violates the transitivity of incomparability (fourth point of the Wikipedia page)

The fun part is that the IEE754 norm has been revised in 2008 (now named IEEE-754-2008), which includes a total ordering function. The fact is that both C++17 and C11 do not implement IEE754-2008, but rather ISO/IEC/IEEE 60559:2011-06

But who knows? Maybe that would change in the future.

Long read:

First, let's start by recalling what undefined behavior actually is, from the same standard draft you linked (emphasis is mine):

undefined behavior behavior for which this document imposes no requirements

[Note 1 to entry: Undefined behavior may be expected when this document omits any explicit definition of behavior or when a program uses an erroneous construct or erroneous data. Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). Many erroneous program constructs do not engender undefined behavior; they are required to be diagnosed. Evaluation of a constant expression never exhibits behavior explicitly specified as undefined in Clause 4 through Clause 14 of this document (7.7). —end note]

There is no such thing as "yielding" undefined behavior. It is simply something that is not defined in the C++ standard. Which may mean you may use it and get correct result at your own risk (like by doing std::min(0.0, 1.0); Or it might raise warning or even compilation errors, if you find a compiler that is really careful about floating-point numbers!

About the subset… You say:

I do not see anything in the Standard (which is quite big, 1719 pages, and hence this question and the language-lawyer tag) that mathematically leads to the conclusion that std::min is fine with doubles provided that NaNs are not involved.

I do not have read the standard myself either, but from the part you posted, it seems the standard already says this is fine. I mean, if you construct a new type T that wraps doubles excluding the NaNs, then the definition of template<class T> constexpr const T& min(const T& a, const T& b); applied to your new type will have a defined behavior, and behave exactly like you would expect from a minimum function.

We could also look at the standard definition of operation < on double, which is defined in the section 25.8 Mathematical functions for floating-point types which says the not really helpful:

The classification / comparison functions behave the same as the C macros with the corresponding names defined in the C standard library. Each function is overloaded for the three floating-point types. See also: ISO C 7.12.3, 7.12.4

What does the C11 standard says? (Because I guess C++17 does not use C18)

The relational and equality operators support the usual mathematical relationships between numeric values. For any ordered pair of numeric values exactly one of the relationships — less, greater, and equal — is true. Relational operators may raise the ‘‘invalid’’ floating-point exception when argument values are NaNs. For a NaN and a numeric value, or for two NaNs, just the unordered relationship is true.241)

As for the norm C11 uses, it is under the annex F of that norm:

This annex specifies C language support for the IEC 60559 floating-point standard. The IEC 60559 floating-point standard is specifically Binary floating-point arithmetic for microprocessor systems, second edition (IEC 60559:1989), previously designated IEC 559:1989 and as IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE 754?1985). IEEE Standard for Radix-Independent Floating-Point Arithmetic (ANSI/IEEE854?1987) generalizes the binary standard to remove dependencies on radix and word length. IEC 60559 generally refers to the floating-point standard, as in IEC 60559 operation, IEC 60559 format, etc.