Revised interval flavors motion (36.02)
P1788
I submit the following revised version of Motion 36.
Please check it for errors as I revised the version 01 text in a bit of a hurry. In particular if I have omitted some amendments I previously agreed to.
John Pryce
Motion 36, version 02.
======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.
2. There shall be a set of "common intervals" shared by all flavors, namely
the closed, bounded, nonempty real intervals (also called "classical
intervals").
The meaning of "shared" in the previous paragraph is defined precisely in
the Rationale. Informally, common intervals behave as a subset of each
flavor, such that operations whose input(s) and output(s) are common
intervals 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 the
decoration system, shall be decided by future motions.
Rationale
=================================================
This rationale text is mostly an edited version of the email Michel and I
circulated on 23rd May 2012.
Back-of-envelope summary
------------------------
There is a set bS of behaviors for set-based intervals and a set
bM of behaviors for modal intervals. P1788 aims to maximize their
overlap and minimize the difference sets bS - bM and bM - bS.
More precise statement
----------------------
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 by
the paragraph containing (1) and (2) below. 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
-----------
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.
Level 1
-------
Set-based intervals and modal intervals both arose from the arithmetic on
classical intervals, extended in different directions. Here "classical"
means 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 set-based things,
- a set M of modal things.
C must include at least the classical intervals, else this proposal becomes
useless. It may include more, such as the empty set, but that is to be
"agreed" between the supporters of M and S.
Making C as large as we can seems a good thing, but may make it harder to
add another flavor in the future.
There is an "agreed" library of named operations, all of which act on each
set. There may be other operations that are private to S or private to M.
There are "agreed" one-to-one embedding maps [I abbreviate s(x) to sx and m
(x) to mx when context makes clear]
s : C -> S }
and } (1)
m : C -> M }
by which C can be regarded as a subset sC of S or as a subset mC of M. The
crucial point is that for each "agreed" operation "op" we must have (I'm
assuming a binary op, the general case is similar):
s(X op Y) = sX op sY }
and } (operation compatibility) (2)
m(X op Y) = mX op mY }
for all intervals X,Y in C such that sX op sY is in sC and/or mX op mY is
in mC.
Let an instance of an operation (that is, the specific "op" and specific
arguments X,Y that are common intervals) be called "internal" in a given
flavor if X op Y is a common interval. So basically (2) means that if an
operation-instance is internal in one flavor, then it must be internal and
give a compatible result in the other flavor. Otherwise there should be two
separate operations.
[Thanks to Vincent Lefevre 2012/07/05 for this wording, which I have edited
slightly.]
The same must hold for any other flavor that might be added in future.
In view of these maps it is immaterial what a common interval "is". If
you're an M supporter you think it is a particular kind of modal interval.
If you're an S supporter you think it is a particular kind of set-based
interval. (2) says you shall get the same results either way. In that sense
C is "shared" between all flavors.
Cautions
--------
In the previous version, I said I suspected hidden traps in specifying
operations on the common set C, namely about the set of interval inputs
they operate on. I think the revised definition of (2) helps, but it
doesn't entirely solve the problem.
I asked, e.g., if "operation compatibility", as in (2), is to hold for
A = [1,2]/[-1,1] ?
B = sqrt([-1,1]) ?
C = sign([0,7]) ?
In the language introduced above, which of these operation instances are
internal?
Instance A can't be internal, because its set-based value cannot be a
common interval (whether we take the exact range, or its hull).
B has the set-based value [0,1], a common interval. Here, the function is
continuous wherever defined, but isn't defined everywhere on the input. I
don't know the modal/Kaucher value, or if it has one.
C also has the set-based value [0,1], a common interval. Here, the
function is defined everywhere, but isn't continuous everywhere on the
input. Again, I don't know the modal/Kaucher value, or if it has one.
Question to modal folk: Is it necessary to make the quite restricted
definition:
An operation instance is internal iff the operation is
everywhere defined and continuous on its inputs
or can modal theory go beyond that in some circumstances?
Note. Since this is about "exceptional cases", it is also about how we make
decorations interoperate with flavors.
Level 2
-------
Let's do the same at Level 2. 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 maps (1)
and compatibility equations (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)?
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.
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.
(Or, if intervals are part of a language, runs identically whether using
the "modal" or the "set-based" compiler switch.)
This is slightly reworded from Version 01.
Difficulties
------------
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 cancelminus(), they should
IMO exist in two named versions, say cancelminusS and cancelminusM, etc.
Then, if you are running an algorithm that relies on
[1,2] cancelminus [10,20]
producing a modal (improper) interval, you *must* use cancelminusM. If you
thentry to link with the "set-based" library the system will report your
error,because it has no cancelminusM operation.
An alternative is to give the operation the same name in both flavors, and
let such events be discovered at run time.
[My examples of division & tan(x) seem now to be covered by the "internal"
discussion.]
Impact on the standard text
---------------------------
As far as I can see this proposal doesn't change the level structure. There
will be impact on the arrangement of material -- almost certainly one
should hive off some parts to a "common" text. However, as I said recently,
I'm thinking to include copies of this text in each flavor's document, so
one can read it without jumping around. I think "common" material includes:
(a) Most of Level 2.
(b) Most of the Level 1 lists of required& recommended ops.
(c) Most of the decoration system at Level 1.
The Level 1 interval theories of different flavors are utterly different,
so will be big disjoint chunks of text. That's the current 5.1-5.5 of the
text.
Item (b) is an instructive "starter" to see what would need doing.