Re: Bare decorations (was ...level 2 datums)
Nate, P1788
This is in response to Nate Hayes' email of 13 Oct 2010, at 14:55.
Despite the large overlap between us on "what are the level 2 datums?" the disagreements are ... let's say "significant". Much of what we disagree on is about design, which is a matter of choice, hence emotions tend to get involved because we can't "prove" one choice is objectively best.
Some of our basic assumptions differ so we come to different conclusions. I'll try to avoid the word "confusion".
Consider 754 floating point. Let Real denote a particular level 2 format. According to 754 Table 3.1, Real IS a set comprising finitely many members of the extended reals R*, together with one thing called NaN, distinct from any extended-real number. (qNaN versus sNaN, and payloads, are invisible at this level of detail.)
That is,
NaN is a value of type Real; equivalently, NaN is a member of the set Real;
just as much as are 0, 1, 3.625, etc. Computer languages agree on this, e.g. if I ask Matlab to tell me the class of a default NaN, I get the answer "double".
Nate wrote:
>> 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.
> John wrote:
>> 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 [JDP: I call it IRbar] . 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.
Yes at level 1, where a bare interval is an element of IRbar.
NO!! at level 2, where, in my design, it is either that or NaI. Just as in 754, which put NaN, as well as numbers, into the level 2 set Real. A design choice.
It is our choice whether to add NaI to our level 2 set Interval. And whether to add a corresponding datum, which I call DNaI, to the level 2 set DInterval = (Interval cross Decoration) of decorated intervals.
IF we do either of those things, there is no ambiguity:
NaI will be a datum of type Interval.
DNaI will be a datum of type DInterval.
Nate's bare decoration (I'll call it Hayes-Not-an-Interval, or HNaI) seems to have inherently different semantics from mine. E.g. it is DERIVED from a DInterval by the dec() function but is NEITHER in the set DInterval NOR in the set Interval.
We could "deem" it to be in either of these sets, by mathematical fiat or construction at level 2 (see <math> below), and by various mechanisms at the language level. But Nate has never clarified whether this is to be done.
In my position paper I said I preferred not to have bare-interval NaI (on performance grounds, but I may have read the trend of the relevant discussion wrongly).
But we need DNaI [Nate, you may be shouting NO! but bear with me], because we need decorated-interval constructors, and we have to return _something_ when construction goes wrong. Suppose Matlab is used (so there is no "compile time", any relevant errors happen at run time). Construct a valid interval:
> xx = DInterval(-Inf,-1) % we expect something like
xx = DInterval [-Inf, -1]
> class(xx) %we shall expect
ans = DInterval
Now what about
> yy = DInterval(-Inf,-Inf) % what do we expect now?
yy = ??
> class(yy)
ans = ??
Your average user will be surprised if the displayed yy isn't something that tells her yy is a DNaI; and surprised if the displayed class is anything other than DInterval.
That's at the language level. Surely it's perverse to specify different behaviour at level 2, which defines the theory on which the language level is based?
Nate, what do you want the two ?? to look like? An answer to that may be the key to bridging the gap between us.
Nate wrote:
> 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.
As you see from above, my view is that this is where _you_ go wrong.
> ...
> bare(X) = Empty and dec(X) = NaI
... or HNaI as I call it. Continuing the Matlab example, suppose I do
> dd = dec(yy);
> class(dd) % surely the answer is
ans = Decoration
You say dd is an NaI, which to me means it can take part in arithmetic operations with decorated or bare intervals -- by analogy with NaN in 754. So what is the result of
> xx + dd % kosher decorated interval plus NaI
ans = ??
or if that's not allowed,
> bare(xx) + dd % kosher bare interval plus NaI
ans = ??
The language must mirror the level 2 semantics, else there is no point to level 2. So again an answer to this question will clarify our respective positions.
Nate wrote:
>>> (Nate) 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...
>> (John) 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.
No problem. I think my theory can handle that by adapting the <math>...</math> below. Same with Arnold's latest five-state decoration (pentit?).
Nate wrote:
>> 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.
I think Michel Hack and others told us that modern compilers can handle 17-byte datatypes efficiently by storing the 16 bytes and the 1 byte separately -- especially in the case of large DInterval arrays -- even though they are conceptually one object.
> ...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.
I absolutely am NOT trying to make 1788 "mandate only one solution" at level 3 or 4. Implementors should be left free to realise level 2 semantics as they see fit.
Summary.
- My NaI or DNaI arises in a running program for different reasons from floating point NaN. But its behaviour is exactly analogous to that of NaN, which makes it conceptually simple.
- That is not the case for Nate's HNaI as he has explained it so far.
Regards
John Pryce
<math>===================================
Here is a rigorous way to construct "IRbar with NaI added" call it IRbar', which doesn't just add NaI "by fiat". Let bool = {0,1}, and let Z be the cartesian product (IRbar cross bool). On Z define the equivalence relation ~ that says
(xx,a) ~ (yy,b) iff (1) xx=yy and a=b, or
(2) a=b=0.
Then IRbar' is the set of equivalence classes of ~. These consist of:
- For each xx in IRbar, the equiv class of the element (xx,1) of Z.
- The equiv class comprising all (xx,0) for xx arbitrary.
If we write EC for the map from a member of Z to its equiv class then
- We identify xx with EC((xx,1)) for any xx in IRbar.
- EC((xx,0)) is named NaI.
Hence IRbar' "is" IRbar with NaI added.
Clearly the same idea works with IRbar replaced by a finite subset of IRbar; or by a set of decorated intervals; or indeed by any set whatever.
Note 1. This is a self-serving piece of maths because it supports my view that what bare interval is inside NaI is unknowable: as Schroedinger's cat is a superposition of "dead" and "alive", so NaI as constructed here is a superposition of all possible (xx,0).
Note 2. But one can always select one "representative" of an equiv class to stand for the whole class. If one selects (Empty,0), this gets back to Nate's (equally good) view that Empty is what's really inside NaI.
Note 3. This construction maps straight onto the level 3 representation of "well/ill formed" by a decoration bit. Namely for (xx,a) in Z, a is the "well-formed" bit.
===================================</math>