Re: Motion on interval flavors
Dear P1788,
I do not know if this motion is considered "officially" having Michel
Hack as a second or not yet, so I hereby second this motion by John
Pryce in order for us to discuss it.
--
Hossam A. H. Fahmy
Associate Professor
Electronics and Communications Engineering
Cairo University
Egypt
On Wed, 2012-06-20 at 06:49 +0100, John Pryce wrote:
> 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.