| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
P1788
This replaces Motion 58, item 3.
There is a nettle that must be grasped, that I have called the "Flavors Level 1 -> Level 2 problem". I had hoped it might "go away". But when one gets down to details of conformance, it can't be avoided, so I pose the problem for group discussion before making a motion.
Outline
=======
We need to make the standard more prescriptive about what a flavor is. Not to do so would dilute its essential nature set out in §5 "Structure of the standard in levels", especially Table 5.1.
IMO, either
(A) A flavor always has Entire as an interval, and Entire belongs to every interval type (as in the set-based flavor). If so, neither classical Moore arithmetic, nor Kaucher arithmetic as originally put forward by Nate Hayes, can be a flavor. Or
(B) We permit a flavor not to contain Entire, but we define a new mandatory exception called, say, IntvlOverflow. This is signaled at Level 2 when the Level 1 result of an operation "overflows", i.e. is too large to be enclosed in any interval of the destination type T.
As regards what 1788 *requires*, one can mix-and-match (A) and (B) in various ways. E.g. it might say a flavor *should* do (A) but if it doesn't, it *shall* do (B).
More detail
===========
Key features of 1788 are that
- A Level 2 interval result of an operation is got by enclosing the
exact Level 1 result in an interval of some Level 2 type T
-- the Level 1 -> Level 2 map in Table 5.1 *exists*.
- A Level 2 interval (ignoring its tag) *is* a Level 1 interval
-- the Level 2 -> Level 1 map in Table 5.1 is the *identity map*.
I believe this should apply to every flavor. If so,
(1) A Level 1 notion of *contains* for intervals must exist in every flavor
-- a partial order, identical to "set-contains" for common intervals.
(2) A Level 2 notion of *type* (a finite set T of intervals) must exist in
every flavor, to enable a sensible, well-defined choice of enclosing
interval in finite precision.
(3) It is then natural to require the notion of *interval hull* -- a minimal
enclosing T-interval chosen by "some algorithm", provided *some*
enclosing T-interval exists.
All of these are absent from the core behaviour of flavors, right up to draft 8.1 of Oct 25th.
An easily proved fact is the following. Write F-contains for the contains relation in flavor F.
Theorem
-------
If in flavor F
(i) every interval (common or not) is F-contained in some T-interval, and
(ii) at Level 1, convexHull(xx,yy) F-contains xx and yy for arbitrary
intervals xx, yy,
then there exists a unique interval Entire that F-contains every interval.
Moreover Entire is a T-interval.
-------
A flavor for which (ii) fails is rather weird -- should it be a requirement on convexHull()?
So basically this says that if the flavor is sensible then for any interval type T
T-hull is defined for every Level 1 interval <==> Entire exists and is a T-interval.
I attach a revised §7.1, written after discussion with Christian, Dmitry and Michel. Compared with the Oct 25 text, note the more precise initial paragraphs, and new items (ii) and (v) of the list.
I also append a couple of extracts from the email discussion so far.
Before I can submit a motion on this, IMO we must decide: Do we choose to require (A) or (B) above, or some combination?
John Pryce
Attachment:
20131120Clause7FlavorsIntro.pdf
Description: Adobe PDF document
--------------------------------------------
On 2013 Nov 15, at 16:40, Michel Hack wrote:
>> (1) a "contains" relation shall exist;
>> (2) a "hull" operation shall exist;
>> (3) the notion "interval type" shall exist at Level 2.
>
> I would say you need both (1) and (2). We already have (3) from
> Clause 5: Each mathematical interval has a unique interval datum
> as its T-hull -- a minimal enclosing interval of that type. This
> is with respect to a flavor-dependent meaning of "contain" -- but
> it must exist.
>
> However, I think the premise that led to this emergency question
> cannot hold:
>>> But that ignores the problem of *overflow*: the possibility that
>>> in a given Level 2 type of flavor F, there is no y' containing y.
>>> E.g., for standard Kaucher intervals, this is possible, as they
>>> don't have an Entire. What should be done?
>
> See Clause 5: the T-hull must exist! This also impacts Clause 6:
> you could not have an FTIA without this. This is also why we require
> the number formats to include the signed infinities.
Michel has put his finger on it. In effect I was asking
(**)
"Can we discard some of §5 and still keep the essence of the standard?"
> I suppose that one way out of this would be forced termination upon
> encountering overflow in a flavor that does not include unbounded
> intervals -- to make sure that the containment failure can never be
> observed by the program!
Yes
> Conceivably this could be an interceptable
> exception, in some implementations.
Isn't this true in *most* implementations? E.g. in C++ or Java, can't
a user program intercept *any* exception with a "catch" clause?
> My impression however was that the Kaucher flavor envisioned by Nate
> Hayes does include support for unbounded intervals and a valid FTIA.
Yes.
> With respect to 20131113FlavorsIntro.pdf: I like this.
> We may however have to add:
> (v) In order to deal with interval widening due to finite precision
> in (iii), each flavor has the notion of T-hull for each interval
> type T that it supports. (Reference to Clause 5.)
>
> With respect to (iv) we might also mention that a given operation, such
> as Addition, may have have mostly common evaluations, but may also have
> some non-common evaluation instances where the result may not be common
> even though all arguments are common -- due to Level 2 discretization.
AFAICS we must choose one of these two:
(A) Each flavor shall have a T-hull that is defined for *every* Level 1
interval of the flavor.
(B) The standard permits some Level 1 intervals not to have a T-hull, in
which case an exception must be signaled when this is encountered.
I slightly prefer (A), hence my answer to (**) is "by preference, No".
But I am not sure why.
John
--------------Further notes--------------
I take (A) to mean that
(*) in flavor F, for every type T and every (Level 1) interval xx there is
a T-interval yy s.t.
yy "C" xx
where "C" is the flavor's "contains" relation.
Without loss, yy can be chosen to be minimal w.r.t. "C". The T-hull is such
a minimal "contain"ing T-interval.
Michel, is that what your (v) above means?
(B) is related to the proposal that there should be a mode that emulates the
pure classical IA flavor, where all intervals are bounded nonempty.
This flavor already must throw an exception with intersect(xx,yy) when xx and
yy are disjoint, or with sqrt([-2,-1]), so doing so on overflow is no big
change. Whether the exception forces termination is not our business.
Ned likes the idea of this mode, but the more I look at it the less I like it.
I think it would be a mess.
--------------------------------------------
On 2013 Nov 15, at 22:51, Michel Hack wrote:
>>> Conceivably this could be an interceptable
>>> exception, in some implementations.
>>
>> Isn't this true in *most* implementations? E.g. in C++ or Java, can't
>> a user program intercept *any* exception with a "catch" clause?
>
> Perhaps most, but certainly not all that might be practical to use.
>
> But you are right that this is not our business. We have decided to
> define certain required exceptions (for the first few years we were
> reluctant to do so, but invalid constructors really forced our hand),
> so adding another one ("Unavoidable containment violation") is no big
> deal. How an implementation reacts to an exception is its own business;
> all we can do is (a) offer suggestions and (b) *require* that the way
> exceptions are dealt with be documented. An implementation that aborts
> with no means for interception would be low on the QoS scale, and one
> that ignores exceptions and returns [0,0] or 0 (as the case may be)
> would be even lower. But there is precedent: atof("bad string") in C
> is defined to return zero!
>
>> I take (A) to mean that
>> (*) in flavor F, for every type T and every (Level 1) interval xx
>> there is a T-interval yy s.t.
>> yy "C" xx
>> where "C" is the flavor's "contains" relation.
>> Without loss, yy can be chosen to be minimal w.r.t. "C".
>> The T-hull is such a minimal "contain"ing T-interval.
>>
>> Michel, is that what your (v) above means?
>
> Yes.
>
>> (B) is related to the proposal that there should be a mode that emulates
>> the pure classical IA flavor, where all intervals are bounded nonempty.
>
> Actually, the way you phrased (B) it doesn't seem so bad...
>
> But this is definitely something that needs to be settled by a Motion.
> If we don't have time for one, we should offer duelling paragraphs and
> point out that one or the other must be picked during the balloting
> period (if this is allowed by IEEE rules) -- conceivable if the effects
> can be completely localised.
>
> Michel.
> ---Sent: 2013-11-15 23:09:22 UTC
>