Re: Bare decorations (was ...level 2 datums)
Nate, P1788
On 6 Oct 2010, at 16:10, Nate Hayes wrote:
> 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.
Nate, thank you for this careful explanation. I think the agreement between us -- over what the relevant level 2 entities are, how they can be constructed and decomposed, and how this might map to level 3 -- is about 90%. Our 10% differences are maybe quite subtle, but important. I hope we can draw on the collective wisdom of many people in the group to resolve them.
My main points, elaborated below, are
- You give "bare decoration" two meanings that seem contradictory to me.
- I am getting contradictory messages about efficiency.
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).
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.
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. Mathematically, these 3 types are distinct, non-overlapping sets. 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?
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.
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.
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. Similar for "domain" etc. Conceptually different from your model which says Empty IS inside it, but functionally, they are the same.
> 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.
And item 3 seems to me, in one very common style of high performance computing, the case that will occur oftenest. 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.
> 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.
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:
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.
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, so there is something I am not understanding.
Regards
John Pryce
P.S. I wrote the inadequate definition that a level 2 decorated interval is a
struct{Interval ivl; Decoration dec}
What I really envisage is something like
taggedUnion{
struct{Interval ivl; Decoration dec} // normal decorated interval
void // ill-formed interval
}
I think taggedUnion's are provided by Ada, but not by C/C++.