Re-revised interval flavors motion (36.02)
P1788
I am sorry for the delay, but off-group discussions have shown the need to
make the wording of Motion 36 more precise. I submit version 3, with
substantially revised motion text and rationale. I now specify the motion
applies to Level 1 only. Discussion of Level 2 remains in the rationale, as
a basis for a future motion.
As I see it, the point raised by Vincent Lefevre is this.
Consider evaluating some operation "op" at specific inputs X1,X2,... which
are in the set C of common intervals:
op(X1,X2,...).
Suppose two flavors give two results R1 and R2 that are both common
intervals, i.e. both in C, and *different*. Is this allowed?
This won't happen often, but must be handled properly. For an example I
take
R = sign([0,3])
where the point function sign(x) equals -1 for x<0, 0 for x=0, 1 for x>0.
- Modal/Kaucher flavor M doesn't give this a value (I believe). That is,
its result is "undefined".
- Set-based flavor S gives a result in C:
R1 = [0,1].
- Suppose someone implements a containment-set (cset) flavor. Because
it's based on taking limits as one approaches points in the input-
interval from either side, it gives a different result in C:
R2 = [-1,1].
Define an operation-instance (opinst) of "op" to be a tuple of intervals
(X1,X2,...;R) such that R = op(X1,X2,...). That is, an opinst is a point in
the graph of ("op" regarded as an interval mapping). Then for the given
input box (X1,X2,...)
- There is no R s.t. (X1,X2,...;R) is in the "common" set of
opinsts, else all flavors would have to agree on the result R.
- (X1,X2,...;R1) is an opinst for the S flavor.
- (X1,X2,...;R2) is an opinst for the cset flavor.
We may not like R1 and R2 being different. We may think this could confuse
the user. But I see no justification for preferring one value to the other.
I think it is essential to say "all flavors are created equal", provided
each is based on a self-consistent Level 1 theory. We can't say, for
instance, "my flavor was defined first, so it takes precedence over yours".
I think users' confusion will be minimised, if the flavor of a section of
code is fixed at the level of a compilation unit, e.g. by a compiler switch
on the command line or by a directive in the source code. But that is not
the subject of this motion.
My conclusion is that to make flavors work, 1788 should specify a common
set of intervals, and a common set of opinsts, and require all flavors to
agree on these. But not make requirements beyond this.
I think a fairly natural choice arises for these two common sets. So I've
put these in the motion, which makes it more specific than before. I hope
the revised rationale makes a good case for the choice.
Chair, I hope this can be taken as a friendly amendment to the previous
version.
Thanks to Vincent. At the time of writing we still disagree on the problem
of "different R1 and R2". I hope wider debate will show the best solution.
Another thing that needs debate is what using flavors would look like in a
user program. If you are a user who knows nothing of flavors, or expects
your particular run of your program to be flavor-independent, how should
you be informed if the flavor makes a difference? If you are more
sophisticated, what is good practice for doing different parts of a
calculation in different flavors? Or for coding "if running flavor F, do
this, else do that"?
Best wishes
John Pryce
Motion 36, version 03.
======Terminology======
In this motion, "set-based" interval means the kind of interval specified
by Motion 3, and "modal" interval includes the modal and the Kaucher kind
of interval, and any related kind that the modal subgroup may wish to
specify.
======Motion======
1. The standard shall permit different kinds of interval, called "flavors",
each having its own part of the standard text as well as a common part.
This motion is only about the Level 1 aspect of flavors.
2. There shall be a set of "common intervals" shared by all flavors, namely
the closed, bounded, nonempty real intervals (also called "classical
intervals").
There shall be a common set of named operations, and for each such
operation a set of "common operation instances". For arithmetic operations,
these shall comprise all cases where the corresponding point function is
defined and continuous everywhere on the input box, the interval result
being defined to be the exact range of the function over this box.
The meaning of "shared" in the previous paragraphs is defined precisely in
the Rationale. Informally, common intervals behave as a subset of each
flavor, on which the common operation instances behave identically in all
flavors.
3. There shall be a set-based flavor, whose specification has been the
subject of previous Motions -- notably 3, 5.02, 8.02, 9, 10.02, 12, 13.04,
18, 21.2, 30.02, 33, which are most relevant to Level 1.
The main Editorial Team, currently John Pryce and Christian Keil, shall be
responsible for the set-based part of the standard text.
4. The P1788 group asks the Modal Subgroup to appoint from its members a
Modal Editorial Team, which shall be responsible for specifying a modal
flavor, and writing a corresponding modal part of the standard text.
5. Beside set-based and modal, other flavors that extend classical
intervals may be specified in future, for instance Kahan wraparound
intervals, or intervals that are open at one or both endpoints.
6. In addition to item 3, the main Editorial Team shall be responsible for
overall style and presentation and, in discussion with relevant editors,
integrating the text of all flavors into the final standard document.
7. Conformance. An implementation shall support at least one flavor. It
shall document which flavors it supports.
If it supports more than one flavor it shall make it possible for a program
to select a flavor in a language-defined way, along the lines of "constant
attributes" in IEEE 754-2008 clause 4. A program shall have the ability to
determine which flavor is in effect at any point of its execution.
8. Aspects of flavors beyond this, including how flavors interact with
Level 2 and with the decoration system, shall be decided by future motions.
Rationale
=================================================
This rationale text is based on the email Michel Hack and I circulated on
23rd May 2012, but substantially revised.
Principle
---------
What matters is behavior, both at Level 1 and Level 2. It doesn't matter
that a set-based interval is a set of reals and a modal or Kaucher interval
is something else, provided that when applied to the "same" inputs they
give the "same" result.
The meanings of "same", and of "shared" in the motion text, are specified
below, especially by the notion of embedding map (1) and operation
compatibility (2). For instance a modal interval X* and a set-based
interval X** are the "same" if X* = m(X) and X** = s(X) for some common
interval X.
Terminology & notation
----------------------
thing = a Level 1 bare or decorated interval,
datum = a Level 2 bare or decorated interval,
The word "agreed" marks a design decision the group must make to let the
set-based and modal flavors interoperate.
Think of X1, X2, etc. as being subscripted X_1, X_2, etc.
Level 1
-------
Set-based intervals and modal intervals both arose from arithmetic on the
"classical" set of closed bounded nonempty real intervals. The motion
requires that at Level 1 there be
- a set C of common (in the sense of "shared") things,
- a set S of things belonging to the set-based flavor,
- a set M of things belonging to the modal flavor.
A general flavor has a set F of things, together with a one-to-one
embedding map
(1) f : C -> F
by which C can be regarded as a subset f(C) of F. A flavor F with its map f
will be denoted (F,f). In particular, there are embedding maps
s : C -> S and m : C -> M
for the set-based and modal flavors.
An operation-instance (opinst) for a k-ary operation "op" means a (k+1)-
tuple of intervals (X1,X2,...Xk;R) such that R = op(X1,X2,...Xk). That is,
an opinst is a point in the graph of "op", when "op" is regarded as an
interval mapping.
A C-opinst means one where all the inputs X1,...Xk and the result R are in
C.
We need "Operation Compatibility" for C-opinsts:
op(fX1,fX2,...fXk) = f(op(X1,X2,...Xk).
(f(X) is abbreviated to fX when context makes clear.) That is, an operation
gives "the same" result, whether you perform it in C and then map to F, or
map to F first and perform it in F.
However, it is essential to specify for just which C-opinsts this is to
happen, because of the point Vincent Lefevre raised. Two cases need
considering:
Case (a)
op(X1,X2,...Xk) gives a result in C with one flavor, but is
undefined in another flavor.
Example: sqrt([-1,4]) is undefined in M, but is defined in S
with value [0,2] in C.
Case (b).
op(X1,X2,...Xk) gives different results R1 and R2, both in C, in
different flavors.
Example: sign([0,4]) is undefined in M, but is defined in S
with value [0,1] in C, and would be defined in a "cset" flavor
with the different value [-1,1], also in C.
Therefore, a set CO(op) of "common" C-opinsts is specified for each
operation "op", such that for each (X1,X2,...Xk;R) in CO(op) we have
op(X1,X2,...Xk) equals R in *all* flavors.
Formally, this means that for each "op", for each flavor (F,f) and for each
(X1,X2,...Xk;R) in CO(op) we have
(2) op(fX1,fX2,...,fXk) is defined in F and equals fR.
Clearly, CO(op) must define a one-valued function, so if (X1,X2,...Xk;R1)
and (X1,X2,...Xk;R2) are both in CO(op), then R1=R2.
A flavor is permitted to extend operations on C beyond this. That is, there
may exist (X1,X2,...Xk;R) *not* belonging to CO(op), such that (+) holds.
See Cases (a) and (b) above.
Reasons for choice of C and CO(oP)
----------------------------------
There seems no point in having this motion unless C includes the
"classical" set of closed bounded nonempty real intervals. I choose C to be
exactly this set, because any larger set might make it harder to add other
flavors in the future.
For a modal-flavor interval version of a point function "op" to be defined
on an input box whose components are in C, it is sufficient and (I believe)
necessary that "op" be continuous on the box. The set-based flavor has no
restrictions here. This makes it natural to choose CO(op), for any "op", to
be all C-opinsts (X1,X2,...Xk;R) such that "op" is everywhere defined and
continuous on the box (X1,X2,...Xk), and R is the exact range of "op" on
this box, which is necessarily a closed bounded nonempty interval.
To be precise, that a function g is defined and continuous on a subset X of its domain is taken to mean
(a) g is defined and continuous at each point of X,
not
(b) the restriction of g to X is defined and continuous on X.
For modal intervals, I think either would do. I chose (a) to support a
possible cset flavor in future -- e.g., it implies ([0,0]; [0,0]) is NOT a
common opinst for the sign() function, thus allowing the cset value sign
([0,0]) = [-1,1] to be different from the set-based value. However I am not
wedded to csets, and could be persuaded to choose (b) instead.
Relation to §5.6 and §5.7 of the standard text
----------------------------------------------
The above shall apply to all arithmetic operations in the Required
Operations (§5.6.2), and to those arithmetic operations in the Recommended
Operations (§5.7) that an implementation provides.
As for other subclauses of 5.6:
- 5.6.1 (Constants) is not relevant.
- 5.6.3 (Interval case expression). At first sight I don't see how
this makes sense for modal intervals, so I propose omitting it
from the common set.
- 5.6.4 (Reverse-mode functions). I don't know what the modal
definition of these should be, but it seems perfectly possible
there is one, so I await advice from the modal group.
- 5.6.5 (Inner add & subtract). The common set should be those where
the S flavor gives a defined result at Level 1. (M gives a defined
result, possibly improper, in all cases.)
- 5.6.6 (Non-arithmetic operations). The common set should be
- convexHull(X,Y) for arbitrary X, Y in C.
- intersection(X,Y) for all X,Y in C that are not disjoint.
These cases give the same result in C for both flavors S and M;
whereas the intersection of disjoint X,Y in M gives an improper
interval, and in S gives the empty set.
- 5.6.7 (Constructors), 5.6.8 (Numeric functions of intervals),
5.6.9 (Boolean functions of intervals), 5.6.10 (Dot product).
These should be the subject of a future motion.
I don't see them giving insuperable problems.
Decorations and flavors
-----------------------
This should be the subject of a future motion. I believe flavors will
remove much of the disagreement between different camps, allowing different
"flavors of decoration", again with an essential common part.
To this end, the decoration system must be able to signal "not a common
opinst". This would occur when doing, say, intersection([0,1],[2,3]) which
gives Empty in S and [2,1] in M. Coupled with the ability to enquire at run
time what flavor is in effect (motion item 7), this would allow code to
give correct results -- or fail gracefully -- in any flavor.
Note this raises at Level 2 the old issue of overflow. Does [0,REALMAX]
+[0,REALMAX]=[0,Inf] count as a common opinst? (The result is a member of
C, but one can't represent it as such.) Some work to do here.
Level 2
-------
The motion now doesn't cover this, but I include the text from version 2
with little change.
Here there are
- a set C of common datums,
- a set S of set-based datums,
- a set M of modal datums.
There is the extra complication of *types*. My proposal requires there be
an "agreed" type-portfolio TP of named types T, and the embedding map (1)
and compatibility equation (2) hold for the datums of each T in TP. I hope
it's obvious what I mean, without more definitions.
Level 2 also has *implementations*. Regard an implementation as a library
that supports various interval types, the operations on them, and inter-
type conversions, and may split into a set-based and a modal sub-library. A
given implementation need not provide every type in TP, and may provide
types not in TP.
Queries: Should there be an "agreed" minimum subset of TP that each
implementation shall support (say, at least the binary64 inf-sup type)?
[Vincent Lefevre, 5 July, wrote:
> I don't think so, except for 754-conforming implementations.
]
Should an implementation that provides both a set-based and a modal sub-
library provide the same subset of TP in each? These are some of the issues
to be decided.
I suggest (2) should hold *exactly* at Level 2 for each operation to which
we give the "tightest" attribute; and for constructors; and for boolean
operations. Probably also for numeric functions of intervals -- this
requires there be an "agreed" set of numeric formats. Equality within a
roundoff tolerance may be accepted for other operations: these are issues
to be decided.
In version 2 I had
"The result I'm aiming for is that
(*) A Level 2 program that only ever performs internal
operations runs identically whether it is linked with the
"modal" or the "set-based" library."
This can now be hardened up to
(*) A Level 2 program that only ever evaluates common opinsts runs
identically in all flavors,
(up to roundoff errors, in case it performs some operations that aren't in
"tightest" mode).
Difficulties
------------
In version 2 I wrote (except I wrongly wrote cancelminus instead of
innerMinus):
What of operations that behave differently in the "set-based" and "modal"
flavors, even when applied to common intervals?
If infrequently used, such as intersect() and innerMinus(), they should
IMO exist in two named versions, say innerMinusS and innerMinusM, etc.
Then, if you are running an algorithm that relies on
[1,2] innerMinus [10,20]
producing a modal (improper) interval, you *must* use innerMinusM. If you
then try to link with the "set-based" library the system will report your
error, because it has no innerMinusM operation.
In fact, a "not a common opinst" decoration makes two named versions
unnecessary. But I still think it may be a good idea for infrequently used
operations. It's not practical for, say, division. Opinions please.
Impact on the standard text
---------------------------
I am now convinced this proposal doesn't change the level structure. I
think to make the standard as readable as possible, there should be
separate documents for each flavor, with a few identical common sections
(produced by \include or \input in LaTeX) clearly marked as common by the
way they are typeset.