Structured support for both standard and modal intervals
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