Dan Zuras wrote:
From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
To: "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>
Cc: <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: The history of the word 'format' in 754...
Date: Wed, 20 Oct 2010 09:56:08 -0500
Dan Zuras wrote:
>> . . .
>>
>
> Now, in the floating-point world exceptions are often
> ignored. Even routinely ignored. While I am not aware of
> any implementation that does not compute the exceptions in
> that case, there is nothing that would prevent it. No one
> would ever know the difference.
>
> Let me suggest that the same be true for intervals. That
> is, that decorations may be dispensed with when it is known
> that they are being ignored. Or perhaps when it is known
> that they do not change in the course of a calculation.
> In this case, bare intervals would be a useful optimization
> at level 3 because, at level 2, they are indistinguishable
> from decorated intervals that computed their decorations &
> ignored them.
>
> However making bare intervals a primary datatype at level
> 2 creates a situation in which one intentionally computes
> WITHOUT the information necessary to correctly interpret
> the results. The analogy would be computing in
> floating-point WITHOUT computing the exceptions. How
> would one know if this infinity is the result of an
> overflow or a divideByZero?
Right.
This is the desired situation in certain interval algorithms, hence
a reason bare intervals should be first-class Level 2 types.
Isn't concern for correct computing the
point of ALL interval algorithms?
It has been pointed out to me by John and Arnold that one sometimes wishes
to compute 1/[-1,1]=[-Inf,Inf] without generating an exception. So ask
them.
>
> Therefore, let me suggest that the proper place for such
> things as bare intervals be at level 3. There they may be
> used by an optimizing compiler without compromising the
> assured computing which is the only reason for intervals
> to exist in the first place.
>
> I'm sure many applications will be able to take advantage
> of them. In particular, your graphics algorithms seem
> particularly well suited to such optimizations.
Most of the graphics algorithms we use are variants on branch-and-bound.
What this means is that bare intervals are all that is needed until an
exception occurs. At that point, the bare intervals are no longer needed
but
bare decorations are then required to finish propagating the exceptional
information through some lengthy computation.
And how will you know that an exception has occured
on a bare interval?
Lets assume there is a sqrt() operation which operates on decorated
intervals.
For the decorated interval xx = ([-1,4],domain:(T,F))
sqrt(xx) = ([0,2],domain:(T,T))
generates an exception, which is recorded in the (T,T) state of the domain
tetrit.
Now lets examine, closely, what happens if we smiply pass a bare interval
to the sqrt() operation, instead:
Motion 8.02 says a bare interval may be promoted to a decorated interval
in order to participate in arithmetic operations. Hence, the bare interval
[-1,4] is promoted to the decorated interval xx = ([-1,4],domain:(T,F)).
The decorated interval xx is then input to the sqrt() operation and the
exception is generated and recorded in the decoration of the decorated
interval output yy. So if I write a marcro or inline function:
bareOrDec(yy)
that returns the interval portion of yy if the decoration of yy is "safe"
but otherwise returns the decoration portion of yy, then:
bareOrDec(sqrt([-1,4]))
accomplishes the task.
You must be counting on some standard exceptional
behavior in the interval part alone to tell you.
We have defined no such standard exceptional
behaviors yet. Will you be making a motion to
this effect?
I wasn't planning to, since it is not strictly necessary. Motion 8.02 and
Motion 18 already provide the necessary definitions and semantics, as
shown above.
However, if people think it would be helpful to have some of this
clarified, I'd be willing to make a new motion for that purpose (i.e., to
clarify, not to change anything).
And when you switch from bare intervals to bare
decorations where will you be getting the operands
that contribute to your bare decoration results?
See the above example.
Without further details, much of this description
smells of things that belong in the decorations of
decorated intervals. At least at level 2, the
level of abstractions.
Exactly.
Dan, you are entirely correct! :-)
Examine the example above, and you will see that it is the decorated
interval that plays the crucial role in allowing this to happen.
This is mostly analagous to how an IEEE 754 computation might not check
exception flags, but would instead depend on a NaN propagating through a
lengthy computation so as to correctly indicate the computation failed
for
some reason.
Of course, with the bare decorations, there are decoration flags in the
payload. So the branch-and-bound algorithm can also see exactly what
exception occured, e.g., "possiblyDefined" vs. "notDefined" etc. It then
uses this information to more optimally delete boxes from the solution.
Decoration flags in WHAT payload?
When have we ever discussed the 'payload' of a bare interval?
What is it you have in mind here?
I'm sorry if I threw you off track:
There are decoration flags in a bare decoration.
I am NOT suggesting a bare interval carries any payload.
> The
> compiler could strip out that 17th byte, pack things up
> nicely, & run literally bare only.
Right... where "bare only" means either bare interval or bare
decoration. Under different circumstances, both will be needed.
The circumstances I suggested were ones in which
a compiler PROVED no decoration was needed.
What circumstances are you suggesting?
Like those mentioned above.
I think compilers will not be able to make these deductions, since when
and where the exception may occur will not be known until runtime.
>
> But let this particular tool be used by compilers & proof
> engines only. To hand it to the fallable user only invites
> error & then mistrust of the standard.
>
I believe IEEE 1788 should provide the Level 2 model with bare
intervals, bare decorations, and decorated intervals and then
leave it up to vendors and implementers to decide how "automated"
the various combinations of these objects will be at Level 3 and
beyond.
I'm sorry Nate. I cannot agree with this.
You should not have voted yes to motion 8.02 then.
This is exactly the sort of thing that will lead to
a standard that does not assure anyone of anything.
Just the opposite:
If you do not agree to this but advocate compilers should optimize away
decorated intervals into bare intervals and bare decorations, then
everyone will do this differently and without any specification or
guidance from IEEE 1788.
That will be a total disaster.
As John's recent challenge shows, even when the USER makes a
programming bug, the decorations will ensure the exception does
not go unnoticed.
No.
You have misinterpreted the meaning of John's challenge.
There was no bug in it. The crux of the challenge was
to recognise that when feedback (either from iteration
or recursion) leads an output to become a new input,
that new input must be 'wiped' of its computation
history as it no longer has any meaning in the context
of an input.
The 'bug' is to be found in any program that fails to
realize that.
Wrong.
John's program is like the following IEEE 754 floating-point example:
float x = -1;
while ( true ) {
float y = sqrt( x ); // generates NaN when x=-1
if ( isnan(y)==false )
break; // succesful exit
else x = y; // x is now a NaN
}
This program will never break out of the while loop, because the NaN is
properly propagated per IEEE 754 semantics.
John's challenge was to recognise that this was so.
No standard will ever be able to prevent users from writing bad
code. But you once wrote a long and eloquent e-mail about how the
standard must ensure correct results even under these conditions,
lest liability be transferred from users to us, the authors of
the standard.
Nate Hayes
> . . .
Nate, I don't think you can use my words against me
in support of something that fails to produce correct
results.
Besides, I don't understand your reluctance to use
bare intervals & bare decorations at some level below
level 2. Level 2 is only at the level of abstractions.
The optimizations or improvements you seek are all to
be had at lower levels. Confining these 'bare' things
to those levels does not denegrate them. It places
them at a level for which those improvements have
meaning.
Where it is safe.
When it is safe.
As I mentioned above, if IEEE 1788 does not specify this behavior at Level
2, then it will be a "free for all" at Level 3. So nothing will be safe,
since there will be no standard to prove what is correct or not.
Nate Hayes
Dan