Motion P1788/M0015.01 NO
P1788
I have concluded that I cannot support motion 15 in its present form so I vote No. Our rules say No-voters should state the changes that would make them vote Yes, so here goes, below.
John Pryce
A. Forenotes
---------
1. I am trying out the term "prit" -- short for "property digit" -- to mean a bit, trit, tetrit, octagit, etc., describing a property in a decoration. Dan wonders if it sounds kinda indelicate. Your views are welcomed.
2. Dan is not happy with the prit name "valid", which to him relates to the 754 "invalid operation" flag. In the next revision of the standard text I propose to change this to "wellFormed" (as an identifier) and "well-formed" with negation "ill-formed" (in running text).
B. Executive summary
-----------------
1. If passed, the motion forces all prits to be, at least conceptually, octagits (encoded in 3 bits) carrying both "latest operation" (non-sticky) and "history" (sticky) data. It also forces each prit to be a "pointwise" property, i.e. it to be based on a predicate P over points x and for an interval xx defines
PTrue = (exist x in xx) P(x) and PFalse = (exist x in xx) !P(x)
where ! is negation.
2. Of all actual prit applications so far propounded, none requires this.
- "well-formed" (was "valid") needs one sticky bit.
- "defined" and "continuous", for fixed point theorem applications,
need one sticky bit. Extending them, as needed by Nate, is no problem.
- "defined", for Nate's branch and bound applications, needs a sticky
trit or tetrit. He may need the same for "continuous", I'm not sure.
- "bounded", in the meaning I think it originally had in Motion 8, needs
one non-sticky bit. (I hope we dump this prit, for reasons I've said.)
- Dan has proposed a prit "range" or "inRange", with both a sticky and
a non-sticky component, but I'm yet to be convinced of any practical
applications.
3. We want a definition of prits that covers what is actually considered useful, rather than forcing into a fixed mould.
4. The topic at hand, of exception-handling, is probably the most abstract and complex of all the issues we have to handle in this standard. It would be all too easy to choose a mechanism just because it looks elegant; or that applies nicely to one application and is clumsy or useless for others; or that is over-specified or under-specified.
So we need all the practical examples we can muster, to test our chosen scheme against.
5. Section D suggests that most actually needed prits are (a) bits, (b) sticky; and it may be possible to make ALL of them so.
C. What would make me vote Yes
---------------------------
1. Allow a decoration to contain prits of different sizes (bit, trit, etc.)
2. Define non-sticky & sticky. Allow prits to be of either kind, or to be a mixture (though I'm skeptical of this last kind's usefulness).
3. Say that a prit's name should indicate its "hoped-for" or "normal" value, e.g. "defined", rather than the opposite.
4. Define the concept of ranking a prit's values, since this seems crucial to the handling of stickiness. (Nate describes this for trits & tetrits for his branch & bound; but his scheme may not work for other applications.)
5. To make me vote Yes enthusiastically, have an extended Rationale which lists examples, offered by the group, of practical application of prits. It does not need to say which prits _should_ go in the standard; that's for later. It does need theoretical justification, as e.g. Nate gives in his example of branch & bound usage.
D. Some detail
-----------
Some examples of decorations that HAVE been discussed:
- "wellFormed" (was "valid")
Purpose: Record correct construction of interval.
Pointwise property: No.
Storage needed: A single, sticky, bit.
Comment:
(a) Ill-formed interval is result of a constructor with bad input, or
of any operation with an ill-formed input.
(b) I claimed there was no point in having a "possiblyWellFormed" value,
and no one has contradicted this, I believe. So one bit will do.
- "continuous"
Purpose: Check function is everywhere continuous on input xx,
for use in fixed point applications.
Pointwise property: Yes.
Storage needed: A single, sticky, bit.
Comment:
On 16 Apr 2010, at 02:39, Corliss, George wrote:
> I still wonder whether propagating ONLY the sticky decorations might be enough. If I write an interval algorithm using a Fixed Point Theorem applied to a function f, all I care about is that f is continuous on the interval \x. If it fails to be continuous, I really don't care where. I THINK sticky decorations are all I need for that.
I agree.
- "defined" 1
Purpose: Check function is everywhere defined on input xx,
for use in fixed point applications.
Pointwise property: Yes.
Storage needed: A single, sticky, bit.
(As with "continuous")
- "defined" 2
Purpose: Check if, on xx, function is defined everywhere,
or nowhere, or at some points & not others,
for use in branch & bound applications.
Pointwise property: Yes.
Storage needed: A sticky trit or tetrit.
Comment:
Nate, can this be thought of as two independent sticky bits? One for "everywhere defined", the other for "somewhere defined". If the first succeeds you have a definite accept. If the second fails, a definite reject. Otherwise bisect & recurse. Does that meet the needs of your B&B?
- "bounded" 1 (its original meaning in motion 8.)
Purpose: Say if interval, stored as unbounded, is actually
known to be bounded, e.g. exp([0,309]) in binary64.
Pointwise property: No.
Storage needed: A non-sticky trit.
"bounded" 2 Dan's version
Purpose: Check that conceptually, overflow never occurred in the
computation path leading to an interval.
Pointwise property: Yes.
Storage needed: A single, sticky, bit.
Comment:
I think Dan's idea is this. For each (elementary) interval operation ee(xx), let e be the corresponding point operation. Set the sticky bit if |e(x)| > (overflow threshold), for any x in xx, in the current precision. Dan, did I get it right?
My query is whether this has practical uses.
Some other comments.
Nate has written a useful paper discussing tetrits:
On 24 Apr 2010, at 20:11, Nate Hayes wrote:
> I believe a priority mapping, as outlined in my position paper, is required
> to overcome this difficulty and integrate the very nice idea of tetrits into
> a reliable exception handling mechanism consistent with Motion 8 semantics.
> Although I have made a position paper available, there has not been any
> discussion about it in the short time before the current motion.
I'm not the only person wondering about "most recent operation" data:
On 24 Apr 2010, at 20:11, Nate Hayes wrote:
> I'm a little skeptical that we really need to partition decorations into
> "most recent operation" vs. "history," but if there turns out to be a
> compelling reason to do this, and if the collective wisdom of P1788 decides
> to go down this path, then I believe we need a total of 4-bits:
Things Michel Hack's has written suggest we should consider including (local copies of) IEEE-754 flags among our decorations:
On 15 Apr 2010, at 19:52, Michel Hack wrote:
> Nate Hayes replying to Ian McIntosh replying to RBK:
>>>> Do we need both the sticky part and the non-sticky part? (RBK)
>>> I don't think so, if we handle it carefully. (IM)
>> I agree with you, Ian. (NH)
>
> Careful here. What Ian said was that some programs care about the
> sticky part, and some care about the details of the last operation,
> but rarely would a program care about both AT THE SAME TIME.
>
> In fact, programs DO care about both, at SEPARATE times. A common
> situation is a fast path that expects no exceptional cases, but
> checks this assumption with a sticky check at the end so as to
> repeat the routine using a slow but thoroughly-checked sequence.
> ...
I wasn't sure from the above whether Michel envisaged repeating the SAME CODE in some sort of debugging mode. But the following indicates he was thinking of executing DIFFERENT CODE if the sticky check failed.
On 26 Apr 2010, at 20:07, Michel Hack wrote:
> John Pryce wrote:
>> (a vectorized calculation of)
>> c = sqrt(a^2 + b^2) (*)
>> where there is a problem when one or both inputs
>> are very large or very small. Then you would do
>> compute c by (*)
>> if overflow or underflow occurred {
>> re-compute c by a careful algorithm
>
> Yes, that's precisely what I had in mind, especially in the
> vector case. If the exceptions are expected to be rare, it
> pays to let it run at full speed -- especially if there is
> a vectorized exception summary as well (as we would like to
> see for interval decorations)...
If this is an interval calculation, cc = sqrt(aa^2 + bb^2), over/underflow shows up as bounds going to oo or 0. I guess it's easy for an implementation to ensure the 754 flags are set in a sensible way (in this case by "square" and "+") so that they could be copied to a decoration if felt useful. Is that right Michel?
Ian Macintosh's contributions offer possible practical examples to include in the Rationale I am seeking.