[std-interval] Mathematical relations and default
initialization
Dr John Pryce
j.d.pryce at ntlworld.com
Sat Sep 16 23:14:31 PDT 2006
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
More information about the Std-interval
mailing list