Re: Motion on interval flavors
Dear John,
If Kaucher intervals were to be included inside the standard, your
proposal would make a lot of sense ! Although I did not check all the
details, I think this is the right way of letting set based intervals
and Kaucher intervals live together. However, as explained several
times during the previous months, including Kaucher intervals in the
standard would be a dramatic error. Let me summarize:
- Scientific point of view. Several experts, including me, have
claimed that every thing that can be done using Kaucher intervals can
also be done using standard intervals (see e.g. the paper by Arnold
Neumaier who spent much time to help us having a wider view on this
topic). There are a few exceptions where Kaucher interval really bring
something that cannot be done using standard intervals, but they are
very technical and, most importantly, not among the applications
proposed by the supporters of including Kaucher intervals in the
standard.
NO REAL SPECIFIC APPLICATION
- Political point of view. We are currently spending a lot of time
discussing of standardizing an exotique theory, of which different
experts have different formulations, different applications, etc. This
is clearly an evidence to me that this theory is not mature enough to
be standardized. Only a very few people among the standardization
group participants are lobbying to include it, so it seems we may take
a decision with heavy consequences on the standard for the interest of
a very small group.
NON MATURE AND SUPPORTED BY A MINORITY
- Standard redaction point of view. Deciding now to change so deeply
the standard structure while we are already so late would probably
lead to great trouble to have an homogeneous and consistent standard
in a reasonable delay.
VERY HARD TO WRITE
- User point of view. Although it makes sense, the flavor proposal is
strongly increasing the complexity of the standard. Having flavors
after decorations make myself is a bit discouraged by so much
complexity, so what about the enduser we aim to reach with this
standard !
VERY HARD TO READ/USE
To summarize, I think that if this motion passes then the standard
have chances to be too complex to be eventually written, or used if
eventually written. Shall it not pass, we will hopefully not discuss
including Kaucher intervals in the standard and focus on more urgent
issues.
Alexandre Goldsztejn
On Wed, Jun 20, 2012 at 7:49 AM, John Pryce <prycejd1@xxxxxxxxxxxxx> 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.
--
Dr. Alexandre Goldsztejn
CNRS - Laboratoire d'Informatique de Nantes Atlantique
Office : +33 2 51 12 58 37 Mobile : +33 6 78 04 94 87
Web: www.goldsztejn.com
Email: alexandre.goldsztejn@xxxxxxxxxxxxxx