Motion P1788/M0036.03:Flavors (revised) -- expedited discussion period begins
P-1788,
John has submitted a revision of the motion, taking account the discussion to-date.
The revised motion, as submitted by John, is included along with substantial
rationale at the end of this message.
Juergen: Please post this revised motion on the web page.
Voting on this motion will begin after Sunday, August 19.
Sincerely,
Ralph Baker Kearfott (acting chair)
P.S. A special note: We have been working on the document for almost 4 years,
the normal term. We have applied for an extension. If we get
an extension from IEEE, we will have essentially one year to produce
the final document wording. Thus, we must maintain a sharp focus
on completing this task. This means that features orthogonal to the
basic standard, as well as controversial features not crucial to the
basic standard, are best left for another day
(after this standard is completed). The alternative is no standard
at all. Everyone: Please imagine how long it will take for each particular
desired feature to be approved, and weigh its importance to you against
the possibility it might derail the standard as a whole. In the mean time,
the officers will plan motions on the actual standard text in an effort
to have the entire text approved on schedule.
On 08/04/2012 04:46 PM, John Pryce wrote:
Vincent & P1788
Here is a version responding to Vincent's comments. Substantive changes marked by
*****
for visibility, with both old version (quoted) and new version given where it's a change rather than an addition.
.
.
.
John Pryce
===========================================================================
Motion 36, version 03. (Sub-version 2?)
======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.
*****add
Each flavor shall satisfy an appropriate version of the Fundamental Theorem
of Interval Arithmetic (FTIA), which shall reduce to the classical FTIA of
Moore when only common operation instances occur. See rationale for details.
*****end add
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, especially in the light of comments
by Vincent Lefevre.
General 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.
*****change
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.
*****to
Common set CO(op) of C-opinsts and how to choose it
---------------------------------------------------
Thus the standard needs to specify a set CO(op) of "common" C-opinsts 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.
The specification of CO(op) must be by general rule(s) that apply to
any new operation that may be put in the library. The specific rules, and reasons
for choosing them, are given below, with separate rules for arithmetic operations
(interval extensions of point functions) and for non-arithmetic operations such as
intersection and convexHull.
*****end change
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 (2) holds --
as in the example cases (a) and (b) above.
*****add
Fundamental Theorem
-------------------
Each flavor (F,f) shall demonstrate that a version of the Fundamental Theorem of
Interval Arithmetic (FTIA) holds, appropriate to its definition of interval and of the "contains" relation.
It follows, from (2) and induction, that this reduces to the classical FTIA of Moore,
in the case when only common opinsts are used, so there is no need to state this as an extra requirement.
*****end add
*****change
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.
*****to
Specific choice of C and CO(op), with reasons
---------------------------------------------
C shall be exactly the "classical" set of closed bounded nonempty real
intervals.
For an interval extension of a point operation "op" , CO(op) shall be all
C-opinsts (X1,X2,...Xk;R) such that "op" is defined and continuous at each point
of the box (X1,X2,...Xk), and R is the exact range of "op" on this box, which is necessarily
a closed bounded nonempty interval.
[Note. This is different from
(*) The restriction of "op" to the box is everywhere defined and
continuous on the box.
To illustrate, (*) implies
sign([0,0]) = [0,0]
is a common opinst, whereas the chosen definition leaves sign([0,0]) undefined. Thus (*)
would disallow cset interval arithmetic from being a flavor, since it gives sign([0,0]) = [-1,1].
However I am not wedded to csets, and could be persuaded to choose (*) instead of the current definition.]
For the non-arithmetic operations convexHull(X,Y) and intersection(X,Y), the normal
set-based definition shall apply for all X,Y in C such that the result is also in C.
Thus, not for the case of intersection when the result is Empty.
Reasons for choice: There seems no point in this motion unless C includes the "classical"
set of closed bounded nonempty real intervals; and choosing 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 a box (X1,...,Xn) 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. Hence the choice of CO(op).
*****end change
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), to non-arithmetic operations (5.6.6) 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.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.
--
---------------------------------------------------------------
Ralph Baker Kearfott, rbk@xxxxxxxxxxxxx (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------