[std-interval] Suggestions for the 2006-09 draft

[Guillaume Melquiond]

Le mercredi 20 septembre 2006 à 14:18 -0700, G. William Walster a
écrit :

> Keeping the above five principles in mind, here are some specific
> illustrative example in the current draft that appear to be violations
> of them:
> 
> 1) Last 4 lines on page 4:  Not all operations on an empty interval
> produce an empty result.  The hull operator is the one exception. This
> is a good reason why un-initialized intervals should be set to the
> whole interval.  They will propagate (except through the intersection
> operator with a finite interval) and be noticed quickly when
> debugging.  They cannot result in a containment failure.

Sorry, I don't understand what the "good reason" is. This cannot be the
fact that "they will propagate". Indeed, whole intervals do not
propagate through intersect nor cos nor sin nor square nor sqrt nor exp
nor pow (with an even exponent) nor atan nor cosh nor any other function
with a codomain shorter than the whole real line. Empty intervals do. I
don't understand either why it would be quicker to notice whole
intervals than empty intervals when debugging, especially as there is an
is_empty predicate but no is_whole predicate.

> 2) Page 5 second paragraph: The goal of not requiring language changes
> is fine.  However, consistent with principles 3) and 4), above, do not
> preclude an intrinsic compiler implementation.

It seems you want us to remove the interval class, so that intrinsic
types can be used instead. I may be too pessimistic, but I think the
proposal would automatically become void after such a change. There are
a few standardization experts on this list, I hope they can give us an
enlightened opinion on what would presumably happen if we were to scrap
the class definition and replace it with a sentence like "There are
three types named interval_float, interval_double, and
interval_long_double."

> 4) Page 6 - Empty Interval: Relative to the discussion of
> implementations on platforms that do not support NaNs, opaqueness
> solves the difficulty.

I don't see any difficulty that needs solving. This is a non-normative
paragraph meant to help vendors implement an interval library. We are
explaining there that using NaNs for bounds leads to an efficient
implementation of empty intervals. I don't see the point in removing
this paragraph (?).

> 5) Page 7 - [a;b] notation:  Why not let this be a localization
> option, as is the use of , or . for a decimal point?  This is
> consistent with principle 5), above.  For example, in countries that
> use a comma for a decimal place, they should be free to adopt the
> semicolon delimiter.  Doing so will not conflict with the use of the
> comma for an interval delimiter by other countries.  Thus, [2.3, 4.5]
> can be unambiguously localized to [2,3; 4,5], or [2,3: 4,5].  This
> need not be specified in the proposed standard.

Quite the contrary in fact. If we let the notation be a localization
option, the proposal would have to specify a lot more than it currently
does. It would require modifying the current Standard to add new members
to the numpunct facet at the very least. This may be more satisfying,
but it means a longer and more intrusive proposal.

This makes me wonder if interval(char const *) should specify that the
string is always parsed with the C locale.

> 6) Page 7 - order relations on empty intervals and - Why do
> "certainly" comparisons return "true" for empty intervals?: There are
> good reasons why *all* relations tests on empty intervals should
> return false.

There are also good reasons to have "certainly" comparisons return true
on empty intervals. If you use the following definition for a certainly
less-than, then true is the natural answer when an empty interval is
involved. Given A and B two intervals, A < B is defined as

    forall a in A, forall b in B, a < b

Moreover, this gives the following conservative identity:

    certainly(a < b) == !possibly(a >= b)

So, as they both have their pros and cons, we need a strong rationale to
decide between returning true and returning false when certainly
comparing an interval with the empty set.

> 7) Page 7 - Should std::set<interval> work?:  By this, I presume is
> meant that sets or lists of intervals could be defined and used.  The
> issue raised, if I understand it, is that because intervals are not
> naturally unambiguously ordered, this cannot be done.  On the
> contrary, when lists (sets) of interval and/or interval vectors (or
> boxes) are used, as they often are ordered using some scalar function
> of them, such as width, relative error upper bound, or the upper bound
> on an objective function in an optimization algorithm.  So, as long as
> set ordering can be performed a result of computing a scalar function
> of the elements of the set, there should be no reason why this
> possibility should not be supported.

I think you have missed the actual issue this paragraph refers to. In
the C++ standard library, std::set<T> means std::set< T, std::less<T> >
and std::less<T> is defined as a functional class for operator<(T,T). As
a consequence, in order for std::set<interval> to work out of the box,
we either have to specify a specialization for std::less<interval> or to
specify an operator<(interval,interval) with a strict weak ordering.
None of these two specifications are desirable.

> 8) Page 8 - Memory layout.  This issue vanishes if interval data types
> are opaque.

As detailed in the paragraph, there is an active defect report related
to std::complex being opaque and without any memory layout. Specifying
std::interval as having the same defect as std::complex would require a
strong rationale in my opinion. I don't think it is sufficient to say
that it allows an implementation to provide non-standardized features.
If the opaqueness allowed a better implementation of the standardized
features, then this would be a strong enough rationale for removing the
memory layout.

> The following typo was noticed by Mike Schulte:
> 
> Page 3 - The specification states "Those optimizations, however, are
> necessary for implementing the proposal." I believe this should be
> "Those optimizations, however, are *not* necessary for implementing
> the proposal."

Thanks. Surprisingly, it seems somebody has already fixed this mistake,
as my local version reads "Those optimizations, however, are not
compulsory for implementing the proposal."

Thanks for all your comments.

Best regards,

Guillaume