Bare decorations (was ...level 2 datums)
Folks,
I'd like to take some time to talk about bare decorations. I apologize in
advance for the length of the e-mail. I've done my best to not ramble and
keep it focused.
In my mind, a bare decoration and NaI are the same thing. Back when Motion 7
was being voted on, many of the "no" votes at the time were because people
not only wanted NaI, but they also wanted NaI to carry a payload of
information. This is essentially what a bare decoration is meant to be: a
NaI carrying a payload of information.
When thinking about bare decorations it is important to keep in mind a
separation between the Level 2 objects and the Level 3 representations. So
let me first just sick to Level 2.
At Level 2, there should only be three components:
bare intervals
bare decorations (NaI with payload)
decorated intervals.
These are the only Level 2 objects needed for IEEE 1788. Bare intervals are
the elements of overline-IR, and this includes the empty set. Bare
decorations are just a collection of bit and tetrit attributes such as the
"domain" tetrit and the "defined and continuous" bit (or perhaps the
"discontinuous" bit, pending outcome of voting), etc. Decorated intervals
are a composite object comprised of a bare interval and a bare decoration.
If X is a decorated interval, there are two forgetful operators: bare(X)
which returns the interval portion of the decorated interval (as a bare
interval) and dec(X) which returns the decoration portion of the decorated
interval (as a bare decoration).
At least two constructors for decorated intervals should exist. One
constructor should accept both a bare interval and a bare decoration as
input. Another should accept only a bare interval. In this latter case, the
decoration portion of the decorated interval can be inferred from the bare
interval input.
Say a user tries to construct a decorated interval with some invalid inputs.
For example, say they try to construct from [-Infinity,-Infinity]. In this
case, the interval portion of the decorated interval should be set to Empty,
and the decoration portion of the decorated interval should be set so that
all bit and tetrit attributes are at their worst state, i.e., the "domain"
tetrit would be set to (F,F) and a "defined and continuous" bit would be set
to F, etc.
Now, if X is this decorated interval mentioned above (created by an invalid
construction), the user has three options:
1. User employs bare(X) to extract the bare interval portion of X (which in
this case is the empty set) and then perform a computation with the bare
interval. This can be useful in algorithms or sections of code where it is
known there are no exceptions, or where it is known something like division
by zero might occur but the algorithm does not want to treat this as an
exception (such a case occurs in ODEs, as I gather from private discussions
with John).
2. User employs dec(X) to extract the bare decoration portion of X and then
continue the computation only with the bare decoration. This is useful in
branch-and-bound algorithms. Once an exception occurs, a branch-and-bound
algorithm no longer needs any bare intervals. However, it is really
important that the decoration bits and tetrits in the bare decoration
continue to propagate through the computation. Note that as they propagate,
according to Motion 8 it is even possible that the decorations might change,
i.e., get "worse". This is by design, and will allow the branch-and-bound
algorithm to make more optimal choices about how to delete interval boxes,
etc. In this case, it is critical that the bare decoration can never be
"absorbed" or lost in the propagation. For example, it should never be
possible that the bare decoration can somehow be turned into an empty set,
or the like.
3. User does not use bare(X) or dec(X) but instead just computes with X, the
decorated interval. I'm not really sure that there is much practical use for
this case.
One important thing to notice about this Level 2 model is that while it is
possible to strip away the interval or decoration portion of a decorated
interval using either the bare(X) or dec(X) forgetful operators, its not
appropriate to consider that the interval portion of a bare decoration could
be "stripped away," or similarly that the decoration portion of a bare
interval could be "stripped away." Also, its not appropriate that there
should be some conversion from a bare interval to a bare decoration or
vice-versa.
But it is always possible that a decorated interval X can be explicitly
constructed from either (a) a bare interval or (b) a bare interval and a
bare decoration. Only then can the bare(X) or dec(X) operators be employed.
Note that there is no way to construct a decorated interval from a bare
decoration. This is by design (see section 2.3 of Motion 8.02), and is to
ensure safety and reliability. For example, it is the only way to guarantee
in option 2 described above that the bare decoration will propagate though
the remainder of the branch-and-bound computation. If users don't like this,
they can always explicitly construct a decorated interval from a bare
interval and a bare decoration.... I say "explicitly" because the user must
in that case specify the bare interval (as well as the bare decoration). But
it should not ever be the case a decorated interval is constructed only from
a bare decoration.
Now lets shift the focus from Level 2 to Level 3. To keep things simple, I
only consider the Level 3 case of an inf-sup decorated interval:
X=([lo,hi],bits)
where "lo" and "hi" are each 64-bit IEEE 754 doubles and "bits" is a
one-byte integer storing all the decoration attribute bits and tetrits,
i.e., "domain" tetrit, "defined and continuous" bit, etc.
All-in-all, the decorated interval X requires 17 bytes of storage. In the
case of the forgetful operator bare(X), we have:
bare(X) = [lo,hi]
i.e., the "bits" byte is discarded leaving only the 16-bit Level 3 bare
interval [lo,hi].
Note that in order to confrom to the Level 2 model, the Level 3 bare
interval [lo,hi] can only be an element of overline-IR. In other words,
[lo,hi] must either be a valid closed and non-empty interval or else the
empty set. I agree with suggestions from many people in the forum that if
[lo,hi] is the empty set, it is probably best to encode this at Level 3 as a
pair of quiet NaNs.
However, what happens at Level 3 when the user employes the forgetful
operator dec(X)? It would seem this might give:
dec(X) = bits
i.e., it might seem the result of dec(X) would be a one-byte integer
containing all the decoration attributes of X.
Well, that _might_ actually be the right choice for certain implementations.
However, I suspect another choice that will be better for many types of
implementations is that
dec(X) = [SNaN,SNaN]
retuns a pair of signaling NaNs. In this case, the decoration "bits" of X
are stored in the payload of the signaling NaNs.
This is the one place I think John's current paper begins to go off-track
and needs some change, e.g., there should not be a special [lo,hi] Level 3
representation that somehow represents NaI "all by itself," where the NaI
doesn't carry any of the decoration attributes of X.
There really should only be two categories of "NaN-like" IEEE 1788 objects
at Level 3: the empty set (represented by pairs of quiet NaNs without any
specific payload) and bare decorations (represented by pairs of signaling
NaNs with decoration bits stored in the payload).
There is no need for a "third" category of "NaN-like" objects in IEEE 1788.
Note that in this regard, the "illform" bit is not a Level 2 concept! It is
only at Level 3 that such a thing is really necessary: to distinguish the
two "NaN-like" objects of empty set (quiet NaNs) from bare decorations
(signaling NaNs).
However, even at Level 3, the "illform" bit is implicit in the distinction
between quiet and signaling NaNs. And even this much is
implementation-specific. For example, it may be possible that some other
IEEE 1788 implementation does not have NaNs and will use some entirely
different way to distinguish between empty set and bare decorations. So in
this regard, I'm quite skeptical that "illform" should be standardized as a
concept, even at Level 3.
For P1788, I think it is sufficient that at Level 2 there shall only be bare
intervals, bare decoration, and decorated intervals (along with the various
constructors and forgetful operators discussed in the mail). At Level 3, it
is only necessary to require that a vendor shall provide a representation
for the empty set and for bare decorations.
Sincerely,
Nate Hayes