Re: Bare decorations (was ...level 2 datums)
John Pryce wrote:
In our design, (data-) types are important -- at level 1 or 2 as well as
level 3 -- and we need to choose them with care. At level 1 or 2, a type
is just a set (plus operations). At level 3 it maps to a computer language
type or class. I shall try to distinguish levels by using a style like
"Interval xx" for level 1-2 and "INTERVAL XX" for level 3. I'll use names
like xxd for a decorated interval, xx for a bare one.
As Nate wrote:
At Level 2, there should only be three components:
bare intervals (JDP: type Interval)
bare decorations (NaI with payload) ( type Decoration)
decorated intervals. ( type DInterval)
These are the only Level 2 objects needed for IEEE 1788...
(OK, except level 2 also needs types such as Bit (or Bool) and Tetrit to
handle the pieces of a decoration).
In C-ish notation, we can say DInterval is struct{Interval ivl, Decoration
dec} which is a fancy way to say that mathematically, DInterval is the
cartesian product of the sets Interval and Decoration (and to add some
syntactic sugar). The operations bare(xxd) and dec(xxd) are just the
coordinate projections (xx,d) -> xx and (xx,d) -> d, where xxd = (xx,d).
Right.
Later, Nate wrote:
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.
Yes. The cartesian product model automatically has all those features.
Ok.
This is important: you just agreed that NaI should not be convertible to
empty set, or vice-versa.
Let's write that in stone!
Nate wrote:
In my mind, a bare decoration and NaI are the same thing... what a bare
decoration is meant to be: a NaI carrying a payload of information.
I have a problem here. A bare decoration belongs to the type (=set)
Decoration. An NaI belongs to either DInterval or Interval.
No.
A bare interval is an element of overline-IR. This includes closed real
intervals and the empty set.
A bare decoration is "not an interval", and hence is not an element of
overline-IR.
A decorated interval is a composite object that consists of exactly one bare
interval and one bare decoration.
Mathematically, these 3 types are distinct, non-overlapping sets.
Then this is the source of your confusion.
Bare intervals and bare decorations are the non-overlapping sets.
A decorated interval simply represents a cartesian product between those two
sets, as you agree above.
But when
you get down to the level 3 stuff:
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.
... your dec(X) is stored like a level 3 INTERVAL object (16 bytes in your
example). The only sense I can make of this is that at level 2, it is of
type Interval, and so can take part in arithmetic operations on Interval
datums. If not, why do this?
I think until the confusion is eliminated at Level 2 it is not productive to
try and introduce Level 3 into the discussion.
Let's walk before we can run. :-)
Normally, arithmetic operations act "within" a single type. OK, computer
languages have various ways to broaden this:
- implicit or explicit conversions such as add(binary32, binary64) giving
binary64;
- providing explicit mixed-type operations in the library;
- class inheritance, e.g. make DInterval inherit from Interval or
Decoration.
But every feature like this that we add will complicate one or more of
- the design of 1788,
- its implementation,
- what we have to explain to the user.
People may say "that's down at level 3, or left to the language level".
No, these are squarely level 2 issues, so we need to resolve them.
So lets make sure we have a common understanding at Level 2, first.
Then we will consider mappings into Level 3.
Nate wrote:
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.
I'm OK with that.
Great.
Also, see below.
Nate wrote:
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.
The JDP model is: what is inside an ill-formed decorated interval xxd is
(at level 2) essentially unknowable but bare(xxd) has to return
something, and Empty is a reasonable choice.
If bare(xxd) = Empty, then what's inside an ill-formed decorated interval is
certainly knowable: the interval portion is Empty.
This model is not different from what I wrote above, e.g., the invalid
construction:
DInterval([-Infinity,-Infinity]) =
(Empty,domain:(F,F),continuous:F)
constructs a decorated interval with interval portion set to Empty and all
decorations set to thier "worst" state (domain tetrit: (F,F) and continuous
bit: F).
The confusion is you have been calling this decorated interval NaI. That's
where you go wrong. It is not NaI. It is just a decorated interval, which is
a cartesian product of a bare interval and a bare decoration.
Therefore if X is the decorated interval returned from this invalid
construction mentioned just above, then:
bare(X) = Empty and dec(X) = NaI
In other words, one obtains the NaI by stripping away the bare interval
portion of the decorated interval with the dec(X) forgetful operator.
Similar for "domain" etc.
Conceptually different from your model which says Empty IS inside it, but
functionally, they are the same.
I don't see the difference.
For example, if Y is the decorated interval:
([1,2],domain:(T,F),continuous:T)
and X is the decorated interval mentioned above, then:
X \union Y = ([1,2],domain:(F,F),continuous:F)
X + Y = (Empty,domain:(F,F),continuous:F)
In these examples, I am computing at Level 2 with the decorated intervals.
Note that the interval portions of the decorated intervals propagate the
bare interval results as normal, and the decoration portions propagate the
decoration results as normal.
Note at this point in time, if Z = X \union Y is a decorated interval, then:
bare(Z) = [1,2] and dec(Z) = NaI
In other words, notice that extracting the bare decoration from both X and Z
always results in "not an interval", since a bare decoration is not an
element of overline-IR.
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...
2. User employs dec(X) to extract the bare decoration... continue the
computation only with the bare decoration...
3. User ... just computes with X, the decorated interval. I'm not really
sure that there is much practical use for this case.
[BTW in item 1, my recollection of "such a case occurs in ODEs" is, it
wasn't ODEs, but RBK's example from branch & bound for global
minimisation. One is asking, for x in a sub-box "for those values of f(x)
that ARE defined, are they all definitely worse than my best so far?". If
so, the sub-box can be discarded. RBK is that right?]
Despite the detail you include here, I have BIG problems with this. Item
2's "continue the computation only with the bare decoration" seems to
imply that at level 2 one can do arithmetic on data of type Decoration.
Of course one can do arithmetic on the data type Decoration. This is the
whole point of NaI: that it can be propagated through lengthy computations.
Decoration is a bare decoration, which is "not an interval", because it is
not an element of overline-IR.
Propagating a bare decoration (NaI) through a lengthy computation is the
same as how a NaN will propagate through a lengthy IEEE 754 computation.
It would be quite useless for NaI if this were not the case.
And item 3 seems to me, in one very common style of high performance
computing, the case that will occur oftenest.
I suspect not!
Who wants to compute at Level 3 with a 17-byte datatype!!
Namely large-scale parallel,
e.g. evaluating a function at many arguments "simultaneously" using
vectorised operations like Matlab's a.*b, a./b, etc. You may well start by
constructing a million sets of interval arguments from non-interval data.
A thousand of them may be ill-formed, but you just want to go ahead and
evaluate, and ask questions afterward.
This is why propagating only the bare decoration (NaI) instead is essential,
at least for certain types of applications and/or computations.
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.
So a level 2 bare decoration has a double meaning. It is NaI, but also one
can reconstruct the original DInterval X from its bare() and dec()
components. This scares me.
It shouldn't. And its not a double meaning.
Examine the definitions above and you will see so.
A decorated interval is just the cartesian product of a bare interval and a
bare decoration.
You have already agreed previously in this e-mail that you have no problem
with a constructor for a decorated interval that takes as input a bare
interval and a bare decoration. So your expression of concern here is a
contradiction.
Nate wrote:
Now lets shift the focus from Level 2 to Level 3...
... 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.
You may well be right here, but I won't say yea or nay till I understand
your model better.
Nate wrote:
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...
Here we agree 100%. I will put it my way, which leads on to my efficiency
concerns:
But also pay attention to recent e-mails between myself and Arnold Neumaier
regarding the "isValid" bit, i.e., that decoration bit is redundant and no
longer needed. It is subsumed by the (F,F) state of the "domain" tetrit.
Let's suppose that the decorations comprise "domain" tetrit and
"continuous" bit. Plus we are going to support the "well/ill-formed"
concept. Then at level 2:
typedef (something) Interval; //bare interval
typedef struct{Tetrit d; Bit c;} Decoration; //bare decoration
typedef struct{Interval ivl; Decoration dec} DInterval; //decorated
interval
/* previous line doesn't catch NaI aspect, for which see the P.S. */
At level 3, we include the "well-formed" bit in the decoration:
typedef (something) INTERVAL;
typedef struct{TETRIT d; BIT c; BIT w} DECORATION; //w is "well-formed"
bit
typedef struct{INTERVAL ivl; DECORATION dec} DINTERVAL;
Now part of the brilliance of the decoration concept, as I understood it
in Motion 8, is that tracking well-formedness is trivial:
DINTERVAL OP(some DINTERVAL arguments XXD1, XXD2, ...) {
do bare interval version of OP on .ivl parts of arguments;
do whatever is needed on .dec.d and .dec.c parts of arguments;
form logical "and" of .dec.w parts of arguments; //costs essentially
nothing
pack up result and return
}
So the decorated interval code can incorporate the bare interval version
of OP without change (except to handle the "domain" and "continuous" stuff
which is also pretty trivial). No extra tests are needed to handle the
"well-formed" aspect. This should run fast.
BY CONTRAST, your proposal to have an NaI-ish object that might be encoded
as [sNaN, sNaN] in the [lo,hi] storage of a bare interval, seems to slow
the code down by requiring an extra "if" test inserted in every operation.
Possibly, but this will likely be much more efficient that trying to
propagate 17-byte datatypes through a sophisticated program.
If it weren't for the deocrations to be stored in the NaNs, it would be
absolutely no overhead, e.g., if X=[1,2] is a bare interval and Y=[NaN,NaN]
is a bare decoration, then the operation X+Y gives:
[1,2]+[NaN,NaN]=[NaN,NaN]
which is exactly the propagation semantics of a bare decoration as described
in Motion 8, i.e., any arithmetic operation involving a bare decoration must
yield a bare decoration.
Some recent discussions with Michel Hack and Dan Zuras have pointed out it
might be better to try representing the NaI as [NaN,bits], where "bits" can
be any arbitrary collection of bits. In this case, "bits" would contain the
decoration bits for "domain" tetrit and "continuous" bit, etc.
In any case, the point of decorated intervals and bare decorations is to
allow implementors, vendors and language committees to choose whichever
approach is best for thier particular application.
For example, a hardware vendor designing an interval processor could easily
put the decoration into the NaN payloads and perform:
[1,2]+[NaN,NaN]=[NaN,NaN]
to give the correct results (i.e., that the NaN payloads could propagate
correctly).
This may or may not work on _existing_ IEEE 754 hardware, as has been
previously pointed out. But nothing's stopping a vendor interested in
producing a fast interval processor from doing this, at least according to
Motion 8.
In any case, the important point is this: if IEEE 1788 mandates only one
solution -- which you appear to be making an effort to do -- then vendors no
longer have any choice and will be forced into Level 3 implementations that
might seriously degrade or jeapardize the performance of thier application.
My impression of the proposed "computing paradigm" that Motion 8 offered
for decorations is:
- We should use bare intervals, whose operations are usually faster, in
parts of a program where exceptions can't occur or don't matter.
- We should use the slightly slower decorated intervals, for safety,
elsewhere. In particular we should always use them when constructing
intervals from non-interval data: i.e. constructors of bare intervals
should not be provided.
What I am hearing now seems to contradict this paradigm
No.
so there is
something I am not understanding.
That much is abundantly clear to me. :-)
I'm doing my best to help bridge this gap. I hope this recent round of
comments help. FWIW, I _do_ see we are making progress. :-)
Nate Hayes