[std-interval] Revised document available

[Dr John Pryce]

Guillaume and all

A.
At 07:14 19/09/06, Guillaume Melquiond wrote:
> > 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:
>
>No, I think you are putting too much meaning in the wording of 26.6#3.

I disagree.

Let me use I_T, as in our cset proposal, to mean the set of 
mathematical intervals represented by interval<T> objects. (The 
underscore has the TeX sense of "subscript".) The words of 26.6#3 
(edited to make sense in plain text) are quite unambiguous:

   If it is non-empty, it is specified by two values of type T, denoted by
   [xlo,xhi], which can be finite or infinite, and xlo is never greater than
   xhi. In this case, the set of real values represented is defined by
   {x in Reals | xlo <= x <= xhi}.

They imply that every nonempty member of I_T has endpoints that are 
type T machine-numbers (possibly infinite). There is no other 
possible meaning of this wording.

BTW one might expect that every mathematical interval, whose 
endpoints are type T machine-numbers, is in I_T. But this wording 
does NOT imply that.

B.
>This paragraph refers to the values returned by the lower and upper
>methods and is fine in itself.

Again I disagree. The words say what they say. And were you to change 
them to say what your above sentence says, the definition of the 
basic concept of
    "what mathematical object an interval<T> object represents"
becomes circular, since it defines the bounds in terms of the results 
of lower/upper, which themselves are defined in terms of the bounds.

> > (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.
>
>Looking at the proposal, the only part that forbids the midpoint-radius
>representation is the interval(T,T) constructor. Is this what you are
>referring to?

No. The basic definition forbids it. Suppose m is 2 and r is type T 
machine precision, EPS. Then 2-EPS and 2+EPS are not type T machine 
numbers. So the words of the text forbid [2-EPS, 2+EPS] to be a member of I_T.

> > (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.
>
>What do you mean "explicitly"?

The first sentence of 26.6#3 uses the word "closed". The following 
text, which I quoted above, uses the inequality <= rather than < . In 
my book, that is an "explicit" statement that non-closed intervals 
cannot belong to I_T.

C.
>Do you want to add an interval(T, T, bool, bool) constructor that 
>sets the opened/closed status of the bounds? Or do you just want 
>26.6#3 to be reworded? Which wording do you suggest?

Here I am concerned about MEANING, and am happy to leave 
implementation details to later. Yes, I believe 26.6#3 needs rewording.

For the record, here is the corresponding text of the June 06 version 
of the ISL cset-based proposal. (We hadn't seen the possible benefits 
of non-closed intervals then.) The set I is the set of all intervals 
in the abstract mathematical model.

>This standard supports just one abstract model:
>- The whole line is the extended reals R* = R union {-oo, +oo}.
>- The set I comprises all nonempty closed intervals in R*, that is [a, b]
>   for arbitrary a, b in R* with a <= b, together with the empty set.
>   This includes the whole line, since it equals [-oo, +oo].
>[ ... stuff about abstract definition of operations, omitted ]
>For each supported type T, the implementation-dependent set I_T, of 
>intervals supported by the interval<T> instantiation, must be a 
>subset of I that includes the empty set and the whole line. I_T must 
>be defined in the implementation's user documentation.

Thus, we are completely silent about data representation. I 
personally would favour something close to this. If we stick with 
closed intervals for the moment, reworded text could be on these lines:

>A nonempty closed interval in R is a set of the form
>       {x in R | a <= x <= b}
>where the endpoints a, b are R union {-oo, +oo} with a <= b. This 
>set is denoted [a,b] if a and b are finite. If an endpoint is 
>infinite, the corresponding square bracket is replaced by a round 
>bracket to show that the endpoint is not a member of the interval.
>The whole line is a closed interval, since it equals (-oo, +oo).
>
>This standard supports one abstract model:
>- The whole line is the reals R.
>- The set I comprises all nonempty closed intervals in R, together with the
>   empty set.
>[ ...one should give an abstract definition of operations here. ]
>For each supported type T, the implementation-dependent set I_T, of 
>intervals supported by the interval<T> instantiation, must be a 
>subset of I that includes the empty set and the whole line. I_T must 
>be defined in the implementation's user documentation.

This wording leaves data representation opaque. It only needs small 
changes to accommodate non-closed intervals should this be desirable.

D.
Return to your question:
>Do you want to add an interval(T, T, bool, bool) constructor that 
>sets the opened/closed status of the bounds?

For general intervals, I suppose yes.

But it may be that the only open endpoints we wish to support are at 
zero. That is, the abstract set I comprises the previous set I 
together with all intervals
   {x in R | a <= x < 0}  and  {x in R | 0 < x <= b}

Then on IEEE machines we don't need an extra constructor. We could 
use signed zeros:
   interval(-2,-0) constructs [-2,0);  interval(+0,2) constructs (0,2];
   interval(-2,+0) constructs [-2,0];  interval(-0,2) constructs [0,2];
and so on.

Note this does NOT mean signed zeros exist in the abstract model. 
They are just a useful encoding offered by the IEEE data representation.

Best wishes

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