Re: Bare decorations (was ...level 2 datums)
Nate Hayes wrote:
John Pryce wrote:
What I did not grasp before
---------------------------
<level3>
Bare decorations CAN be stored as single bytes, but we also give them
encodings in 16 bytes -- distinct from encodings of bare intervals. Thus
{intervals} union {decorations}
can be regarded as a single datatype, analogously to IEEE 754's
{F.P. numbers} union {NaN}
(in a given format, say binary64), forming a single set of floating point
datums. When viewed thus, the different bare decorations are, i.e. can be
defined to be, different kinds of NaI.
In particular, an *array* of 16-byte objects can hold a mix of intervals
and NaIs on which to do arithmetic -- but NOT general decorated
intervals,
which need 17-byte objects.
Encoding the decoration values in NaN payload(s) looks promising, but may
need special hardware and/or revision to 754's NaN handling to be really
efficient.
</level3>
Yes.
This is _one_ of the possibilities conforming to Motion 8.
But nothing of this kind is required or suggested in Motion 8,
which was purely level 2. So there was nothing to be grasped about this,
except for the existence of more possibilities for implementation.
Arithmetic
----------
Abstractly, arithmetic on a mix of bi's, bd's and di's is defined by
promoting each bi or bd to a di
With one important exception:
The only way to construct a decorated interval is from
-- a bare interval; or
-- a bare interval and a bare decoration.
Promotion is just a form of construction. Usually, promotion means the
construction is implicit. Hence, this means a bare decoration can never be
promoted to a decorated interval, since a decorated interval can never be
constructed only from a bare decoration.
If users wish to, they can override this behavior by explicitly
constructing
a decorated interval. But this requires the user to explicitly provide both
a bare interval and a bare decoration from which the decorated interval
will
be constructed.
Yes, this is essential.
then doing the operation on the resulting di's. This is Motion 8
§2.2-2.4,
but it needs rewriting:
(a) It doesn't cover a mix of operands, such as (bare interval) + (bare
decoration).
This is covered by 2.3 that says any operation involving a bare decoration
must always result in a bare decoration.
Yes.
So in the example
(bare interval) + (bare decoration)
one could promote the bare interval to a decorated interval to obtain its
(optimistic) decoration. Then the infimum of the two decorations should be
returned as a result of the arithmetic operation.
No. As stated in Section 2.4 of the Motion 8 rationale, one has
to promote the bare interval to a decorated interval to obtain its
most pessimistic consistent decoration - since one cannot know
what the dropped decoration looked like.
In the 5-value decoration scheme I had suggested, this would mean
that a bare interval is promotred to a decorated interval with
decoration 4 if it is Empty, and decoration 2 otherwise.
Otherwise dropping a decoration and then promoting the bare interval
to a decorated interval may give over-optimistic decorations -- e.g.,
providing everywhere definedness although this need not be the case.
(Whether or not this actually is the case depends on the conditions
under which bare decorations are created.)
(b) §2.3 must now say explicitly, I believe, that every bd is promoted by
giving it an empty interval part, i.e. it becomes (Empty, bd).
No, in agreement with the explantion of Nate Hayes.
(In the 5-value decoration scheme I had suggested, your suggestion would
result in inconsistent decorated intervals when the decoration is
0,1,or 2.)
Instead, arithmetic operations involving a bare decoration proceed by
returning the worst case among the decorations resulting from promoting
the bare decorations to decorated intervals in _all_possible_
consistent ways,
(c) §2.4 seems to say that every bi is promoted by giving it the most
*pessimistic* possible decoration part. This is an error. It must be
given
the most *optimistic* decoration.
In retrospect, I think thats probably true.
No, it is definitely false, since it can introduce over-optimism.
The original formulation was chosen for good reasons.
(d) Missing from the present Motion 8 description is the need for
"demotion" as the last stage of an operation. Otherwise if, say, I add
two
of my vectors of 16-byte objects, I end up with a vector of 17-byte
objects. At level 1 & 2, can demotion be ignored? I don't find that
obvious; it is one of the consistency questions I mention below.
According to Motion 8, the bare objects are closed under arithmetic
operations, since bi o bi = bi and bi o bd = bd o bi = bd o bd = bd.
Thus the 16-byte representation never generates a 17th byte.
The stripping operations that remove from a decorated interval
the decoration or the interval (probably depending on configurable
circumstances) are only needed to convert the 17-byte rep. to a
16 byte rep..
A compiler could choose the appropriate stripping based on an analysis
of the final use made of an interval calculation. Thus these final
uses should be analyzed so that the standard can adequately support
compiler writers in this task.
Discussion
----------
We seem to have three kinds of interval arithmetic here:
- "Raw" 16-byte interval arithmetic, in which bare decorations (NaIs)
don't exist. An exception can occur locally to an operation, but these
are
not propagated through a computation because there is nowhere to store
them. This is the underlying arithmetic in terms of which the other two
kinds are defined.
- The enhanced 16-byte arithmetic described above, in which when an
exception occurs, the interval part is discarded and the exception
propagates, "stickily", as a flavour of NaI.
Motion 8 is silent about enhanced 16-byte arithmetic or its
equivalent on level 2.
What _is_ well-defined on the basis of Motion 8 is
only an enhanced 16-byte arithmetic defined on bare objects.
But this will _never_ switch from bare intervals to bare decorations,
since the result of arithmetic operations on bare intervals is always
a bare interval.
The conditions under which one switches, and how, may be different
for different applications. Thus switching modes would have to be
discussed separately if they should be standardized at all.
- Full 17-byte decorated interval arithmetic.
Q1. Nate & Arnold. Am I reaching for the right end of the stick?
In my opinion, yes.
The right direction, but still far from the right details.
Finally, it is not obvious that this exception handling scheme is
self-consistent. I think it is now sufficiently well specified that one
could attempt to define what that means, and prove it.
I think Motion 8 is consistent as it stands; who thinks otherwise,
should point to an inconsistency.
Arnold Neumaier