[std-interval] Revised document available

[Guillaume Melquiond]

Le jeudi 14 septembre 2006 à 10:59 -0500, George Corliss a écrit :
> Sylvain and all,
> 
> > A revised version of the proposal is now available at:
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2067.pdf
> 
> Can you help me understand the difference between "undefined" and
> "implementation-dependent" or "implementation-defined"?

I don't think we put "implementation-dependent" situations on purpose.
It may simply be mistakes at places where we meant "implementation-
defined". I should review them.

"Implementation-defined" means "behavior, for a well-formed program
construct and correct data, that depends on the implementation and that
each implementation shall document." So it is a documented yet not
portable behavior. For example, the number of bits of an int is
implementation-defined.

"Undefined" (not "unspecified") applies when using "an erroneous program
construct or erroneous data". For example, overflowing signed integers
brings about undefined behavior in C and C++. It could fail an assertion
in debug mode or simplify execution paths when optimizing. In
particular, the compiler is allowed to assume that the sum of two
negative numbers is a negative number. Note that undefined behavior
situations are generally perfectly identified in the Standard.

> I am not familiar with the vocabulary of standards, but it would seem to me
> that "undefined" means that not only does the standard not specify what the
> result should be, but that no one else does, either.  In principle, the
> result is permitted to be non-deterministic on a single machine, let alone
> on a single implementation.

Yes, non-deterministic describes it fine.

> I would expect "implementation-dependent" to mean that the choice is up to
> the implementation.  I see you often use "implementation-defined," which I
> would interpret to mean that it is the responsibility of the implementation
> to specify what it will do and then to do what it specified?

Exactly. The behavior could even depend on a compiler option.

> If those interpretations are consistent with standard writing practice, is
> there a reason to leave ANYTHING "undefined?"  If we cannot specify results
> for each implementation, should not the implementers be required to specify,
> that is, to be "implementation-defined"?

When you specify that, for some entries, the result is implementation-
defined, it means you force the implementer to test for these specific
entries, to define a result, and to document it. Let us consider the two
ways of querying a lower bound in the proposal.

On one hand, x.lower() returns the lower bound of x. But if x is empty,
the result is undefined. On the other hand, inf(x) returns the lower
bound of x, or infinity if x is empty. But if x is empty and infinities
do not exist, the result is implementation-defined.

As a consequence, a library implementer is allowed to write a trivial
version of lower: this is just a memory read. It is also possible to
assert that the interval is not empty. Indeed, a failed assertion is a
typical example of undefined behavior, so this is allowed.

For inf, the situation is different: the behavior is always defined,
whether x is empty or not. The implementation has to test for this case
and deal with it in a documented manner. If the implementation provides
infinities, the standard specify what the result is. Otherwise, it is up
to the implementation to specify it.

I hope this illustrates that allowing undefined behavior on some inputs
allows to write more efficient code. The lower member could have been
changed to "implementation-defined", but then it may have considerably
slowed down codes that are known not to generate empty intervals. On the
other hand, it means the user has to be careful and use inf if the code
can generate empty intervals. I think this is a good compromise.

> If that makes sense, would it also make sense to specify that
> implementations on IEEE machines take advantage of IEEE support?  For
> example, one might say, "On machines that support infinities, ... On other
> machines, ... is implementation-defined."  That would be a MUCH stronger
> specification of portability without imposing additional requirements in
> practice.

Note that this is already the case for inf(). For other functions, it
would depend on what you put behind your "..." dots. Note also that the
current wording impose the use of infinities for arithmetic functions if
the implementation supports them, as they are the only way to enclose
some theoretical interval results. So the question becomes: should we
impose implementations to document the results they return when they
would have to return an interval containing an infinite bound? I'm not
sure it is worth it, as I don't see how such a documentation would help
developers.

Best regards,

Guillaume