[std-interval] Mathematical relations and default initialization

[George Corliss]

Sylvain,

Very helpful explanations.  Yes, I am prepared to agree to #6.  Others?

Re: Propagation of empty.  I have tended to oppose tightness requirements,
preferring to call those QOI issues.  In an off-line discussion, John Pryce
has convinced me of the wisdom of requiring tightness in obvious cases where
there is no speed penalty, but we would only be requiring what any
reasonable implementer would do anyway.

It appears that the propagation of empty through most operators fits that
pattern on machines that support NaN.  Hence, I agree that it makes sense to
specify that empty propagate, at least in operators where the speed impact
is low.

John's argument for specifying tightness when it is easy to achieve was
based on proving assertions about programs, and one would certainly like to
be able to prove assertions about empty sets.

Dr. George Corliss
Electrical and Computer Engineering
Marquette University
P.O. Box 1881
1515 W. Wisconsin Ave.
Milwaukee, WI 53201-1881
George.Corliss at Marquette.edu
414-288-6599 (office); 288-4400 (GasDay);
    288-6280 (Dept.); 288-5579 (fax)
Office: Haggerty Engineering 296
Www.eng.mu.edu/corlissg



On 9/15/06 4:08 AM, "Sylvain Pion" <Sylvain.Pion at sophia.inria.fr> wrote:

> 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.