Supporting set- and modal-paradigms
P1788 members
Here is my take on the problem of supporting both set intervals and
modal intervals in one standard. I offer it now, during the
discussion period of "multi-format" motion 6, because
- I believe it, like multi-format, is best treated as a level 2 issue.
- But the considerations below suggest it is completely orthogonal to
multi-format. What we decide on either issue does not affect the
other. That, if true, is nice to know while we are discussing motion 6.
Nate's sales pitch for a modal system (MOD for short) in his paper
"Introduction to modal intervals" (version of 2009 April 26) is that
it is possible to extend the set-interval system (SET for short) by
adding extra objects, and extending the operations, so that if one
sticks to set-intervals one never notices the difference.
But can this really be done? This is about
- the definition of the abstract objects and operations of level 2,
in the two systems;
- how closely they do, or can be made to, correspond; and
- the implications for representation and implementation level 3.
For simplicity, leave aside NaI (till later). Also consider just one
format, say 754's binary64.
What the level 2 objects *are*, is arbitrary. They can be replaced by
any other set of objects that is in 1-1 correspondence (=bijection),
with the operations appropriately re-defined on the new set.
- SET has one set of abstract interval objects. I think of them as
*being* a finite subset of the set of mathematical intervals.
- MOD has another set of abstract interval objects. Following Nate's
paper they *are* ordered pairs (xx, Q) where xx is a nonempty set-
interval and Q is either \E or \A (the existential or the universal
quantifier, respectively). When Q is \E the interval is "proper",
else "improper".
Or, one can equally say that they *are* ordered pairs of numbers,
written [a,b], with the bijection defined by mapping [a,b] to
(xx = set-interval [a,b], Q = \E) if a <= b,
(xx = set-interval [b,a], Q = \A) if a > b.
(To get a bijection, you have to say that when xx is a singleton
interval, either (xx,\A) is considered equal to (xx,\E), or that (xx,
\A) is forbidden. I shall take the latter convention. Nate is vague
about this.)
How to merge SET and MOD into one system?
-----------------------------------------
If it were true that the set of level 2 objects in either system *is
a subset* (under some natural correspondence) of the set of level 2
objects in the other system, things might be easy. But this is NOT
the case.
The correspondence, of course, is between
nonempty SET interval xx and MOD interval (xx, \E).
(eqn1)
Then, in finite precision (i.e. at level 2), for:
- bounded, nonempty SET intervals, and
- the four arithmetic operations excluding xx/yy when 0 in yy,
SET and MOD match up exactly. But outside this, they do not match up.
Difficulties with the objects:
(1) SET objects that do not exist in MOD -- just the empty set;
and MOD objects that do not exist in SET -- all the improper
intervals. These don't cause a problem as such, but getting a
level 3 representation of them that makes SET and MOD operations
equally fast seems a problem.
(2) Unbounded MOD intervals may be a problem. Hayes (sect 7.4) says what
such a thing is *represented by*, but doesn't say what it *is*.
But from other remarks in 7.4, I believe it *is* (xx, Q) where xx
is a SET unbounded interval as Motion 3 has decided it shall be
-- that is, a closed unbounded connected subset of the reals R;
and Q is \E or \A. If so, then (eqn1) works fine for unbounded
intervals too.
(3) MOD intervals represented by [-oo,-oo] and [+oo,+oo] (Hayes 7.5)
seem to be a problem, because they do not exist as separate
objects in SET.
Hayes 7.5 also mentions signed zeros -0, +0 as endpoints, but says
they are treated as the same. That is, at MOD level 2 there is only
one zero, just as in SET. So -0, +0 do not cause a problem.
(4) Hayes 7.6 writes of "indefinite modal intervals", which have one
"mark" (= endpoint) equal to NaN; and says all of these should be
called NaI. In my view this illustrates a confusion, throughout
Hayes
sect. 7, between level 3 and level 2. I would like to know whether
at level 2 of MOD there should be just one NaI abstract object, or
several. E.g. in MOD does the operation [1,2]/[0,2] on legal
intervals produce the same kind of NaI (at level 2) as, say, a
faulty constructor that creates an illegal object "[3,NaN]"?
Difficulties with the operations:
(5) Division by an interval containing zero. In SET this is just an
ordinary operation. There is more than one proposal for how to get
the maximum information from it: Kulisch & Kearfott propose two
styles of "extended division" so that, e.g., 1/[-2,4] returns, in
effect, [-oo, -0.5] union [0.25, +oo]. Vienna proposes "division
with gap" with equivalent effect.
In MOD however, it is proposed that this return some form of NaI.
(6) Operations on unbounded intervals. In SET there is nothing special
about them: they are defined exactly as operations on bounded
intervals. In MOD, Hayes 7.4 does not explain how the operations
are defined, so I can't tell whether there is a problem here or
not.
Sample question: in MOD does xx*0 = 0 for every proper interval xx
-- whether bounded or not -- as is the case in SET?
(7) Neumaier's paper assessing nonstandard interval arithmetic says
there are various ways to extend general binary point-operations to
nonstandard intervals; modal & Kaucher arithemtic differ in their
definitions; but luckily these reduce to the same thing for the
four basic operations, by monotonicity properties. But for other
standard functions, both unary and binary, do MOD definitions,
restricted to proper intervals, always give the same result as SET
definitions? If not, one will need separate SET and MOD interval
libraries.
(8) The concept of "loose" evaluation (i.e., ignoring points outside
the domain of a function) seems unacceptable to the MOD approach,
but is essential for certain applications of the SET approach.
My conclusions:
Level 2 is the best place to discuss the prospects for merging two
distinct but overlapping interval systems, while having regard to
finite-precision issues. But one must consider level 3
simultaneously, to avoid a system that is mathematically nice but
hopelessly inefficient. For instance, support seems to be growing for
NaI to exist, but MOD's NaI is a different beast from SET's. Can one
devise a representation that handles NaI, indeed more than one kind
of it, and also runs at speed on modern FPUs, especially in massively
parallel applications such as element-wise array processing? The
empty set raises similar level 3 questions, because MOD returns an
improper interval in various cases where SET returns Empty.
I believe it is difficult, in software, to implement one interval
system that runs both SET and MOD with maximum efficiency. There is a
big overlap between the two. But there is an inevitable parting of
the ways.
One can write a system angled to SET, and put an MOD wrapper round
it, thus making MOD rather slower than SET. One can do the reverse,
making SET slower than MOD. Or one can put branches in the code, to
choose between the two systems, making both systems run slower than
they could.
On the other hand, if we look forward to a 1788 standard being
implemented in hardware, it seems feasible to angle it toward SET but
provide "hooks" to support efficient implementation of MOD. The
Vienna proposal takes steps towards this. I support Nate's suggestion
that P1788 should concentrate on SET for now, and that the "modal
subgroup" of P1788 should decide, later in the production of our
standard, just what it thinks those "hooks" should be.
I offer these conclusions diffidently, as I still find modal theory
very hard to grasp; and I am not knowledgeable on hardware.
Best wishes
John Pryce