# [std-interval] Revised document available

Dr John Pryce j.d.pryce at ntlworld.com
Thu Sep 21 13:46:43 PDT 2006

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