[std-interval] Revised document available

[Dr John Pryce]

Dear std-intervalers,

At 09:16 12/09/06, Sylvain Pion wrote:
>A revised version of the proposal is now available at:
>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2067.pdf

My first comments on the revised proposal were 
about the use of "undefined". In this message, as 
a second theme, I will comment on the status of 
infinity (which I write oo) in the proposal.

A.
Sylvain and colleagues: your text (by this I mean 
the draft standard text, excluding the preamble) 
has at least one clause (p17 #16) that explicitly 
prohibits a cset-based model. In particular your 
present text prohibits Sun interval arithmetic, 
and FILIB++ extended arithmetic.

I have no complaint about this in itself - the 
ISL proposal explicitly allows ONLY a cset-based 
model. We should have liked to be more 
accommodating, but a draft that had both in one 
document got so messy that we could not be sure it was logically consistent.

Therefore I am moving to favour two standards, 
identically structured as far as possible, 
defining a non cset-based and a cset-based model 
respectively. What do people think?

B.
I do not feel the text makes it clear whether the 
platform's arithmetic MUST support oo - which 
more or less amounts to using IEEE arithmetic. On p4 we read
   The value of whole() requires that T has an infinity
   (in std::numeric_limits<T>).
and the definition of "whole()" has
   Requires: std::numeric_limits<T>::has_infinity.

For the record the draft C++ standard says the 
following (I believe "Required behavior:" and 
"Requires:" paragraphs are the same thing).
>17.3#3
>Descriptions of function semantics contain ...
>— Requires: the preconditions for calling the function.
>
>17.4.3.8 Required paragraph [lib.res.on.required]
>1 Violation of the preconditions specified in a 
>function’s "Required behavior:" paragraph 
>results in undefined behavior unless the 
>function’s "Throws:" paragraph specifies 
>throwing an exception when the precondition is violated.

Usually a "Requires:" gives preconditions on the 
ARGUMENTS to a function (and the only other 
"Requires:" in your text does just that). But 
this one is a precondition on the PLATFORM. So it has the effect
   This function MUST be provided on any platform, but on a platform that
   does not support oo this function must never be called!

Actually one can easily (at the cost of some 
performance penalty) encode "whole" and other 
infinite intervals on an arithmetic without oo, 
using reverse-ordered bounds, as recent postings to this group have hinted.

C.
More on ambiguous support for oo. The definition 
of an interval<T> object 26.6#3 uses the phrase 
"is specified by two values of type T ...". Implications of this wording are:

(a) If T does not support oo then infinite intervals are forbidden: one is
   not permitted to encode them by some other method.

(b) A midpoint-radius (m-r) representation is forbidden: not explicitly, but
   de facto. I don't think m-r is a good system on the real line (recall Rump's
   INTLAB uses it in the complex plane) but I use it as a test. I don't think
   a standard should rule out m-r, and believe one that does so is too
   implementation-oriented.

The reason m-r is excluded is that it defines an interval by two type T numbers
   m, r such that the exact mathematical interval is [m-r, m+r]. In general
   these endpoints are not exact type T numbers, 
but the text says they must be.

(c) Implementations that support non-closed intervals are explicitly forbidden.
   This is indirectly related to handling oo, and 
I will return to it in a later
   message.

   Actually George pointed out this is not 
entirely true. By playing around with
   the class hierarchy one can add other kinds of interval to those this
   standard restricts one to. But it would be nice to permit them explicitly.

The ramifications of (a) are such that unless you 
rewrite 26.6#3, you may as well say explicitly 
that this standard only applies to IEEE systems. On systems without oo:
- You have no way to handle overflow, including conversion, say, of
   interval<double>(x) to interval<float> where x is above float's
   largest representable number.
- You cannot represent 1/[0,1].
etc.

D.
You could change 26.6#3 to say "... specified by 
two values, denoted by [xlo,xhi], which are 
either finite of type T, or infinite, and xlo is never greater than xhi."
This permits special encoding of infinite 
intervals on systems without oo. However it still 
forbids m-r form, so I feel it also is too implementation-oriented.

In the ISL proposal, I tried to get round this by 
not saying anything to influence the 
representation method, but merely saying that 
every singleton interval<T>, x=[t,t] where t is 
of type T, had to be stored exactly. That is, you 
could recover t by doing inf(x), for example. 
This gives interval<T> a "minimum QOI" by tying 
it loosely to the precision of T, while allowing 
both bounds and m-r representation. Maybe someone 
will show this idea is seriously flawed but it 
was the best I could think of ...

E.
Suppose 26.6#3 is reworded on the above lines. 
Then we have a text that mandates (and makes 
possible) support of whole and other infinite 
intervals whether the arithmetic supports oo or 
not. I have no basic theoretical quarrel with it. However:

1. It still does not state the Abstract Interval 
Model (or preferably, the range of models) 
supported by the standard. This makes it harder 
to discuss alternatives and opportunities.

2. In particular - see 5.1 of the Pryce-Corliss 
paper I circulated - in the cset context one gets 
interesting opportunities from allowing (some, or 
all possible) intervals with non-closed 
endpoints. In particular allowing open ends at 0 
and oo cures Sylvain's [REALMIN,REALMAX]^4 example of nasty cset behaviour.

It may be worth exploring this for a non-cset 
system. For instance, allowing 1/[1,+oo) to be 
represented as (0,1] rather than [0,1].

I think a small change to 26.6#3 would make such 
intervals PERMISSIBLE without making them MANDATORY.

3. My main objection to the way this text treats 
oo is that since 1985 - see interesting account 
at http://www.cs.berkeley.edu/~wkahan/ieee754status/754story.html
- we have an arithmetic system, IEEE 754, in 
which oo is treated systematically and 
consistently as an actual number. (Except for the 
behaviour of signed zeros, IEEE implements the 
arithmetic of the extended reals R* that has been 
used by mathematicians since around 1890.) 
Moreover, IEEE 754 offers rounding modes 
deliberately designed to help interval 
arithmetic. And as far back as 1968, W.Kahan 
gives a lecture course on a practical interval 
arithmetic in which oo is an actual number.

Yet, 20 years later, we set out a standard for 
interval arithmetic in which oo is not a number: 
the existence of IEEE's -Inf and +Inf is just 
used as a convenient way to encode infinite 
intervals of the reals R, not of the extended 
reals R*. Yes, choosing such a standard is much 
better than no standard at all. But I cannot 
believe that 10 years hence, anyone will praise 
the wisdom of those who chose it rather than a 
standard that supports infinity systematically.

BTW some people feel that the IEEE designers 
"didn't really intend" Inf to be infinity, but 
just to mean some finite number too large to 
represent. But then, why is it that IEEE defines 
Inf times 0 to be NaN rather than 0?

4. One other consequence of choosing this 
standard is that, at the level of expressions 
rather than individual elementary operations, one 
loses the opportunities for optimization of 
interval code offered by the Rational 
Rearrangement Theorem of cset theory. It remains 
to be seen how powerful a tool this is compared 
with other methods for reducing "interval bloat", 
such as constraint propagation, and methods being 
studied by Lee Winter. But it should not be dismissed.

Regards

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