[std-interval] Mathematical relations and default initialization

[Dr John Pryce]

Sylvain, George and all

Re:
>1- no default constructor at all
>2- [0,0]
>3- empty
>4- whole
>5- uninitialized tag
>6- see below (something a la "singular iterator")

At 10:08 15/09/06, Sylvain Pion wrote:
>George Corliss wrote:
>>... 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 [allows] the behavior you mention, but also many others...
>
>The specification for #6 could look like the following.
>" 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. "

Now you spell out the semantics so clearly, I begin to like #6. If it 
is policy that every interval operation HAS TO return an interval 
(and I don't mean just an object of interval type, I mean a member of 
the abstract interval model, i.e. a set) then I still favour "whole" 
over "empty" - George, I comment below on your examples.

But I sense a general view that this is NOT good policy. There are 
operation-instances where it is certain or extremely probable that 
the programmer has overlooked something, and there is no sensible way 
to continue the computation. "x = interval<double>(NaN,3);" for 
instance. I have argued for throwing an exception in such a case. But 
I accept the force of the argument that this also is bad policy in 
the case of large parallel computations. Assume we have made the 
constructor work elementwise for arrays, and we have
     x = interval<double>(xlo,xhi);
where x,xlo,xhi are arrays of a million elements. If just one element 
of x failed to be constructed because of a NaN in xlo or xhi, we 
would like to continue working with the "good" 999999 while STILL 
BEING ABLE to detect that the computation with the one bad value 
produces garbage output.

Sylvain, your specification of #6 looks very like one for "Not an 
Interval", NaI: just as NaN is a floating-point object that does not 
represent a value in the abstract model of (extended-)real numbers, 
so NaI is an interval object that does not represent a value in the 
abstract model of (extended-)real intervals. Is that a fair description?

>>>(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 guess that the typical efficient 
>representation of empty (with NaNs) will propagate at no additional cost...
>On the other hand, I'm not sure it's very useful to
>specify propagation of empty ...
>Not specifying tightness at all is easy, but it is also risky: it allows
>a dumb ("return whole") implementation, be standard compliant.

Is it "risky"? There are enough good interval systems out there for 
market forces to weed out the shoddy ones or force them to improve. 
Or am I naive?

George argues forcefully against specifying behaviours that should be 
QOI issues. Against this, I favour the argument that the more precise 
the standard, the more one can prove about the behaviour of code, and 
this can be a massive help to algorithm writers. Simple example: the 
Ada model of floating point arithmetic operations "op" is basically 
no more than
       (computed a op b) = (1+eps)*(true a op b) for inputs a, b
in the absence of under/overflow. With the far more precise IEEE 
model it is a (very useful) theorem that if
       0.5 <= a/b <= 2
then a-b is computed without roundoff - which one cannot deduce from 
the Ada model.

So, until I am convinced otherwise, my view is that, to increase the 
range of PROVABLE BEHAVIOUR of interval code
    When good behaviour is painless to implement, or nearly so, then it
    should be enforced by the standard.

"Painlessness" depends on the opinion of the implementer and on the 
language, compiler and hardware. But I see this as a useful guide. I 
would apply it to the following 2 examples, for instance:
  - Whenever the exact result of an elementary operation is empty,
    then empty should be returned.
  - Whenever an interval<T> x = [a,b] is converted to an interval<U> y,
    whether of higher or lower precision, if interval<U> is capable of
    representing [a,b] exactly, then the conversion SHOULD be exact.

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

I also find that tempting, because it seems easily achievable on IEEE 
machines with the lower/upper bound representation, but it would rule 
out the present version of INTLIB, I believe. It may also be 
problematic for midpoint-radius representation. I believe this has 
few if any advantages for real (as opposed to complex) interval 
arithmetic, but I believe a standard should not prohibit it.



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

I agree, I think, that in such cases it is better to return "no value 
at all" than empty or even whole, since by Murphy's Law one cannot 
"protect the careless programmer" from all possible carelessnesses.

George wrote:
>>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 do not accept Example 2. Our basic philosophical premiss about 
interval objects is that they are SUPERSETS of some true value or set 
of values, and therefore one never makes a true statement into a 
false one by making ALL intervals bigger. This requires all allowed 
operations to be inclusion-isotonic - which is TRUE of interval 
versions of elementary functions; of interval hull; of set union & 
intersection. But FALSE of the second argument of set difference, X 
in Example 2.

In that sense X is a different class of object from "interval". In 
order for Example 2 to make sense, X must have the nature of a SUBSET 
of a set of true values. Its set-complement has the "superset" 
nature. If one implemented a class for objects like X, it would make 
sense for its constructor to default to EMPTY.

Regards

John Pryce
Dr John and Mrs Kate Pryce
142 Kingshill Rd
Swindon, Wiltshire SN1 4LW
UK
Tel (+44)1793-331062