[std-interval] C++ interval std

[George Corliss]

Sylvain Pion wrote:
>> Steve and Lawrence are both members of the C++ Committee (J16),
>> representing Sun. Steve is the chair of J16.  It was Lawrence
>> who wrote the comment to the this group in early March about
>> passing by value.
> 
> Note that I am attending the ISO C++ meeting this week in Berlin,
> so I will have the opportunity to present the status (briefly, as
> I don't think we are ready to show a concrete update adressing all
> the comments), and discuss with Lawrence and Steve.
Understood.  I hope that as soon as you have an updated draft of the
proposal, you'll let us all know.

>> Sun has an open source release of its interval elementary functions,
>> so the barrier to entry is low.  That means we CAN require math.h
>> functions be provided in an interval standard.
> 
> There are also other open source implementations available.
> However, at the presentation in Mont-Tremblant, the committee was
> a bit reluctant to add more "complicated numeric functions" to
> the standard, because there was other proposals with such a common
> theme.  So the question might boild down to whether we prefer to
> have nothing or an incomplete library.
> 
> I however agree that this would make the proposal attractive to more
> users, and that the more complete implementation based on existing
> codes is probably not that hard.
Since there are AT LEAST two implementations of elementary functions
available, I favor asking that they be included in the standard, unless the
committee balks.

>> Infinities, etc.  Define mathematically what you must contain, and
>> permit as much implementation creativity as you can.
>> 
>> At this point, correctness is MUCH more important than speed.  When
>> people start demanding intervals be fast, we'll know we've won.
>> Having tests in each operation is not a problem.
> 
> Well, if we're arguing that passsing-by-value is fundamentally important
> for speed, and that adding a few more tests is not because speed is less
> important... ;)
> 
> It's important to get the semantics that most people want first,
> I agree.
Pass by value vs. pass by reference is an issue of speed and flexibility, as
I understand it.  There is no question of tightness.

