Motion on interval flavors
P1788
I submit a motion that the standard shall permit different "flavors" of
interval, as proposed by Michel Hack and myself recently. It specifies (a)
technical properties of the standard, and (b) responsibilities within the
group for constructing the part of the standard relating to each flavor.
I think items 1-7 of the motion must go together as they set out the basic
structure. It would be nice to agree to item 8 at the same time, but if it
proves controversial we could defer it.
I'm not very happy with the name "set-based" intervals, but calling them
"standard" intervals is no longer appropriate, as well as clashing with the
main meaning we give to "standard" (as a noun and also an adjective). Any
better name welcomed.
Regards
John Pryce
======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 intervals shared by all flavors. These "common
intervals" shall include at least the set of all closed, bounded, nonempty
real intervals, called "classical intervals". Any extension of the common
intervals beyond this set shall be by agreement between the editorial teams
of the different flavors.
The meaning of "shared" and "include" 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.
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. The set-based and modal Editorial Teams shall agree on the set of common
intervals, taking into account the possible future creation of other
flavors. (The common intervals may well coincide with the classical
intervals.) The target shall be to submit a motion specifying this set,
within four weeks of this motion passing.
8. 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.
9. 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 recently.
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" and "include" 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
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. (I'm assuming a binary op, the general case is
similar.)
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.
Caution
-------
My intuition tells me there are hidden traps in specifying operations on
the common set C. Namely about their *domain* -- not in the sense of point
function domain as in Table 2, 5.6.2 of the standard text, but "the set of
interval inputs they operate on".
E.g., is "operation compatibility", as in (2), to hold only for those cases
where the corresponding point function op(x,y) is defined and continuous on
the box (X,Y)? Or must it hold also for
[1,2]/[-1,1] ?
sqrt([-1,1]) ?
sign([0,7]) ?
This is not just about "how a program chooses a flavor", by a compiler
switch or whatever; it raises questions of meaning, that must be sorted
before we proceed. See also "Difficulties", below.
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 uses common intervals
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.)
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 (dual) interval, you *must* use cancelminusM. If you then
try 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. E.g. suppose the modal folk
decide either to support *unbounded* intervals differently from the set-
based folk, or not to support them at all. Then such intervals cannot be in
C. So doing
[1,1]/[0,1]
produces an output that isn't in C, from one that is in C. Operations such
as tan(x) cause the same difficulty.
Unlike cancelminus, division is used frequently. We could give it different
names in the two flavors, but I don't think that would be popular. So an
event such as doing [1,1]/[0,1] has to be detectable, presumably via the
decoration system. (Our proposed decoration schemes do detect it, but maybe
not in a way that is useful for the current purpose.)
Or else we have to water down principle (*). I don't currently see an ideal
solution.
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. 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.