Re: A proposal for the next motion
I also share many of Arnold's comments and concerns regarding this motion.
It does appear we need some formal procedure to "polish" the motions, in
addition to the usual three week discussion period.
My largest difficulty with the motion as it currently stands is that it
claims to be an effort to support mixed-format interval arithmetic. However,
in reality it reaches much, much further than this and is essentially a bag
of many other subjects and topics, as well. Baker's suggestion of breaking
it down into smaller, bite-sized motions I think is terrific idea.
Another problem I have is it represents an effort to standardize a c-set
interpretation of intervals (in regards to natural domains of functions),
and this is not compatible with practical and efficient modal interval
implementations (see comments below).
In the future, I would prefer to see much more smaller, manageable motions.
I think the size and complexity of this one makes it difficult to consider.
Nevertheless, I will make effort to be productive and provide some comments,
although it is not a full scope of my concerns and objections (I just wish
to give some general guidance at this point without being overly nit-picky).
Nate Hayes
Sunfish Studio, LLC
>
> P1788 members
>
> I propose the following motion. Like Motion 3, it is not about structure
> and procedure of the standard, but about content. I aim in the next few
> weeks to turn the text below into a LaTeX document that can be submitted
> for inclusion in the standard text.
>
> Note to the officers: this is significantly changed from the previous
> draft. I have responded to various comments, and have tightened up various
> definitions.
>
> John Pryce
> ====================================
>
> ===Motion P1788/M0005.01_Level_2_Mixed_format===
> Proposer: John Pryce
> Seconder: Dan Zuras
>
> ===Motion text===
> P1788 shall support mixed-format interval arithmetic (Definition D2) as
> specified in 1 to 11 of the Rationale below. Specifically:
>
> (1) An implementation (of this standard) shall specify which interval
> formats (Definition D1) it supports, and shall provide mixed-format
> arithmetic for all supported interval formats.
> (2) An implementation shall be called 754-conforming if: (i) its
> underlying system is 754-conforming (Definition D3) and if the
> implementation supports intervals of each of the five basic 754 floating
> point formats: binary32, binary64, binary128, decimal64, and decimal128;
> or (ii) it is functionally indistinguishable from case (i).
Again, I think this puts the cart before the horse. We do not yet even know
what are the Level 1 semantics of intervals in 1788, so this definition is
hardly enough to specify if a 1788 implementation can be considered
754-compliant or not.
> (3) The relation between a floating point format and its interval format
> shall be as defined in 7 and 8 below.
> (4) There shall be conversions between any two supported interval formats,
> as defined in 9a below.
> (5) An implementation shall specify a set of "interval-supported
> elementary functions" (Definition D7). For any such function and any
> supported format F there shall be an interval version of that function in
> that format, which shall enclose the sharp interval F- extension of that
> function as defined in 9b below, but is otherwise not specified by this
> motion.
> This motion also leaves it open whether every point elementary function
> (Definition D3) is interval-supported.
> (6) A 754-conforming implementation may provide other interval formats
> beside the basic five, and appropriate conversions and operations: for
> instance, in variable-precision arithmetic.
> (7) An implementation may provide more than one interval elementary
> function in a given format: for instance, to offer different trade- offs
> between speed and tightness.
>
> Constraint: Items (3,4,5) above ensure that the Basic Theorem of Interval
> Arithmetic (BTIA) holds for mixed-format calculation in any conforming
> implementation, as outlined in 10, 11 below. The BTIA is fundamental to
> interval computation; therefore, an amendment to this motion is only
> acceptable if it preserves the BTIA.
>
> This motion does not cover:
> - What elementary functions shall be, or are recommended to be, provided
> by
> an implementation.
> - Issues of the construction of intervals, from real numbers, text
> strings, etc.
> - Issues of definition of real-valued functions of intervals, such as
> whether
> finding the midpoint of the whole line should return NaN, or generate an
> exception, etc.
> - Issues of tightness of enclosure, as in the 'accuracy modes' of
> Vienna§3.2.
> - Flags, exceptions or other means of signalling that an elementary
> function
> has been evaluated outside its domain.
The definitions below completely contradict this statement, i.e., this
motion *does* require certain (unwanted, in my view) interpretations of
these situations.
>
> ===Rationale===
> ===============
> This divides into Foundations; Terminology; Definitions; Introduction;
> Level 1 description; and Level 2 description.
>
> Foundations.
> ------------
> Motion 2 and the associated position paper, defining a levels structure as
> a guideline for the standard.
>
> Motion 3, which defines P1788's number system and set of intervals.
>
> Terminology.
> ------------
> 754§X denotes section X in the standard IEEE754-2008. Vienna§X stands for
> section X in the final version of the Vienna proposal, 19 December 2008.
>
> Definitions.
> ------------
> [Note. These are intended to be part of a standard set of definitions,
> abbreviations and acronyms of this standard, similar to 754§2. I have not
> yet put them in any systematic order.]
>
> D1. An "infsup interval format" means the set IR_F of F-intervals for some
> floating point (abstract) format F, as defined in 7 below. When used
> without qualification, "interval format" means an infsup format -- by
> contrast with, say, a midrad (midpoint-radius) format.
>
> D2. "Mixed-format" interval arithmetic refers to operations on intervals
> where the formats of the operand interval(s) and the destination interval
> may not all be the same.
> Note. It is implied by the theory below that the formats of the lower and
> upper bounds of an individual interval are the same.
>
> D3. A "754-conforming system" is a programming environment in which the
> default floating point arithmetic (whether implemented in hardware,
> software or a mixture) conforms to IEEE754-2008.
> [Note. A hardware processor (e.g. the Cell processor) may not be
> 754-conforming in itself, but a 754-conforming system may be built on top
> of it with software assistance.]
>
> D4. A "point elementary function" is a point function, in the sense of 4
> below, that is provided by an implementation. The set of these is the
> implementation's "point elementary function library" ("point library" for
> short). These terms may be qualified by a format, e.g. "binary64 point
> library".
> [Note. The four basic arithmetic operations count as elementary
> functions.]
>
> D5. An "interval elementary function" and the "interval elementary
> function library" ("interval library" for short), possibly qualified by a
> format, are defined similarly.
>
> D6. An interval elementary function is "algebraic" if it is an interval
> extension of a point function. See 5 below.
I agree with Arnold's comments: "algbraic" is not the best term for
transcendental functions such as exp, ln, sin, cos, etc.
>
> D7. A point function is "interval-supported" if an interval extension of
> it exists in the interval library.
> [Note. An interval-supported function need not be in the point library. A
> function in the point library need not be interval- supported. It is left
> open whether the standard makes requirements on these issues.]
>
> Introduction.
> -------------
> The theory below aims to provide a simple foundation for interval
> computation in mixed formats, for instance mixing binary and decimal
> intervals in arithmetic expressions, as well as potential compile- time
> "exact denotations" of intervals such as pi + [-0.1,0.1].
>
> We believe the concepts given here, though general, are easily grasped and
> easily taught. They show that the theoretical difficulties of mixed-format
> interval computation are none, and the practical difficulties --
> illustrated by the example in 10 below --
> are minor.
>
> The notation used is similar to that of the Vienna proposal, which is
> suitable for a plain-text document such as this. I believe the
> functionality defined below is essentially what the Vienna proposal
> defines, or rather what it would define if it supported mixed-format
> computation explicitly: see the end of Vienna§1.1.
>
> I have avoided the Vienna terms "L-numeral" and "B-numeral", which are
> valuable notions but place an emphasis on representations that I think is
> unnecessary in this context.
>
> I believe there is nothing in this motion and the theory below that
> hinders the implementation of various forms of non-standard intervals --
> Kahan, modal, etc. -- as discussed at the end of Vienna§1.2.
This is simply not true. The definitions provided by this motion concerning
natural domains of functions is not compatible with practical or efficient
modal interval implementations.
>
> Level 1 description.
> --------------------
> This section recapitulates what has already been decided.
>
> 1. R is the set of reals. R* is the set of extended reals
> R* = R union {-oo, +oo},
> where we use -oo and +oo to denote negative and positive infinity.
> Following 754, any member of R* is called a number: it is a "finite
> number"
> if it is in R, else an "infinite number".
I'm not sure this has really been decided. Motion 3 says that intervals are
(possibly unbounded) sets of real numbers. But the vote did not actually
specify what is the meaning of -oo and +oo other than they can be used to
indicate ubounded endpoints.
There may be other interpretations. For example, that -oo and +oo represent
large but finite "universal bounds." Until the Level 1 definition of the
interval arithmetic is agreed upon, I don't think its wise or safe to assume
754 conventions.
I think this motion therefore makes assumptions about things that haven't
completely been agreed to or voted on.
>
> 2. Following Motion 3, the set of "textbook" intervals (Vienna§1.2) in R,
> denoted IR, comprises the empty set together with all intervals
> x = { x in R | xlo <= x <= xhi } (*)
> where xlo <= xhi, -oo <= xlo < +oo, -oo < xhi <= +oo.
>
> Following standard mathematical notation, the interval (*) is denoted
> [xlo, xhi] if xlo and xhi are finite, but denoted (-oo, xhi] or [xlo, +oo)
> or (-oo, +oo) in the case of infinite endpoints, to indicate that -oo
> and/or +oo is not a member of the set.
>
> The empty set is denoted by Empty. The whole of R is denoted by Entire.
>
> 3. The (interval) hull of an arbitrary subset ss of R, written hull (ss),
> is the
> smallest member of IR that contains ss.
>
> 4. A "point function" is a (possibly partial) multivariate real function:
> that is,
> a mapping f from a subset D of R^n to R^m for some integers n,m >= 0.
> (When n=0
> and m=1, we have a "named real constant".)
>
> When not otherwise specified, a scalar function is assumed, i.e. m=1. If
> m>1,
> the function is called a vector function.
>
> D = D_f is the domain of f.
>
> To specify n, call f an "n-variable point function", or denote f as
> f(x_1, ..., x_n).
>
> The "range" (or "exact range") of f over an arbitrary subset ss of R^n is
> the
> set
> range(f, ss) = {f(x) | x in ss and x in D_f}.
Adding the constraint "x in D_f" is a c-set convention.
This convention is not compatible with modal interval interpretation, which
would essentially be:
range(f,ss) = { f(x) | x in ss },
so if any element x in ss is not also in D_f, the expression is undefined.
This follows the natural mathematics. It brings back all the prior
discussions about NaI vs. Empty.
>
> Note. Here, f is a mapping, not an expression. Expressions are dealt with
> in
> 11 below.
>
> 5. Unless otherwise specified, an "interval function" is a mapping ff from
> (IR)^n to (IR)^m for some n >= 0. To specify n, call ff an "n- variable
> interval function", or denote ff as
> ff(xx_1, ..., xx_n).
> As with point functions, m=1 is assumed unless specified otherwise.
>
> An interval function is "algebraic" if it is an interval extension of some
> point function, as defined next. Examples of non-algebraic functions are
> the interval hull and intersection functions.
I think the term for these "non-algebraic" functions is "lattice operators".
>
> Given an n-variable point function f, an "interval extension" of f is any
> interval function ff such that
> ff(ss) contains range(f,ss) for any subset ss of R^n.
> The "sharp interval extension" of f is defined by
> ff(ss) = hull(range(f,ss)) for any subset ss of R^n.
>
> Equivalently, for the case where ff has separate arguments ss_1, ...,
> ss_n,
> each being a subset of R, an interval extension satisfies
> ff(ss) contains range(f,ss_1, ..., ss_n),
> and the sharp interval extension satisfies
> ff(ss_1, ..., ss_n) = hull(range(f,ss_1, ..., ss_n)),
> for any ss_1, ..., ss_n.
> This is an alternative notation for the case where ss is the cartesian
> product of the ss_i.
>
> In particular, when f is a binary operator "op" written in infix notation,
> this gives the familiar definition of its (sharp) interval extension as
> xx op yy = hull({x op y | x in xx, y in yy, and x op y is defined}).
Again, this is a c-set convention because of "x op y is defined".
>
> Notes.
> - Example. With these definitions
> xx*{0} = {0} and xx/{0} = Empty for any nonempty interval xx.
> - All interval functions used here are automatically defined for all
> arguments (e.g. sqrt([-1,4]) = [0,2], sqrt([-2,-1]) = Empty). It is left
> open what exceptional action may be taken by an implementation on
> evaluating ff(ss), when ff is an extension of a point function f, and
> ss is not a subset of D_f.
These interpretations are not compatible with modal intervals.
By default, they should be:
sqrt([-1,4]) = NaI
sqrt([-2,-1]) = NaI
where NaI simply means "undefined" or "invalid operation," so that the NaI
will be guaranteed to propagate through the remainder of a lengthy
computation.
If users are interested in the c-set conventions, they can explicitly
intersect the interval argument with the natural domain of the function,
i.e.:
sqrt([-1,4]&[0,+oo)) = sqrt([0,4]) = [0,2]
sqrt([-2,-1]&[0,+oo)) = sqrt({empty}) = {empty}
>
> Level 2 description.
> --------------------
> 6. A floating point "abstract format" ("aformat") F is a finite subset of
> R*
> such that at least -oo and +oo are elements of F.
>
> <754>A format in the 754 sense shall be identified with the aformat
> comprising
> those extended-real numbers that are exactly representable in that format,
> where -0 and +0 both represent 0.
>
> Notes.
> - In view of this definition, 754's -0 and +0 are considered identical.
> Also,
> in 754 decimal formats, numbers in the same cohort are considered
> identical.
I do agree it is good idea to not give unique algebraic properties to -0 and
+0, but this seems to be off-topic from the current motion (and may be
controversial to others).
> - For examples, we use the abbreviations b64 to mean 754's 64-bit binary
> format (C's "double"), and d64 for 64-bit decimal. Similarly b32 is 32-bit
> binary (C's "float").
> </754>
>
> 7. Given an aformat F, the set of F-intervals in R, denoted IR_F,
> comprises the
> empty set together with all textbook intervals whose endpoints are in F.
>
> Notes.
> - This definition implies some form of infsup, that is (lower bound,
> upper bound) representation of intervals. Variants of this exist, see for
> instance Vienna§1.6.
> - It also implies that it is not just wrong, but actually meaningless at
> this level, to speak of an interval that has NaN as an endpoint or has its
> lower bound greater than its upper bound.
How is the empty set then represented?
>
> An "F-interval datum", by analogy with the definition of floating- point
> datum
> in 754§3.2, is either an F-interval or possibly, should P1788 support it,
> an abstract object NaI, "Not an Interval".
>
....snip....
> However these ee_F operations are implemented, it is easy to see that
> Moore's
> Basic Theorem of Interval Arithmetic holds for any such mixed-format
> calculation:
>
> Theorem (BTIA). For any interval inputs xx = (xx_1, ..., xx_n), the result
> yy = ff(xx) of (4) encloses the exact range, range(f, xx) of the real
> function
> f over xx.
>
I think this motion bites off more than any of us can chew in one sitting.
It is like asking to give "YES" or "NO" vote on the entire Vienna Proposal
"as is." I think it would be much better to break this motion down into more
manageable topics and discussions that can be considered in some more
orderly fashion. In particular, I think the discussion should be focusing
more on Level 1 at this point, since there is not yet agreement even there.
Nate