Re: Motion 8: Exception Handling for Interval Arithmetic
> Date: Wed, 16 Sep 2009 20:57:30 +0200
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> Subject: Re: Motion 8: Exception Handling for Interval Arithmetic
>
> Dan Zuras Intervals wrote:
> > First, from the motion:
> >
> > 2.2. An operation on standard decorated intervals returns a
> > standard decorated interval whose interval is the result of the
> > operation on the argument intervals, and whose decorations are
> > computed from the arguments such that they retain the most
> > informative and valid information about the interval. All result
> > decorations will be completely specified (later) according to
> > the intended semantics of the decoration trits.
> >
> > This is excellent. The intervals only depend on the intervals.
> > And the decorations may depend on both. This promotes (indeed,
> > I would say, is essential for) efficient implementations.
> >
> > However, in the rationale, we have:
> >
> > 3.2. Recent discussion in the P1788 forum showed that some
> > interval algorithms require decorated intervals while others
> > only require intervals and/or decorations (or NaI's). There are
> > various implementation and performance tradeoffs to be gained or
> > lost by restricting interval computations to only one of these
> > types of objects. These tradeoffs may depend on available
> > (present or future) platforms, hence the choices should be left
> > to implementors for exploitation, rather than be fixed by the
> > standard.
> > The framework presented in this motion also unifies the concept
> > of NaI and Empty in a semantically correct way. For example,
> > given any non-empty interval X,
> > X \union Empty = X
> > is usually the case. However, depending on the history that
> > created Empty, some applications may need
> > X \union Empty = Empty,
> > which is the same semantics as NaI, i.e.,
> > X \union NaI = NaI.
> > This can be neatly handled by decorations.
> >
> > This example would seem to be the main desired result of the
> > motion & yet it is an example where the interval result DEPENDS
> > on the decoration of the operands.
> >
> > Is this a violation of clause 2.2 of your motion or am I
> > misreading things?
>
> The above is the ambiguity when not using decorations.
> With decorations, where
> -- ok is the decoration of a nonempty, bounded new interval,
> -- emp is the decoration of an empty set created by intersecting
> two decorated intervals with ok decoration,
> -- inv is the decoration of an interval created by an invalid
> conversion,
> we may have for example
> (X,ok) union (Empty,emp) = (X,ok)
> as an unambiguous version of X \union Empty = X, and
> (X,ok) union (Empty,inv) = (X,inv)
> as an unambiguous version of X \union NaI = NaI
> (which would have had to be X \union Empty = Empty
> in the Vienna proposal, with an Empty with payload.
Good. I get it now. It is well defined & the interval
portions do not, in fact, depend on the decorations.
This also answers my question about 'isValid' which seems
to be a way of getting at 'invalid'. Also a good approach.
>
> Since the motion should not be overloaded with details for all
> operations, we did not define good notation for decorations and
> (cf. 3.3) did not spell out decoration propagation rules beyond the
> bare minimum.
I understand. I just needed some examples to understand
your intention.
>
>
>
> > 2.3. An operation on bare decorations is obtained by promoting
> > the bare decorations to decorated intervals whose intervals are
> > the empty set and then performing the operation with the
> > resulting decorated intervals.
> >
> > While I can admit the possibility that operations on bare
> > decorations might be necessary, I can think of none.
>
> ONce an exception of a certain type occurred, the user could decide
> to continue only with the decoration. An invalid interval could
> propagate much faster since the interval part need not be inspected
> anymore. Most bare decorations behave like NaI.
OK, while this may or may not be strictly necessary, it is
a good optimization to give to our implementors.
>
>
> > 2.5. Forgetful operations behave as specified above except they
> > throw away either the interval or decoration portion of the
> > result.
> >
> > And yet, since operations in 2.4 would seem to be 'maximally
> > forgetful', I don't see the need for explicitly forgetful
> > operations.
> >
> > Can you provide possible examples?
>
> What precisely will be useful must be further discussed.
> The motion only demands that some such operations exist,
> not their precise specification. Perhaps two operations
> forgetDecoration and
> forgetInterval
> are enough.
Given the above, I can see this now.
>
> One certainly needs the former, to enter a high-speed
> program area where one knows exceptions cannot occur.
>
> A compiler writer may need the latter for optimal speed in
> computations involving exceptions, when it is known that after a
> lengthy computation only the decoration is needed to make a decision.
>
>
> > 3.1. This motion uniformly handles all arithmetic and
> > nonarithmetic exceptions that are relevant for interval
> > arithmetic and its applications. It eliminates the need for
> > separate global sticky flags, and integrates non-intervals
> > (NaI), without introducing any overhead for users who don't make
> > use of exceptions.
> >
> > Specifically, just how are NaIs 'integrated' into other
> > intervals 'without introducing any overhead'?
>
> A compiler that sees that a certain computation does not check
> the final decorations can decide to forget the decorations.
> Then the arithmetic works exactly as if there would never have
> been decorations, and is optimally fast.
> (The same could be done by a compiler directive if the user knows
> that exceptions do not matter.)
Now that I see that all the needed NaIs live entirely
within the decorations, this is clear to me.
>
>
>
> > Are NaIs intended to live only within the decorations?
>
> Formally, there are no NaI anymore, but some bare decorations
> and decorated intervals with these decorations take the role of NaI
> with payload,
>
>
> > Is empty only a decoration or does it live in the interval
> > as well?
>
> It has to live in the interval part, as otherwise rule 2.2 would not
> make sense.
Of course. It also means that some interval operations
will result in a decoration set with multiple decorations
set for various different uses. So, in some of our
favorite examples:
sqrt([-2,-1]) = (Empty,isEmpty+notDefined)
sqrt([-2,+1]) = ([0,1],possiblyDefined)
Or is that last ([0,1],possiblyEmpty+possiblyDefined)?
Either way, it should solve both the problems of returning
an empty set when needed & preserving the information that
we were evaluating on the boundary of the domain of the
function which is all important in Nate's classification
methods.
>
> Motion 8 does not decide on the actual decoratiosn, and it is not
> certain that the Empty trit will be needed or useful. This is to be
> discussed.
I think it will but it is worthy of discussion as you say.
>
>
> > 3.4. Useful candidates for decoration trits are:
> > isValid possiblyValid notValid
> > isStandard possiblyStandard notStandard
> > isEmpty possiblyEmpty notEmpty
> > isEntire possiblyEntire notEntire
> > isBounded possiblyBounded notBounded
> > isDefined possiblyDefined notDefined
> > isContinuous possiblyContinuous notContinuous
> > isTight possiblyTight notTight
> > These fit exactly into 2 bytes if each trit is represented by
> > two bits.
> >
> > This is an excellent set of decorations. It would seem to
> > cover all we might need &, as you say, fits in 2 bytes.
> >
> > All the intended uses of these decorations (as well as good
> > propogation rules) seem clear to me except for 'isValid' &
> > its kin.
>
> For example, we could decide that
> stringToInterval('[Inf,Inf]')=(Empty,notValid)
I understand now. Good.
>
>
> > What does this mean in the context of the other decorations?
>
> Probably all trits should propagate independently (though we haven't
> considered the possibilities exhaustively - this should be based on a
> semantic definition of the trits and the operations, and then a formal
> exhaustive check by Coq or so).
> So the Invalid trit probably does not affect other trits.
>
>
> > Can you give examples of all 3 trits of this decoration to
> > clarify things?
>
> stringToInterval('[1,-1]')=([1,-1],notStandard)
Well, I was looking for examples of the 'valid' trit but
I believe I understand your intention now.
>
> The Empty and Entire trit need no explanation.
> maybe we do not need them at all.
>
> Bounded is needed, e.g., for checking the assumotions of Brouwer's
> fixed point theorem
And for some of Nate's examples as well.
>
> [1,1]/[0,0]=(Empty,notDefined)
> [1,1]/[-1,1]=(Empty,possiblyDefined,notContinuous)
>
> Tight means constructed using only interval operations implemented with
> maximal accuracy.
Good. This neatly replaces the accuracy modes in Vienna.
>
>
>
> Arnold Neumaier
>
Thanks for all the clarifications.
You have both done a wonderful job on a very difficult
problem.
Yours,
Dan