Re: Re-revised interval flavors motion36.03
Vincent & P1788
Here is a version responding to Vincent's comments. Substantive changes marked by
*****
for visibility, with both old version (quoted) and new version given where it's a change rather than an addition.
The issue of containment and FTIA isn't quite what I thought, and needs further discussion, I believe.
On 31 Jul 2012, at 14:49, Vincent Lefevre wrote:
> On 2012-07-30 19:10:13 +0100, John Pryce wrote:
>> My conclusion is that to make flavors work, 1788 should specify a common
>> set of intervals, and a common set of opinsts, and require all flavors to
>> agree on these. But not make requirements beyond this.
> I disagree (this is not what was decided at the end of the discussion).
I take it you disagree with "But not make requirements beyond this". Those words are not part of the motion or rationale, but your criticism of them is fair. What I meant was on the lines of
(A)
"For opinsts outside the common set, 1788 should not make general
requirements about how two flavors relate to each other, such as that
op(X1,X2,...), if defined, should have a value independent of the flavor;
because it seems hard to implement this in a specific case except by
saying one of the flavors has precedence and the other must conform to
it."
> The problem with this choice is the following: the standard needs to
> specify requirements and recommendations for arbitrary functions ...
>
> For instance, a requirement would be the containment property.
OK. Motion 36 affects the basic architecture of the standard, and the equally basic requirement of containment needs restating.
But thinking it over, I see we don't NEED to say "each flavor must have its own FTIA". For evaluating an expression in the case where only common opinsts are used, it is a Theorem, not a Requirement, that you get enclosure. (Also true in Level 2.) Obvious really, because in that case, for any flavor, you are actually doing classical interval evaluation but pretending it is something else.
For evaluating an expression outside this case, it seems to me containment constitutes a conformance requirement, rather than a requirement on behavior. A flavor can do whatever it likes, outside the common opinsts, but it shall demonstrate that a flavor-specific "generalized FTIA" applies, otherwise it can not be conforming. This generalized FTIA may use flavor-specific definitions of "contains", "exact range", etc., which however aren't needed for stating the FTIA in the common opinsts case.
Does that seem reasonable?
> There
> would also be requirements and recommendations concerning the accuracy.
To deal with later, in Level 2.
> And requirements about flavors are needed too. Thus instead of listing
> a set of opinsts that would be specific for each function, the standard
> needs to give a rule from which one would deduce the set of opinsts.
> The rule you gave at the end of the discussion was: "the operation is
> defined and continuous at each point of its input box". And the rule
> should be simple enough so that the standard makes easy to implement
> new functions from a minimal library.
I've reworded, to make it clearer that my rule *is* a general one with (I think) the properties you demand.
> Also, this was not discussed, but I think that
(B)
> an operation that is
> not an interval extension of some math function shall not depend on
> the flavor (at least if the result is in the common set).
IMO (B), as a requirement, has the defect noted in (A) above. At present the only operations that fall into this case are convexHull and intersection -- I can't think of other non-arithmetic operations that we might plausibly want to add to the library in the future.
However a general rule for this case *is* needed. The obvious but somewhat ad-hoc one is: follow the set-based definition for the case where inputs and output are common intervals. So the opinsts are:
Z = (set-based convexHull(X,Y))
for arbitrary common X,Y;
Z = (set-based intersection(X,Y))
for arbitrary common X,Y such that Z is common, i.e. nonempty.
I have included this specification.
If Empty were in the common set then (B) would be false, so one may regard (B) as a constraint that gives a reason to exclude Empty from the common set.
> I wonder what the intersection of [0,1] and [2,3] should be in the modal
> flavor...
[2,1], I believe.
John Pryce
===========================================================================
Motion 36, version 03. (Sub-version 2?)
======Terminology======
In this motion, "set-based" interval means the kind of interval specified
by Motion 3, and "modal" interval includes the modal and the Kaucher kind
of interval, and any related kind that the modal subgroup may wish to
specify.
======Motion======
1. The standard shall permit different kinds of interval, called "flavors",
each having its own part of the standard text as well as a common part.
This motion is only about the Level 1 aspect of flavors.
2. There shall be a set of "common intervals" shared by all flavors, namely
the closed, bounded, nonempty real intervals (also called "classical
intervals").
There shall be a common set of named operations, and for each such
operation a set of "common operation instances". For arithmetic operations,
these shall comprise all cases where the corresponding point function is
defined and continuous everywhere on the input box, the interval result
being defined to be the exact range of the function over this box.
The meaning of "shared" in the previous paragraphs is defined precisely in
the Rationale. Informally, common intervals behave as a subset of each
flavor, on which the common operation instances behave identically in all
flavors.
*****add
Each flavor shall satisfy an appropriate version of the Fundamental Theorem of Interval Arithmetic (FTIA), which shall reduce to the classical FTIA of Moore when only common operation instances occur. See rationale for details.
*****end add
3. There shall be a set-based flavor, whose specification has been the
subject of previous Motions -- notably 3, 5.02, 8.02, 9, 10.02, 12, 13.04,
18, 21.2, 30.02, 33, which are most relevant to Level 1.
The main Editorial Team, currently John Pryce and Christian Keil, shall be
responsible for the set-based part of the standard text.
4. The P1788 group asks the Modal Subgroup to appoint from its members a
Modal Editorial Team, which shall be responsible for specifying a modal
flavor, and writing a corresponding modal part of the standard text.
5. Beside set-based and modal, other flavors that extend classical
intervals may be specified in future, for instance Kahan wraparound
intervals, or intervals that are open at one or both endpoints.
6. In addition to item 3, the main Editorial Team shall be responsible for
overall style and presentation and, in discussion with relevant editors,
integrating the text of all flavors into the final standard document.
7. Conformance. An implementation shall support at least one flavor. It
shall document which flavors it supports.
If it supports more than one flavor it shall make it possible for a program
to select a flavor in a language-defined way, along the lines of "constant
attributes" in IEEE 754-2008 clause 4. A program shall have the ability to
determine which flavor is in effect at any point of its execution.
8. Aspects of flavors beyond this, including how flavors interact with
Level 2 and with the decoration system, shall be decided by future motions.
Rationale
=================================================
This rationale text is based on the email Michel Hack and I circulated on
23rd May 2012, but substantially revised, especially in the light of comments by Vincent Lefevre.
General principle
-----------------
What matters is behavior, both at Level 1 and Level 2. It doesn't matter
that a set-based interval is a set of reals and a modal or Kaucher interval
is something else, provided that when applied to the "same" inputs they
give the "same" result.
The meanings of "same", and of "shared" in the motion text, are specified
below, especially by the notion of embedding map (1) and operation
compatibility (2). For instance a modal interval X* and a set-based
interval X** are the "same" if X* = m(X) and X** = s(X) for some common
interval X.
Terminology & notation
----------------------
thing = a Level 1 bare or decorated interval,
datum = a Level 2 bare or decorated interval,
The word "agreed" marks a design decision the group must make to let the
set-based and modal flavors interoperate.
Think of X1, X2, etc. as being subscripted X_1, X_2, etc.
Level 1
-------
Set-based intervals and modal intervals both arose from arithmetic on the
"classical" set of closed bounded nonempty real intervals. The motion
requires that at Level 1 there be
- a set C of common (in the sense of "shared") things,
- a set S of things belonging to the set-based flavor,
- a set M of things belonging to the modal flavor.
A general flavor has a set F of things, together with a one-to-one
embedding map
(1) f : C -> F
by which C can be regarded as a subset f(C) of F. A flavor F with its map f
will be denoted (F,f). In particular, there are embedding maps
s : C -> S and m : C -> M
for the set-based and modal flavors.
An operation-instance (opinst) for a k-ary operation "op" means a (k+1)-
tuple of intervals (X1,X2,...Xk;R) such that R = op(X1,X2,...Xk). That is,
an opinst is a point in the graph of "op", when "op" is regarded as an
interval mapping.
A C-opinst means one where all the inputs X1,...Xk and the result R are in
C.
We need "Operation Compatibility" for C-opinsts:
op(fX1,fX2,...fXk) = f(op(X1,X2,...Xk).
(f(X) is abbreviated to fX when context makes clear.) That is, an operation
gives "the same" result, whether you perform it in C and then map to F, or
map to F first and perform it in F.
However, it is essential to specify for just which C-opinsts this is to
happen, because of the point Vincent Lefevre raised. Two cases need
considering:
Case (a)
op(X1,X2,...Xk) gives a result in C with one flavor, but is
undefined in another flavor.
Example: sqrt([-1,4]) is undefined in M, but is defined in S
with value [0,2] in C.
Case (b).
op(X1,X2,...Xk) gives different results R1 and R2, both in C, in
different flavors.
Example: sign([0,4]) is undefined in M, but is defined in S
with value [0,1] in C, and would be defined in a "cset" flavor
with the different value [-1,1], also in C.
*****change
> Therefore, a set CO(op) of "common" C-opinsts is specified for each
> operation "op", such that for each (X1,X2,...Xk;R) in CO(op) we have
> op(X1,X2,...Xk) equals R in *all* flavors.
>
> Formally, this means that for each "op", for each flavor (F,f) and for each
> (X1,X2,...Xk;R) in CO(op) we have
>
> (2) op(fX1,fX2,...,fXk) is defined in F and equals fR.
> *****to
Common set CO(op) of C-opinsts and how to choose it
---------------------------------------------------
Thus the standard needs to specify a set CO(op) of "common" C-opinsts for each
operation "op", such that for each (X1,X2,...Xk;R) in CO(op) we have
op(X1,X2,...Xk) equals R in *all* flavors.
Formally, this means that for each "op", for each flavor (F,f) and for each
(X1,X2,...Xk;R) in CO(op) we have
(2) op(fX1,fX2,...,fXk) is defined in F and equals fR.
The specification of CO(op) must be by general rule(s) that apply to any new operation that may be put in the library. The specific rules, and reasons for choosing them, are given below, with separate rules for arithmetic operations (interval extensions of point functions) and for non-arithmetic operations such as intersection and convexHull.
*****end change
Clearly, CO(op) must define a one-valued function, so if (X1,X2,...Xk;R1)
and (X1,X2,...Xk;R2) are both in CO(op), then R1=R2.
A flavor is permitted to extend operations on C beyond this. That is, there
may exist (X1,X2,...Xk;R) *not* belonging to CO(op), such that (2) holds -- as in the example cases (a) and (b) above.
*****add
Fundamental Theorem
-------------------
Each flavor (F,f) shall demonstrate that a version of the Fundamental Theorem of Interval Arithmetic (FTIA) holds, appropriate to its definition of interval and of the "contains" relation.
It follows, from (2) and induction, that this reduces to the classical FTIA of Moore, in the case when only common opinsts are used, so there is no need to state this as an extra requirement.
*****end add
*****change
> Reasons for choice of C and CO(oP)
> ----------------------------------
> There seems no point in having this motion unless C includes the
> "classical" set of closed bounded nonempty real intervals. I choose C to be
> exactly this set, because any larger set might make it harder to add other
> flavors in the future.
>
> For a modal-flavor interval version of a point function "op" to be defined
> on an input box whose components are in C, it is sufficient and (I believe)
> necessary that "op" be continuous on the box. The set-based flavor has no
> restrictions here. This makes it natural to choose CO(op), for any "op", to
> be all C-opinsts (X1,X2,...Xk;R) such that "op" is everywhere defined and
> continuous on the box (X1,X2,...Xk), and R is the exact range of "op" on
> this box, which is necessarily a closed bounded nonempty interval.
>
> To be precise, that a function g is defined and continuous on a subset X of its domain is taken to mean
> (a) g is defined and continuous at each point of X,
> not
> (b) the restriction of g to X is defined and continuous on X.
>
> For modal intervals, I think either would do. I chose (a) to support a
> possible cset flavor in future -- e.g., it implies ([0,0]; [0,0]) is NOT a
> common opinst for the sign() function, thus allowing the cset value sign
> ([0,0]) = [-1,1] to be different from the set-based value. However I am not
> wedded to csets, and could be persuaded to choose (b) instead.
> *****to
Specific choice of C and CO(op), with reasons
---------------------------------------------
C shall be exactly the "classical" set of closed bounded nonempty real
intervals.
For an interval extension of a point operation "op" , CO(op) shall be all C-opinsts (X1,X2,...Xk;R) such that "op" is defined and continuous at each point of the box (X1,X2,...Xk), and R is the exact range of "op" on this box, which is necessarily a closed bounded nonempty interval.
[Note. This is different from
(*) The restriction of "op" to the box is everywhere defined and
continuous on the box.
To illustrate, (*) implies
sign([0,0]) = [0,0]
is a common opinst, whereas the chosen definition leaves sign([0,0]) undefined. Thus (*) would disallow cset interval arithmetic from being a flavor, since it gives sign([0,0]) = [-1,1]. However I am not wedded to csets, and could be persuaded to choose (*) instead of the current definition.]
For the non-arithmetic operations convexHull(X,Y) and intersection(X,Y), the normal set-based definition shall apply for all X,Y in C such that the result is also in C. Thus, not for the case of intersection when the result is Empty.
Reasons for choice: There seems no point in this motion unless C includes the "classical" set of closed bounded nonempty real intervals; and choosing any larger set might make it harder to add other flavors in the future. For a modal-flavor interval version of a point function "op" to be defined on a box (X1,...,Xn) whose components are in C, it is sufficient and (I believe) necessary that "op" be continuous on the box. The set-based flavor has no restrictions here. Hence the choice of CO(op).
*****end change
Relation to §5.6 and §5.7 of the standard text
----------------------------------------------
The above shall apply to all arithmetic operations in the Required
Operations (§5.6.2), to non-arithmetic operations (5.6.6) and to those arithmetic operations in the Recommended
Operations (§5.7) that an implementation provides.
As for other subclauses of 5.6:
- 5.6.1 (Constants) is not relevant.
- 5.6.3 (Interval case expression). At first sight I don't see how
this makes sense for modal intervals, so I propose omitting it
from the common set.
- 5.6.4 (Reverse-mode functions). I don't know what the modal
definition of these should be, but it seems perfectly possible
there is one, so I await advice from the modal group.
- 5.6.5 (Inner add & subtract). The common set should be those where
the S flavor gives a defined result at Level 1. (M gives a defined
result, possibly improper, in all cases.)
- 5.6.7 (Constructors), 5.6.8 (Numeric functions of intervals),
5.6.9 (Boolean functions of intervals), 5.6.10 (Dot product).
These should be the subject of a future motion.
I don't see them giving insuperable problems.
Decorations and flavors
-----------------------
This should be the subject of a future motion. I believe flavors will
remove much of the disagreement between different camps, allowing different
"flavors of decoration", again with an essential common part.
To this end, the decoration system must be able to signal "not a common
opinst". This would occur when doing, say, intersection([0,1],[2,3]) which
gives Empty in S and [2,1] in M. Coupled with the ability to enquire at run
time what flavor is in effect (motion item 7), this would allow code to
give correct results -- or fail gracefully -- in any flavor.
Note this raises at Level 2 the old issue of overflow. Does [0,REALMAX]
+[0,REALMAX]=[0,Inf] count as a common opinst? (The result is a member of
C, but one can't represent it as such.) Some work to do here.
Level 2
-------
The motion now doesn't cover this, but I include the text from version 2
with little change.
Here there are
- a set C of common datums,
- a set S of set-based datums,
- a set M of modal datums.
There is the extra complication of *types*. My proposal requires there be
an "agreed" type-portfolio TP of named types T, and the embedding map (1)
and compatibility equation (2) hold for the datums of each T in TP. I hope
it's obvious what I mean, without more definitions.
Level 2 also has *implementations*. Regard an implementation as a library
that supports various interval types, the operations on them, and inter-
type conversions, and may split into a set-based and a modal sub-library. A
given implementation need not provide every type in TP, and may provide
types not in TP.
Queries: Should there be an "agreed" minimum subset of TP that each
implementation shall support (say, at least the binary64 inf-sup type)?
[Vincent Lefevre, 5 July, wrote:
I don't think so, except for 754-conforming implementations.
]
Should an implementation that provides both a set-based and a modal sub-
library provide the same subset of TP in each? These are some of the issues
to be decided.
I suggest (2) should hold *exactly* at Level 2 for each operation to which
we give the "tightest" attribute; and for constructors; and for boolean
operations. Probably also for numeric functions of intervals -- this
requires there be an "agreed" set of numeric formats. Equality within a
roundoff tolerance may be accepted for other operations: these are issues
to be decided.
In version 2 I had
"The result I'm aiming for is that
(*) A Level 2 program that only ever performs internal
operations runs identically whether it is linked with the
"modal" or the "set-based" library."
This can now be hardened up to
(*) A Level 2 program that only ever evaluates common opinsts runs
identically in all flavors,
(up to roundoff errors, in case it performs some operations that aren't in
"tightest" mode).
Difficulties
------------
In version 2 I wrote (except I wrongly wrote cancelminus instead of
innerMinus):
What of operations that behave differently in the "set-based" and "modal"
flavors, even when applied to common intervals?
If infrequently used, such as intersect() and innerMinus(), they should
IMO exist in two named versions, say innerMinusS and innerMinusM, etc.
Then, if you are running an algorithm that relies on
[1,2] innerMinus [10,20]
producing a modal (improper) interval, you *must* use innerMinusM. If you
then try to link with the "set-based" library the system will report your
error, because it has no innerMinusM operation.
In fact, a "not a common opinst" decoration makes two named versions
unnecessary. But I still think it may be a good idea for infrequently used
operations. It's not practical for, say, division. Opinions please.
Impact on the standard text
---------------------------
I am now convinced this proposal doesn't change the level structure. I
think to make the standard as readable as possible, there should be
separate documents for each flavor, with a few identical common sections
(produced by \include or \input in LaTeX) clearly marked as common by the
way they are typeset.