Re: Bare decorations (was ...level 2 datums)
John Pryce wrote:
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,
This couldn't be further from the truth.
I understand that you are trying to invent a different Level 2 mathematical
model than Motion 8.02. One that has questionable and dubious properties, in
my mind.
Rightly or wrongly, I also have the perception your motivation for doing
this is based on a notion of some particular Level 3 implementation that you
have in mind. This comes from the observation that the bulk of your Level 2
examples and arguments are expressed in terms of bits, bytes and lanugage
bindings. I've yet to hear you clearly formulate your position purlely in
Level 2 terms.
This leaves me skeptical that you have such a Level 2 model in mind.
I believe P1788 should be working in the opposite direction, i.e., that the
Level 3 implementations and representations should be derived as a
consequence of a clearly formulated Level 2 model.
hence emotions tend to get
involved because we can't "prove" one choice is objectively best.
Oh, I think this can all be proven.
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.
My understanding is that a "format" is a Level 3 concept (see below), hence
from my perspective you're already off-topic.
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;
The type "Real" is some some language binding concept.
IEEE 754-2008 specifies "floating-point data" at Level 2. NaN is distinct
from the set of finite numbers, as well as +- Infinity (hence the "unions"
depicted in Table 3.1).
clause 3.3 states:
"A floating-point datum, which can be a signed zero, finite non-zero
number, signed infinity, or NaN (not-a-number), can be mapped to one or more
representations of floating-point data in a _format_."
Emphasis is mine: "format" is Level 3. Hence, the Level 2 floating-point
datums are mapped to Level 3 formats.
Thus, I see you are conflating Level 2 and Level 3 concepts (and even
conflating Level 3 representations with language bindings), particularly
when you say things like:
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".
Where "double" is a language binding of a format, neither of which are Level
2 concepts.
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.
This doesn't make any sense: this means NaI is an element of overline-IR.
How can something that is "not an interval" be an element of the set of
"valid intervals"?
Just as in
754, which put NaN, as well as numbers, into the level 2 set Real. A
design choice.
No. YOU put NaN into Real, and "Real" in this case is actually a language
binding of a format, neither of which are a Level 2 set.
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.
On the contrary, I see this is ambiguous and raises all kinds of doubts.
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.
As it should be (at Level 2).
Just like 754-2008 NaN is "not a number" because at Level 2 it is not a
member of the set of finite floating-point data or the set of infinities
(subclause 3.3).
It is intersting to note that if IEEE 754-2008 also had the concept of a
decorated number, then it would be consistent with the Motion 8.02 Level 2
model:
-- bare numbers would be R*, i.e., the reals and infinities
-- bare decorations would be the NaNs
-- decorated numbers would be the cartesian product between bare numbers
and bare decorations
-- if X is a decorated number, bare(X) would return an element of R* and
dec(X) would return NaN
-- arithmetic operations on bare numbers and bare decorations would be
as they currently are specified in IEEE 754-2008
-- note that in this case, binary64 is not a bare number: it is a Level
3 format which may represent either a bare number or a bare decoration
All of this is consistent with (and analagous to) Motion 8.02.
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.
Yes I have. Repeatedly:
NaI is not an element of overline-IR, and hence is "not an interval."
Only at Level 3 is a pair of doubles possibly interpreted as representing
either a bare interval or a bare decoration, just as in the analagous
example above "binary64" is a Level 3 format possibly representing either a
bare number or a bare decoration (had IEEE 754 used a decorated number
model).
You are the one advocating NaI should actually "be an interval" at Level 2,
which is quite a strange concept, if you ask me.
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).
Requiring only decorated intervals will be a huge negative performance
impact for most interval applications, particularly since it is hardly the
case that applications need both the bare interval and bare decoration at
the same time once an exception occurs.
Thus, you force implementors and users alike to compute with a 17-byte
datatype that always drags the bare interval along, even when it is no
longer needed, i.e., in cases when a bare decoration represented at Level 3
as [NaN,NaN] or the like would be much more practical and efficient...
especially with the proper hardware support.
By analogy, it would be like saying only a 9-byte decorated number could be
used to represent NaNs in IEEE 754, had it decided to use a decorated number
model. In other words, its like saying that an IEEE 754 NaN would in that
case always drag an element of R* along with it. Quite a waste indeed, since
using an 8-byte binary64 to represent the NaN at Level 3 is not only
perfectly adequate: typically its all thats required, as decades of
computing with NaNs that do not drag an element of R* along with it shows.
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.
I am not shouting NO.
I agree.
I co-wrote Motion 8.02, which requires decorated intervals.
Don't you remember?
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.
Correct.
AS I HAVE SAID REPEATEDLY:
the invalid construction
yy = DInterval(-Inf,-Inf)
should be the DECORATED INTERVAL:
(Empty,domain:(F,F),continuous:F)
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.
See above (as well as previous e-mails).
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.
I see this is your view.
But I don't see your view is correct.
...
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 = ??
I have already explained this in my previous e-mails.
By Motion 8.02, subclause 2.3, the result will be (at Level 2) a bare
decoration (NaI).
or if that's not allowed,
It might be the case we do not want to allow this at Level 3.
> bare(xx) + dd % kosher bare interval plus NaI
ans = ??
This is also a bare decoration (NaI) for the same reason.
This needs to be allowed at Level 3.
Your efforts to abolish this would, in my view, be a fatal mistake.
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.
Motion 8.02 already gives the core semantics.
And I have already given more detailed explanations in recent past e-mails
on this topic.
So from my perspective, it appears you are asking me to repeat myself.
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.
I would not use a 17-byte datatype in my software or products.
...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.
John, by proposing that P1788 should abolish bare decorations, you are
"mandating only one solution," namely that any computation involving
decorations will require a 17-byte Level 3 format.
I don't oppose that people can compute with a 17-byte format if they wish.
But it is overkill for the vast majority of interval algorithms and
applications that I'm aware of.
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.
Absolutely not.
You are proposing that NaI may be converted to Empty (among other strange
things), which is akin to IEEE 754 allowing some arithmetic operation on a
NaN to produce a non-NaN result.
I would not trust (or use) an IEEE 1788 standard with those semantics.
- That is not the case for Nate's HNaI as he has explained it so far.
Oh, contraire...
Motion 8.02 bare decoration has the same semantics as IEEE 754-2007 NaNs.
This is by design. In addition, cartesian products of bare intervals and
bare decorations may be formed to construct decorated intervals. This latter
concept is unique to Motion 8.02 and does not exist in IEEE 754. However, if
it did, it would be a direct analogy.
Nate Hayes
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>