P1788
I propose an approach that may lessen the ongoing controversy about
different models of interval arithmetic basics. It is essentially the same
as what Michel Hack recently proposed. He, I and one or two others are
working to turn these ideas into one or more motions.
We seem, at present, to be discussing a structure of 1788 where modal (or
Kaucher) intervals are supposed to do everything that standard intervals
do and then some; and if there is some behaviour of standard intervals
that is inconvenient or impossible for modals, it should be modified.
Right from the start I've had a different view.
Back-of-envelope summary
------------------------
There is a set bS of behaviors for standard 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
----------------------
I emphasize that what matters is behavior, both at Level 1 and Level 2. It
doesn't matter that a standard interval is a set of reals and a modal
interval is something else, provided that when applied to the "same"
inputs they give the "same" result according to an appropriate meaning of
"sameness".
I'll use the terms
thing = a Level 1 bare or decorated interval,
datum = a Level 2 bare or decorated interval,
The word "agreed" is used frequently. This marks a design decision the
group must make, to let the standard and modal worlds interoperate.
Level 1
-------
Our standard intervals, and modal intervals, both arose from the
arithmetic on classical intervals, extended in different directions. Here
"classical" means closed bounded nonempty real intervals. So assume at
Level 1 there are
- a set C of common (in the sense of "shared") things,
- a set S of standard things,
- a set M of modal things.
C shall include at least the classical intervals; it may include more,
such as the empty set, but that is to be "agreed" between the supporters
of M and S.
The bigger we can make C, the better for everyone.
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 a subset mC of M, as
you wish. 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.)
"Is" a member of C a set of reals, or a pair of reals, (xlo,xhi), or what?
I don't know. 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 standard interval. (2) says you shall get the same results either
way.
Level 2
-------
Let's do the same at Level 2. There are
- a set C of common datums,
- a set S of standard 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 standard 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 standard 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 "standard" library.
(Or, if intervals are part of a language, runs identically whether using
the "modal" or the "standard" compiler switch.)
Difficulties
------------
What of operations that behave differently in the "standard" and "modal"
worlds, 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 "standard" 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 worlds, and
let such events be discovered at run time. E.g. suppose the modal folk
decide either to support *unbounded* intervals differently from the
standard folk, or not to support them at all. Then such intervals cannot
be in C. So doing
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 worlds, but I don't think that would be
popular. So an event such as doing 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. But this problem will be present no matter how we
structure the standard, given that we aim to support two different
"worlds".
Final note
----------
I respect what Nate Hayes is aiming to achieve with his "Overflow" paper
and motion. But it is an imperfect compromise between the standard and
modal models, losing the simplicity possessed by each on its own. (And I
can't help feeling that if a satisfactory theory of this kind existed,
someone such as Kaucher would have created it already.) The alternative,
outlined here, makes such compromises unnecessary. There are, as Michel
Hack puts it, two "flavors" of the standard; they have equal merit; they
have an agreed overlap by which they interoperate; outside the overlap, we
can design the best standard for each flavor without requiring any changes
to the other flavor.
We look forward to your comments.
John Pryce, with Michel Hack