[std-interval] Mathematical relations and default initialization

Sylvain Pion Sylvain.Pion at sophia.inria.fr
Fri Sep 15 12:08:54 PDT 2006


George Corliss wrote:
>>>>1- no default constructor at all
>>>>2- [0,0]
>>>>3- empty
>>>>4- whole
>>>>5- uninitialized tag
>>>>6- see below (something a la "singular iterator")
> 
> Could someone fill me in?  I'm not familiar with "singular iterator", and I
> found nothing "below" in the original message that helped me understand what
> is #6.  Is #6 equivalent to "undefined," in the sense that what you get is
> whatever bit pattern happened to be in that memory location from its
> previous use?

It is more an implicit specification which allows, among other things,
the behavior you mention, but also many others, like a debug mode to
detect use of uninitialized variables.

The specification for #6 could look like the following.  The wording
could be put in the default constructor specification, or at the
beginning of the chapter.

" An interval object is always in one of the two following exclusive
states: initialized or uninitialized.  The default constructor produces
uninitialized intervals.  The state is propagated through assignments
and copy constructors.  The other constructors produce initialized
intervals.  Other operations on uninitialized intervals have undefined
behavior, while operations on initialized intervals follow the semantic
described in this chapter. "

(one should check the full API to see if there are other cases where it
would be useful to specify a non-undefined behavior for uninitialized
intervals)

This specification allows both efficient (no cost) default constructors, 
as well as a debug mode for detecting use of uninitialized intervals,
or even initialization with "whole", or...


>>(while at it : concerning the propagation of empty, the current
>>proposal does not say anything, since any function taking empty
>>can return any interval: are there opinions on the sharpness of
>>returned intervals in this case?  we could easily enforce empty
>>as returned interval)
> 
> Ouch!  Yes, that is a (unintended?) consequence of not specifying tightness.

If there is consensus on that, then we can add the enforced propagation
of empty intervals.  I don't see cases where it would be a problem,
since I guess that the typical efficient representation of empty (with
NaNs) will propagate at no additional cost (or a negligible one) through
most operations.  On the other hand, I'm not sure it's very useful to
specify propagation of empty (is it?), so we must be sure that it has no
performance impact.


Not specifying tightness at all is easy, but it is also risky: it allows
a dumb ("return whole") implementation, be standard compliant.
Not very useful...
It would be nice if we could find a more useful specification.
I would be tempted by something like "for functions specified by IEEE
754[r] on floating-point, the corresponding interval version has to be
tight (return the smallest interval)".  Mentionning the IEEE754 standard
from the ISO C++ one is a problem, I heard, but something along these
lines could be a possibility.  Other ideas are highly welcome.
At the other end of the spectrum, we could look for the state of art
and specify the maximum tightness achievable today, but it may be not
so good either, due to a speed/tightness trade-off, so something in
between would probably be best (though hard to specify).  Maybe we
could hard-code a "3 ulp away from the tightest result" rule, or
something like that.


>>6 also has the advantage of speed, I'm thinking especially of array
>>initialization.
> 
> My understanding of C++ is that happens often, since in some parameter
> passing, a default constructor is called and then the appropriate values are
> copied into those locations.  Is that close?  Is that why is is a TOTAL
> waste of time to initialize an array that is about to be filled anyway?

It is not really for parameter passing.  The default constructor is not
called there.  But imagine code like :

   interval<double> sum[10000];
   for (int i=0; i<10000; ++i)
     sum[i] = a[i] + b[i];

For this kind of code, a default constructor doing something will have
a visible cost.  And I think this kind of code is common, so we wish
to have it really optimized.


>>I'm not very convinced by the arguments which have been given so
>>far in favor of "whole", because I think they mix the correctness
>>issue of forgotten initializations, with the preferred value of
>>the initializations of variables in *some* algorithms.
>>Such algorithms should initialize variables explicitly to "whole",
>>IMO.  
> 
> No, we agree that it is bad programming practice to rely on default
> initializations, no matter what they are.  I am talking about the extent to
> which we can protect the careless programmer who forgets to initialize the
> variable before using it.

I think the optional debug-mode solution allowed by #6 is the best
choice to solve this problem.  This is what many C++ implementations
do nowadays for detecting misuses of singular iterators, so I see it
as a good option.

>>And given that there is no clear intuitive default, users
>>will never remember that "whole" is used as default value, so
>>in practice it will be better to use "whole" explicitly anyway
>>for these cases, so no need to make it the default constructed
>>value.  If somebody thinks it would be too inconvenient to require
>>an explicit initialization to "whole" for some codes, I would be
>>interesting in seeing such codes.
> 
> Does the same argument apply for empty?
> I think whole and empty are equivalent in that argument.

I agree.

> Here are two careless programs:
> 
> Example 1.
> Interval X I think is 1, but it is built with a default constructor that
> defaults to empty.
> Y = [-1]
> Z = HULL (X, Y) 
> I think Z encloses all values of sin, but it does not because it is [-1]
> I assert that is a containment failure.
> 
> Example 2.
> Interval X I think is 1, but it is built with a default constructor that
> defaults to whole.
> Y = [2, 4]
> Z = [-3] + set difference Y \ X.
> I think Z encloses all values of sin, but it does not because it is empty
> I assert that is a containment failure.
> 
> Conclusion: NEITHER empty nor whole are immune to containment failure.
> 
> I think whole and empty are equivalent in that argument.
> 
> Conclusion 2: My case against #6 is pretty weak.
> 
> My case favoring whole over empty is not very good, either.

I agree that we do not really protect the innocent significantly more
using whole/empty.  It may even be dangerous to believe something
along these lines.


>>My personal preference goes to 6 (i.e. producing an "uninitialized
>>interval", similar to the behavior of iterators, that is, only
>>copies/assignments are allowed on them, basically).
> 
> Assuming I have understood what you mean by #6, I am forced to agree.

Good.  I hope we can reach consensus on this question, then.

-- 
Sylvain


More information about the Std-interval mailing list