Several of the possible choices about infinities, for example, give
enclosures in a wider set of cases, at the expense of additional tests.
There, I argue that we MUST get enclosures (I hear no opposition to that),
we SHOULD get them in as wide a set of circumstances as possible
(alternative being some form of "I can't," such as an exception or some form
of NaN), and we should get as tight as we can (but that's a Quality of
Implementation issue.

>> Uninitialized.  The convention in C/C++ is to initialize to zero,
>> but we agree that is not correct for intervals.  Whole is probably
>> the best we can do.
> 
> I'm not convinced.  Initilization to [0,0] seems nice to me for
> intervals because of homogeneity reasons with floating-point.
> I could even imagine that the empty interval would make as much
> sense as whole.
> 
> What makes you think that [0,0] is "not correct", and why 'whole'
> would be better than 'empty' ?
I agree that initialization of uninitialized intervals to [0,0] is easy, and
it is consistent with floating-point practice.  My reservation is that it
can lead to violations of containment.

The issue is not with "our" code.  It is with users' code.  Floating-point
arithmetic makes no promises of accuracy.  Intervals promise a guaranteed
enclosure.  If a user mis-uses our tools and gets a violation of
containment, WE will be blamed, not the programmer who forgot to initialize
all variables.  I want to make it as difficult as possible for even
incorrect code to lie.

Simple example:
   interval Pi;
   cout << "Pi is enclosed by " << Pi;

The result violates containment if the default initializer is either [0, 0]
or Empty.  It is truthful if the initializer is Whole.

Of course, no one would do that on purpose, but programmers DO sometimes use
variables they have not initialized.

One easy-to-imagine case might define a variable by a complicated set of
nested cases/ifs.  The programmer thinks all possible cases are covered, but
misses one case.  In that case, the variable is not given a value, but the
following code uses it, unaware that it might not have been assigned a valid
value.

Asserting that a set is empty is perhaps the strongest assertion one can
make about a set.  Asserting that it is contained in the universal set is
the weakest assertion one can make.  That is why I argue for Whole.

I'd like to have some special "undefined" value that would propagate like a
NaN, but that is too much to ask for.  Whole does not lie.

A Tag (see below) could be used for exactly that purpose.

>>  Aside: The next day, we visited Berkeley and
>> talked with Jim Demmel and Bill Kahan.  Among other things, Kahan
>> wants user-defined data types to be tagged.  If we have the
>> Kahan-suggested tag, we can tag intervals as Uninitialized.
> 
> Could you elaborate on this tag ?  What would it do ?
> Would this be a run-time feature of the objects telling if
> they are initialized or not ?  Can't this be left to some
> "debug mode" ?
Let me explain Kahan's reasoning, as well as I am able.

The request is that a tag be permitted by the standard.  As I understand it,
what would be required is to remove the phrase that an interval is
represented by two values.  The down side, of course, is that it is harder
to know how much memory an interval may require.

If we are permitted a tag, the tag can be used in MANY different ways within
an implementation.  The tag could be an attribute, or it could be a pointer
to a complicated internal data structure of properties of the interval.  The
most extreme case I can think of is that the tag might point to the Abstract
Syntax Tree that generated the interval, allowing run-time symbolic
processing.

In most implementations I can imagine, the tag could be used for
"uninitialized," "exterior interval," various flavors of NaN, precision in a
multiple precision implementation, and the like.  If we want a (center,
radius) implementation, a tag could distinguish semi-infinite intervals, or
it could distinguish [lo, hi] from (center, radius) intervals.

The proposed standard is 1-D, where boxes and ellipses are the same (finite)
sets, but if we want to build higher-dimensional Interval, we might consider
subclasses Box and Ellipse, although polymorphism handles that without
explicit tags.  Hmmmm.  That suggests that C++ run-time types form a sort of
tag.

>> The 1999 C standard provides for access to IEEE hardware.  The
>> next version of the C++ standard will also address features new
>> in the 1999 C standard to be included in C++.
>> 
>> The current C++ standard does not discuss or acknowledge threads.
>> They are working on the next revision of the standard, which will
>> have something to say about threads in the language proper and in
>> the standard library.  Probably the interval standard should say,
>> "Intervals will be implemented in a thread-safe manner."
> 
> I guess this will have to be true for the whole standard library,
> or almost all, so I don't think we should worry specifically about
> this at the interval level, other than stating this requirement.
Agreed.

>> IEEE 754R
>> David Hough <David.Hough at Sun.com>
>> 
>> IEEE 754R is nearly over.  It is likely to include
>>    Decimal formats for floating point
>>        (Should C++ IA standard permit decimal intervals?)
> 
> We have explicitly asked this question (at the Mont-Tremblant meeting)
> to the IBM representant supporting the decimal floating-point proposal.
> He agreed that, at least currently, there is no need for this
> compatibility as the corresponding user communities targeted are
> a priori separate.
As I read it, there is nothing to prevent someone from offering additional
base types, including decimal or multiple precision?  Technically, they
would not be standard-conforming, but they could conform to the spirit.

>>    Fused Multiply and Add
>>        (I assume with directed rounding?
>>         Great for interval linear algebra, too)
> 
> I guess it also depends if there appears a function for doing fma
> on floating-point types in C++, in which case a natural overload
> for intervals would be nice and natural.
The benefit to intervals is clearer at the vector level, which the proposed
standard does not consider.  My observation is that a dot product is easier,
tighter, or faster with a directed rounding FMA.

>>    min/max
>>        (I wonder how they handle NaN, infinity, etc.)
>>    expression evaluation
>>        (Don't remember what that means)
>> 
>> As far as David is concerned, ISVs (Independent Software Vendors)
>> drive the market.
> 
> More generally, since IEEE754R will most probably be released before
> C++0x, it would be nice if C++0x would take it into account.
Yes, probably.

Dr. George F. Corliss
Electrical and Computer Engineering
Marquette University
PO Box 1881 
1515 W. Wisconsin Ave.
Milwaukee WI 53201-1881 USA
414-288-6599; Fax: 288-5579; Dept. 288-6280
Office: Haggerty Engineering 296
George.Corliss at Marquette.edu