Re: Revised version of Level 1 text (draft)

["Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>]

John Pryce wrote:
> I do not expect this scheme to receive universal acclaim. For one thing,
> it is not child's play to grasp the specifications. For another, I have
> followed the Neumaier approach to the mathematics. I found this easier to
> follow than the Hayes approach which disagrees with it in various ways. I
> hope, at the implementation level it does the most important things that
> Nate requires.

Not yet. Even at Level 1 there remain some non-trivial differences.

But I'm pleased with the progress; and I see your skill with the technical
writing continues to be a service to all of us.

At the heart of where we agree or converge is the linear ordering (6) of
decorations and then formulas (10) and (11). Regarding (9), in our proposal
we instead define propositions for the various attributes, e.g., C(f,X) for
defined and continuous, D^+(f,X) and D^-(f,X) for the domain tetrit, etc.
then dec(f,X) would be a function that gives a range of decoration states
based on the tabulated truth-values of all the various attribute
propositions (similar to how the interval overlapping operator works). In
this way, ordering (5) is then no longer necessary or relevant to the
definitions.

The main problem with ordering (5) in my view is it contradicts the "sticky"
nature of exception states, and hence leads to most of the remaining
concerns that I have with the currently proposed system. For example, in
IEEE 754 there are various exception flags for overflow, divide by zero,
etc. These flags are "sticky" in the sense that once a particular exception
occurs, the appropriate flag is set and remains that way for the remainder
of the calculation (unless the user manually intervenes and resets the
flag).

Although P1788 decorations are not global in nature, the exception
information stored in the decorations should nevertheless be "sticky," just
like in IEEE 754. However, ordering (5) ensures this will not always be
true. Just as an example: if a vendor returned decoration "con" for all
interval operations, it would satisfy ordering (5). But it would not provide
any reliable way for users or applications to detect exceptions.

The greatest impact appears in the lattice operations. So I'd like to focus
on this a bit. As mentioned in 4.8.5, ordering (5) gives rise to semantics
such as

   ([1,3],"safe") intersect ([2,4],"somewhere undefined") = ([2,3],"safe").

This is an example of potentially introducing a false positive into a
computation, since the fact that a "somewhere undefined" exception occured
is quietly lost by the intersection operation without the user's knowledge
(i.e., the "somewhere undefined" decoration is not "sticky"). Any
application that would rely on such an exception being detected and reported
to the user may therefore be susceptible to failure (the attached PDF is an
example of this).

It appears the motion's definitions for the lattice operations depend on
special circumstances which might not always be true. For example, the
semantic of the intersection operation above assumes that [1,3] and [2,4]
are ranges of some function f evaluated using two different algebraic
rearrangements of f. But in a general-purpose computational environment,
[1,3] and [2,4] might just as well be ranges of two unrelated functions.

Even in the best case when all of the assumed semantics and preconditions
are valid, one can obtain unpredictable results. At the very end of this
e-mail is another example for the intersection operation. In this case
f1(x,y) and f2(x,y) are algebraic rearrangements of f(x,y). Both f1 and f2
are undefined, respectively, for x=0 and y=0. We also have fgood(x,y)
defined as the intersection of f1, f2 and f. According to the example,
evaluating
   fgood([-1,1],[3,4])=([8/5,4],saf)
is proof that the function f is defined and continuous for all x,y in the
box ([-1,1],[3,4]). However, it is only a coincidence that fgood is true. A
user or computer algorithm may just as well evaluate
   fgood([0,0],[3,4])=(Empty,emp)
to find "proof" that the function f is not defined and continuous for all
x,y in the box ([0,0],[3,4]). This is clearly the wrong result, since it
contradicts the previous assertion that f is defined and continuous for all
x,y in ([-1,1],[3,4]).

We are currently examining the application of decorations to Constructive
Solid Geometry (CSG):
   http://en.wikipedia.org/wiki/Constructive_solid_geometry
This relies heavily on the interval lattice operations min and max. For
example, a solid object may be represented by an implicit function f. Then
the set of all f < 0 is inside the object, f > 0 is outside the object, and
f = 0 are points on the surface of the solid object. If A and B are two
solid objects and fA and fB are their respective implicit functions, then
the intersection between A and B is defined
   A intersect B = max(fA,fB)
and the union between A and B is defined by
   A union B = min(fA,fB).
The current draft is silent on the min and max operations, but we see the
decorations need to propagate through the lattice operations in a manner
similar to formula (10) but without the c_0 decoration (since the lattice
operations are obviously not real functions, c.f., "Theorem 8" in our draft
position paper). I don't have time right now to post a more detailed
explanation, but will do so as time permits.

Nate Hayes

P.S. John, I am sympathetic to your observations about the "bounded"
attribute: that in some ways it continues to be a fly in the ointment. This
rekindles some of my earlier thoughts that "bounded" should not be a
decoration, but an intrinsic property of the bare intervals, e.g., interval
endpoints could make the distinction between Overflow and Infinity as Ian
McKintosh has pointed out several times in this forum.





> Appendix 2: A detailed example for the intersection
>
> Suppose as part of a long interval evaluation we have a subexpression
>   z = (2x+2y)/(2x+y) =: f(x,y).
> The naive interval calculation
>   function f = fnaiv(x,y)
>     f=(2x+2y)/(2x+y);
>   end
> overestimates the range once both x and y are proper intervals.
> However, if x is nonzero, we can rewrite it in the form
>   z = 2-2/(2+y/x)    =: f_1(x,y),
> and if y is nonzero, we can rewrite it in the form
>   z = 1+1/(1+2x/y)   =: f_2(x,y).
> Since x and y appear only once in f1 and f2, their interval evaluation
> produces the precise range in case that 0 not in x for f1 and 0 not
> in y for f2.
>
> Due to the exceptions, one expects that the decoration concept can
> be used with advantage to compute good range enclosures reliably.
> To get the best of all, we define the enclosure function
>   function f = fgood(x,y)
>     f=(2x+2y)/(2x+y);
>     f1=2-2/(2+y/x);
>     f2=1+1/(1+2x/y);
>     f = f intersect f1 intersect f2
>   end
> and use it as part of the larger interval calculation. We illustrate
> several concrete cases.
>
> (i):  x=[1,inf], y=[-1,1]. Here
>   f=([0,inf],def);
>   f1=([0,4/3],saf);
>   f2=([0,inf],con);
>   fnaiv(x,y) = ([0,inf],def);
>   fgood(x,y) = ([0,4/3],saf),
> The naive evaluation gives a useless result.
> The good evaluation proves that the function f is continuous and
> bounded by [0,4/3] on the box (i).
>
> (ii):  x=[1,2], y=[-1,1]. Here
>   f=([0,6],saf);
>   f1=([0,4/3],saf);
>   f2=([0,inf],con);
>   fnaiv(x,y) = ([0,6],saf);
>   fgood(x,y) = ([0,4/3],saf),
> The naive evaluation gives a safe but poor result, proving that the
> function f is continuous and bounded by [0,6] on the box (ii).
> The good evaluation proves that the function f is continuous and
> bounded by [0,4/3] on the box (ii).
>
> (iii): x=[-1,1], y=[3,4]. Here
>   f=([1/3,10],saf);
>   f1=([0,inf],con);
>   f2=([8/5,4],saf);
>   fnaiv(x,y) = ([1/3,10],saf),
>   fgood(x,y) = ([8/5,4],saf),
> The naive evaluation gives a safe but poor result, proving that the
> function f is continuous and bounded by [1/3,10] on the box (iii).
> The good evaluation proves that the function f is continuous and
> bounded by [8/5,4] on the box (iii).
>
> (iv): x=[-1,1], y=[3,inf]. Here
>   f=([0,inf],def);
>   f1=([0,inf],con);
>   f2=([8/5,4],saf);
>   fnaiv(x,y) = ([0,inf],def);
>   fgood(x,y) = ([8/5,4],saf),
> The naive evaluation gives a useless result.
> The good evaluation proves that the function f is continuous and
> bounded by [8/5,4] on the box (iv).

Attachment: intersection.pdf
Description: Adobe PDF document