Motion M0002: Review of why I think "Levels" a good idea
P1788 members
I want to review my reasons for thinking it a good idea to structure the concepts of P1788, and the discussions, into "levels".
A. Consistency
--------------
Dan Zuras has teased me, maybe justifiably, for charging around like Don Quixote in defence of absolute truth. But we are practitioners of a remarkable discipline, where
(1) if we write correct interval code
(2) for an interval system constructed on certain principles
(3) and run it on a machine whose hardware obeys certain rules
(4) putting intervals X in and getting intervals Y out
then
(5) the relation of Y to X is a mathematical theorem,
often of the form that Y encloses range(F,X) for some specified F. Doing item (3) for *discrete* math is no big deal, but we do it for *continuum* math, like "locating gaps in the band spectrum of a Schroedinger equation". I find this amazing.
My zeal for truth that Dan notes is not that of a religious enthusiast, but of an accountant. I want an audit trail between input X and output Y. Only thus will interval computations achieve such credibility that, for instance, their results stand up in court.
One key to achieving that is George's "Keep It Simple, Stupid". C.A.R. Hoare said in Turing Award Lecture 1980: "There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies." (See www.jbox.dk/quotations.htm for more on software simplicity).
A breakdown into layers helps achieve KISS.
In particular there must be an underlying theoretical model. For the particular aims of intervals, (1-5) above, a central feature of the model must be a form of Moore's Theorem (MT):
Evaluating an explicit expression y=f(x_1,...,x_n), in the interval sense,
with interval inputs xx_1, ..., xx_n, either produces an enclosure yy of
the range of f on (xx_1, ..., xx_n), or tells you it failed.
We have currently two competing models:
- R-based Vienna, for which MT is, I believe, a purely algebraic result,
proved in the same way as in Moore's original theory.
- R*-based csets, where evaluation actually computes an enclosure of the _cset_
of f and uses the fact that this encloses the ordinary range. Here, the proof
of MT uses concepts of convergence and compactness.
In exchange for the extra sophistication of csets one gets benefits like the Rational Rearrangement Theorem -- as well as what Arnold sees as defects to do with infinity.
Siegfried has considered a third model that tries to formalise the notion of infinity [resp. signed zero] as "arbitrarily large finite [resp. small nonzero] number". But until it is proven consistent, we should steer clear of it. (I think I showed a containment failure in it.)
Summary: All our work should be submitted to the MT test.
If P1788 doesn't guarantee MT, users risk the ultimate interval sin of Containment Failure. So, from the mathematical model (level 1) down, we are wise to check whether any decision we make puts MT at risk.
B. Existence of things
----------------------
There has been some discussion where one talked about things like [NaN,+oo], as if they have an existence just by virtue of the fact that certain operations on a data structure in a computer can fill its fields with the values NaN and +oo. This confuses the mathematical object with its representation. In the scheme M0002 proposes, one is at level 1, the other at level 3. Keeping these distinctions in view can avoid fruitless discussion.
In the position-paper I use the notation that [xinf,xsup] means a mathematical object (level 1) and [[xinf,xsup]] means a data-structure object (level 3). This is not perfect but it will do. Some people use, say, <<m,r>> to mean an object at level 3 using midrad representation, which is a good idea.
E.g., assuming an infsup representation, [[+oo, +oo]] denotes [+oo, +oo] in a cset system but is a "nonstandard interval" in the Vienna system, which specifies no meaning for it (Vienna 2.4). No meaning is specified for [[NaN,+oo]] in either system.
BTW "No meaning is specified" for a level 3 value doesn't mean we can just forget it. I believe IEEE has reminded us that we must eventually specify what a fully compliant implementation must do, for *every* operation, for *every* input bit-string.
What about interval level 2? It consists of "the finite set of abstract objects one does interval operations on" in a given FP format. I find this a hugely helpful level for discussing things like signed zero and "Not an Interval" NaI. For instance "Are [-0,1] and [+0,1] different?" At level 1 they are obviously *the same* if we use either R or R*. At level 3, [[-0,1]] and [[+0,1]] are obviously *different* if the fields are P754 numbers. At level 2 we can intelligently discuss whether to make [[-0,1]] and [[+0,1]] represent the same object or not, and the consequences for arithmetic.
Vienna doesn't really distinguish level 2 from level 3 (representations), which I find a bit annoying. For instance it hard-wires [[NaN,NaN]] as the representation for Empty.
Summary: Let's say at what level we are discussing, so it is clear in what sense an object exists, and in what sense two objects are equal.
We have many decisions to take, and there are genuine objections to various alternatives we might choose. Distinguishing levels will help us stick to genuine issues and avoid spurious ones.
C. The Lohez level 1' proposal
------------------------------
Dominique Lohez proposes a level 1' above level 1, which would help relate the standard to other kinds of interval (modal, etc.). Dominique, please produce precise wording, but it must observe the KISS principle. George Corliss says this can be a separate motion after M0002 finishes.
D. Two issues where levels are helpful
--------------------------------------
1. "Infinity as member" (Michel Hack's term)
... and Vincent Lefèvre's (Feb 26) statement that it is "buggy". Various people have clarified this now; I think the discussion arose because of confusing level 3 with level 1 concepts.
2. Neumaier's Empty with a payload.
Arnold considers using the "payload" field of a NaN to tag the Vienna system's Empty with diagnostic data. I find this concept completely equivalent to my level 2 NaI concept, but less flexibly expressed because it is tied to its level 3 representation.
E. An issue where levels seem less helpful
------------------------------------------
I'm thinking of the interface between point-numbers and intervals. There are conflicting proposals, notably for how an interval constructor
xx = interval(xinf,xsup)
should treat cases such as
(A) xx = interval(+oo,+oo) in a Vienna-style system, and
(B) xx = interval(NaN,+oo) in Vienna or cset system.
This seems one of the most intractable problems yet, to get consensus on. On (A), Rump and Neumaier have disagreed strongly, and the Vienna proposal has what looks like a compromise with StandardInterval(l,u) and realHull(l,u) constructors that behave the same except when l,u are both -oo or both +oo. The issue touches on
- How far can or should one protect interval programmers from writing bad code?
- How P1788 interfaces with (maybe impacts on) languages.
- What one thinks infinity "is"...
- ... hence, what a user may see as "natural".
In (A), Rump thinks oo should be treated as an arbitrarily large but finite number so xx = [realmax,+oo]. Neumaier thinks oo should be treated as a mistake here, and prefers xx = Empty. I think xx = NaI is more natural.
As far as levels are relevant, I think (A) is a primarily mathematical, level 1, issue, while (B) belongs to level 2.
It has been pointed out that problem (A) is partly due to P754 not distinguishing "true oo" from "finite but overflowed". But we are stuck with that.
Such issues trouble me. At the start, I wrote
(1) if we write correct interval code...
then our remarkable discipline gets guaranteed results. Yet we find it hard to create a programming environment that prevents stupid interval bugs. A bug due to a programmer misunderstanding what interval(+oo,+oo) does, is exactly of the kind that may lie dormant for years and suddenly jump out. How can we improve this?
Best wishes
John Pryce