Re: Motion 8: Exception Handling for Interval Arithmetic
[Dan, sorry for the second copy -
I had sent this only to you instead of to the whole list.]
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.
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.
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.
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.
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.)
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.
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.
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)
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)
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
[1,1]/[0,0]=(Empty,notDefined)
[1,1]/[-1,1]=(Empty,possiblyDefined,notContinuous)
Tight means constructed using only interval operations implemented with
maximal accuracy.
Arnold Neumaier