Re: Revised version of Level 1 text (draft)
Nate Hayes wrote:
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.
You gave three interesting and important examples that help to clarify
the usage of the decorated semantics.
(i) Intersection of objects
---------------------------
> 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).
Here
A = {x | A(x)<=0},
B = {x | B(x)<=0},
where A(x), B(x) are arithmetic expressions, and an inequality is
supposed to be false if a subexpression is undefined.
We want to deduce information about
C := A intersect B,
D := A union B.
Since
C = {x | C(x)<=0}, where C(x)=max(A(x),B(x)),
D = {x | D(x)<=0}, where D(x)=min(A(x),B(x)),
this can be handled by ordinary interval evaluation of arithmetic
expressions, using min and max as binary arithmetic operations as in the
Level 1 text draft. We just evaluate the interval extension and at the
end check the decorated range enclosure.
No change in the semantics is needed, no false conclusions are generated
by the algorithm for deciding whether a box xx is inside or outside C or
D, or whether no decision is possible.
(ii) The example in intersection.pdf
------------------------------------
Here
A := {x | a(x) is defined},
B := {x | b(x) is defined},
and we want to deduce information about
C := A intersect B,
D := A union B.
Introduce an arithmetic operation def(x) on decorated intervals, where
def(x)=1 if x.dec=def, and def(x)=0 otherwise.
Then
A = {x | A(x)=1}, where A(x)=def(a(x)),
B = {x | B(x)=1}, where B(x)=def(b(x)).
Now
C = {x | C(x)=1}, where C(x)= A(x) & B(x),
D = {x | D(x)=1}, where D(x)= A(x) | B(x).
Again, this can be handled by ordinary interval evaluation of arithmetic
expressions, using def as unary and &, | as binary arithmetic
operations, as in the Level 1 text draft. We just evaluate the interval
extension and at the end check the decorated range enclosure.
A minor change in the semantics is needed, since def needs decoration
information to be evaluated, hence is not defined on bare intervals.
But with this change, no false conclusions are generated by the
algorithm for deciding whether a box xx is inside or outside C or D, or
whether no decision is possible.
However, if we apply the range evaluation machinery on a(x) and b(x)
only and then take naively the intersection, we get wrong results since
we take intersections of ranges of two different functions. But this
intersection is never meaningful for bare intervals, and hence should
not have a meaning for decorated intervals either. What one intersects
is the sets on the left hand sides of the definition, not ranges, and
this must be reflected in the choice of encoding.
(iii) The counterexample related to Appendix 2 of dec.txt
---------------------------------------------------------
This is indeed a valid criticism, and shows that my definition was
slightly sloppy, so that the intended theorem wasn't valid.
But it does not affect the current Level 1 text draft since that draft
is restricted to arithmetic operations, whereas intersection is a set
operation. At the time where the Level 1 text draft is extended to cover
the latter, there will also be theorems showing that no case has been
overlooked.
With the insight form the counterexample, Section 6 must be corrected as
follows:
6. Intersection and Union
The propagation under nonarithmetic operations is unspecified by
the above definitions of the semantics of decorations; cf. the first
paragraph of Section 6. This must therefore be analyzed partly on
different grounds, including important examples of use in algorithms.
In particular, since the set operations intersect and union are not
operations that would occur in functions, the original semantics of
decorations must be suitably extended to be maximally useful in the
applications. Again, the rules are essentially determined by the
requirements for function enclosures, but allowing more complex
evaluation schemes than simple expression evaluation.
The intersection operation must cater for the situation where a function
(or an intermediate term in a function) can be expressed in multiple
ways as a (possibly not everywhere defined) expression.
For example,
f(x)= (x_1-x_2)/(x_1+x_2) = 2/(1+q)-1, where q=x_2/x_1.
The evaluation of the second expression gives the optimal range on
boxes where x_1 does not contain 0. Depending on the argument, it may
pay to evaluate both expressions and intersect the results.
(See Appendix 2 for a worked example.)
Thus if
f(z) = g(z) if g(z) is defined and f(z) = h(z) if h(z) is defined,
we must be able to get optimal information on the range of f on zz
from the available information on g and h on zz by intersecting
the decorated intervals g(zz) and h(zz). This requires that
(gg,dg) intersect (hh,dh) = (ff,df),
where
dg>dh --> (ff,df) = (hh,dh),
dh>dg --> (ff,df) = (gg,dg),
dg=dh -->
if gg disjoint hh --> (ff,df) = (Empty,emp),
else --> (ff,df) = (gg intersect dh,dg).
The union operator (i.e., the interval hull) must cater for the
situation where a function (or an intermediate term in a function)
is expressed for different ranges of an argument by different
expressions. For example, if
f(z) = g(z) when z>=0, and f(z) = h(z) when z<=0,
we must be able to get optimal information on the range of f on zz
from the available information on g on [0,sup(zz)] and h on [inf(zz),0]
by taking the hull of the union of the decorated intervals
g([0,sup(zz)]) and h([inf(zz),0]). This requires that
(gg,dg) union (hh,dh) = (ff,df),
where
df=ill || dg=ill --> (ff,df) = (Empty,ill),
otherwise
df=dg=emp --> (ff,df) = (Empty,emp),
otherwise (with min, max in the < ordering)
(ff,df) = (ff union gg,max(con,min(dg,dh))).
These rules also ensure that we can obtain valid information by
evaluating f on zz by splitting: If zz is covered by zz1 and zz2
then both f(zz) and f(zz1) union f(zz2) (and hence also their
intersection) are valid enclosures of the range of f on zz, with a
valid decoration.
For example, for f=sqrt and zz=[-4,4], we get for safe input decorations
f(zz)=([0,2],con).
If we split zz1=[-4,-1], zz2=[-1,4], we get
f(zz1) union f(zz2)=(Empty,emp) union ([0,2],con) = ([0,2],con),
whereas if we split zz1=[-4,1], zz2=[1,4], we get
f(zz1) union f(zz2)=([0,1],con) union ([1,2],saf) = ([0,2],con).
To avoid possible ambiguities in the decoration semantics for
nonarithmetic operations, I propose to require the following default
rule:
All nonarithmetic operations that make sense for undecorated intervals
but are not explicitly motivated and specified by the standard operate
on decorated intervals by ignoring the decorations. In particular, the
output is not decorated.
(So programmers are responsible for checking the decorations before
applying these operations, thus ensuring that they are aware of what
they do. Since such operations are used rarely, this seems reasonable.)