[std-interval] Comments on the Interval Standard Proposal

[Guillaume Melquiond]

Le lundi 25 septembre 2006 à 21:27 -0700, Lawrence Crowl a écrit :
> My comments are based on 2006-09-05 revision 1.
> 
> III Impact on the Standard
> 
>    paragraph 3:  "however, are necessary" => "however, are not necessary"
> 
> 26.6 Interval Numbers
> 
>    paragraph 2:  Remove bool.
>       This text is a holdover from an earlier version of the proposal.

Fixed.

> 26.6.1 Header <interval> synopsis
> 
>       Might be better to change the namespace from X_ops to X_comparisons?
>       Such a change is more in line with the actual content.

The name was inspired by the "rel_ops" STL namespace. I don't have an
opinion on what a good name would be, especially as it doesn't really
matter if the name is long since its main use is with "using namespace".

> 26.6.2 interval class template
> 
>       The standard doesn't actually need to provide a definition of the template
>       class interval.  That is, the specializations can be defined without a
>       definition for the template.  Is there a particular reason for defining the
>       template?

No particular reason. And I think this is not the first time we have had
this discussion and we had already agreed on removing the generic
definition. Done.

> 26.6.4 interval member functions
> 
>    whole();
> 
>       I do not see a definition of the static member function whole().
>       I am particularly interested in what whole().lower() et.al. means.

There is a definition in the proposal saying that "whole" returns [-inf,
+inf]. Anyway, there was some discussions on the list and now "whole" is
only defined as returning an interval containing all the real numbers.
There is no difference with the older definition for a 754-based
efficient implementation, but the function can now be defined on an
arithmetic without infinities.

Concerning the "lower" and "upper" members, I have fixed their
definitions along the lines of the "inf" and "sup" functions, so that
they return the corresponding infinities for unbounded intervals. When
infinities are not available, the behavior is implementation-defined.

>    interval(const char *s);
> 
>       I think undefined behavior here is a very bad idea.  The programmer
>       cannot effectively avoid the bad behavior without parsing the string
>       manually.  That is too much of a burden.  I suggest that the parse
>       either return empty (which is indistinguishable from a successfully
>       parsed empty) or return an error code, or throw an exception.  You
>       should ask the library experts for their prefered solution.

On the contrary, I think undefined behavior is a good idea :). The point
of this constructor is to define interval constants in the program, e.g.
``interval<float> Pi("[3.1415926,3.1415927]");''. With an undefined
behavior, we may hope that compilers will warn when they detect a syntax
error, as they already do with printf format strings.

The constructor was not meant to be used to convert user inputs. The STL
I/O stream machinery should be used instead as it will correctly detect
any mistyped input and report it to the program. Am I missing something?

>    interval(T t);
> 
>       What does "if the value of t is infinite, it will be interpreted as a finite
>       number to [sic] big to be representable when constructing the
>       interval" mean?  How does this statement affect my program?

This is a good question, and I'm not sure I have a good answer. The
point of this definition is to provide an interval that still respects
the inclusion property when an infinity is interpreted an overflow. From
an implementation point of view, it means that interval(+Inf) constructs
the interval [+Max,+Inf].

>    interval(T lo, T hi);
> 
>       The undefined behavior here is almost zero cost to avoid.  In particular,
>       under IEEE 754, the comparison <= returns false when either of its
>       operands are NaN.  The only cases that fail are interval(-oo,-oo) and
>       interval(oo,oo).  Assuming that the extra two comparsions to detect
>       these cases are too expensive, what are the consequences of defining
>       these two intervals to be valid?  (Remember, I am a language/compiler
>       person, not an interval person.)

If you don't manipulate intervals on the extended real numbers, then the
addition of two intervals [a,b] and [c,d] can be defined as [down(a+c),
up(b+d)]. So interval addition is just two floating-point additions. By
using the usual opposite trick, it can even be reduced to one single
SIMD operation (as this is done in RealLib on SSE2 for example).

Now let's suppose the interval [-Inf,-Inf] is valid and let's add [0,
+Inf] with our floating-point additions and IEEE-754 semantic. The
result is [-Inf,NaN] and this cannot do any good to the rest of the
program. In order to get a more sensible result like [-Inf,+Inf] (as
expected in a cset arithmetic for example), you would have to spend a
lot more time to compute the sum. (There was a proposal to change the
behavior of floating-point operations in directed rounding mode so that
they don't generate NaNs, but it wasn't included in 754R).

>    template<class U> interval(U x);
> 
>       I think the prefered form is template<typename U> ....
> 
>       What is the rationale for this template?  There isn't a corresponding
>       definition in the specializations.
> 
>       If the definition is to remain, the constraints on U need to be specified.

This was the remnant of an older version, when the various constructors
were not explicit. I, however, have kept the "U" symbol (defined as
being a primitive floating-point type different from "T"), as this makes
the text simpler to understand, in my opinion.

I have gone a bit farther and I also removed the "template<U>"
mixed-type member functions. This simplifies both the interface and the
implementation and I don't think people will miss this feature.

> 26.6.7 bool_set comparisons
> 
>    template< class T> bool_set operator<=(....
> 
>       The definition confused me greatly.  I spent quite a bit of time trying
>       to decide whether or not a<=b was the same as (a<b)|(a==b).
>       Eventually, I decided that it was.  However, the definition certainly
>       didn't lead one to easily conclude that they were the same.  I think
>       the proposal would be clearer if the "or" version of the definition were
>       used, particularly for those of us that know a<=b is not always the
>       same as !(b>a).

I added a note saying that a<=b is equivalent to (a<b)|(a==b) for
bool_set comparisons. This way, both interpretations are present for the
reader.

> 26.6.10 Set inclusion comparisons
> 
>    template< class T> bool operator<(....
>    template< class T> bool operator<=(....
> 
>       I think the 'returns' clause has the order of arguments to the
>       'contains' function reversed.

Fixed.

> On Infinity and NaN.
> 
>    I think the proposal might be substantially improved by recognizing
>    two categories of implementation -- those with infinity/NaN values
>    in their floating-point, and those without.  The second would have
>    degraded semantics.  The standard probably needs needs a macro
>    indicating the category.

I still have a few sentences to fix, but once it is done I expect the
proposal to be implementable whether infinities and NaNs are supported
or not. From a programmer point of view, the only difference in behavior
will be the values returned by the bounds functions "lower", "upper",
"inf", and "sup" for unbounded and empty intervals. This should be the
only degraded semantic and, as the proposal stands, it can be tested by
checking numeric limits. Is this the kind of degraded semantics you were
speaking about?

Thanks a lot for your comments.

Best regards,

Guillaume