Re: Motion on ``discontinuous'' decoration bit
P1788,
Just to fill in a few additional gaps from the discussion George mentions:
John is proposing a Level 1 definition of continutity (taken verbatim from
his comments):
"Interval algorithms that use fixed point theorems require to verify
continuity, in the form "the restriction of f to box X is everywhere defined
and continuous," i.e., the predicate
P(f,x) = (all a in X)C(f,a,X)
where
C(f,a,x) = "the restriction of f to X is defined and continuous as a".
There are several detailed formalizations of C(f,a,X); I propose the
following.
f(a) is defined, and for all e > 0 there exists d > 0 such that whenever
x is in X and f(x) is defined and abs(x-a) <= d, then abs(f(x)-f(a)) <= e.
Note: The "restriction" phrase is essential: consider the function f(x)
= floor(x)+1/2. Its restriction to X=[1,1.9] is everywhere defined and
continuous, being the constant 1.5...."
Accordingly, I'm proposing a Level 2 exception handling mechanism that uses
John's Level 1 definition. It is very similar to definition of the "domain"
tetrit in Motion 18:
-- Level 1 For interval box X = x1, x2, ..., xn, the definition of
"defined and continuous" is P(f,x) = C(f,a,x1,x2,...,xn) as given by John
-- Level 2 exception handling propagation mechanism. This is just a
simpler version of tetrits, i.e., for operands (x1,p1), (x2,p2), ...,
(xn,pn) of some operation f, where each (xi,pi) is a decorated interval
comprised of interval xi and sticky-bit pi, the resulting sticky-bit of the
entire operation is:
p1 & p2 & ... & pn & C(f,a,x1,x2,..xn)
if f is an interval extention of a point function and
p1 & p2 & ... & pn
otherwise (e.g., intersection and union). Here, the "&" is logical-and.
The rationale is that the finite sequence of operations leading to any
interval result forms -- from a conceptual perspective -- a Directed Acyclic
Graph (DAG). This DAG is the computation graph of the final interval result.
The Level 2 propagation mechanism ensures by structural inducation a proper
characterization of the computation graph via decorations.
Nate
----- Original Message -----
From: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
To: "P1788" <stds-1788@xxxxxxxxxxxxxxxxx>
Cc: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
Sent: Monday, August 30, 2010 4:36 PM
Subject: Fwd: Motion on ``discontinuous'' decoration bit
P1788,
For several days, there has been a VERY active discussion going on among
several people, and it should be exposed to everyone. Unfortunately, you
are being brought into the middle of the discussion, and I'm not willing
to summarize all that has gone before. Basically, we have been discussing
Motion on ``discontinuous'' decoration bit. Much of the discussion has
been on decorations for the results of intersect(), union(), and hull(),
which are NOT interval extensions of point functions.
George, replying to John (most recently):
Begin forwarded message:
From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
Date: August 30, 2010 10:50:56 AM CDT
To: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
Cc: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>, Dan Zuras Intervals
<intervals08@xxxxxxxxxxxxxx>, Christian Keil <c.keil@xxxxxxxxxxxxx>,
Nathalie Revol <Nathalie.Revol@xxxxxxxxxxx>, Ralph Baker Kearfott
<rbk@xxxxxxxxxxxxx>, "J. Wolff von Gudenberg"
<wolff@xxxxxxxxxxxxxxxxxxxxxxxxxxx>, Wiliam Edmonson <wwedmons@xxxxxxxx>,
Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
Subject: Re: Motion on ``discontinuous'' decoration bit
Folks
On 29 Aug 2010, at 17:31, Corliss, George wrote:
As Dan said, this takes some thought. Let's see if I grog this.
One impediment to my understanding is that I am accustomed to
considering such questions as, "Is this function defined?" or "Is this
function continuous?" while holding a domain in my hand. In the sense
we are considering, what I am holding in my hand is a RANGE. Domain and
computational graph are implicit. It takes my total concentration to
understand.
So, in my example, my suggestion that the "defined and continuous"
decoration of a disjoint union must be some form of "possibly bad" is
WRONG. The fact that we do not know something about some elements
(interval (1, 2), in this example) of the range of the computational
graph is true, but irrelevant. What matters is that the function
represented/implemented by the computational graph is defined and
continuous at all points in its DOMAIN (whatever that was). That
function MUST be defined and continuous if its operands were defined and
continuous on [0, 1] and [2, 3], respectively.
So, if I have it, hull() and intersect() are NOT especially problematic.
Good.
On 29 Aug 2010, at 17:39, Nate Hayes wrote:
You NAILED it right on the head.
I couldn't explain it better. Thanks.
I agree. Thank you George. I admit I was also being confused between
DOMAIN and RANGE, so I was thinking that "The fact that we do not know
something about some elements ... of the range" was important.
Right. I was (am?), and I think some others were, too.
We can have different functions on the different arguments, right?
Right
In general if we have several point functions f_i and input boxes X_i,
and evaluate Y_i = f_i(X_i), and then do a mix of hull and intersection,
using all these Y_i, then if the result Y has d&c = true we deduce EACH
f_i is d&c on its X_i.
(Where "d&c" means the "defined and continuous" decoration.)
Right
For instance, suppose in Baker's recent example we have two functions,
f(x)=1/x and g(x)=1/x^2.
Then we take A = [-1,-1/2] = f([-2,-1]),
and take B = [1/4,1] = g([1,2]) instead of RBK's f([1,2]).
Then, C = hull(A,B) = hull(f(A),f(B)) = [-1,1].
By Nate's rules this has d&c = true, from which we conclude
f is d&c on [-2,-1] and g is d&c on [1,2].
Yes, but when we are examining the decorated interval C, we no longer have
(explicitly) A and B. Decorations reflect the entire computational graph,
but they do not provide access to it.
If we want to find something different, e.g. "Is SOME f_i d&c on its
domain?", then I suppose we have to extract the d&c information into
ordinary boolean variables, and manipulate these explicitly.
You would have to examine the decorated intervals Y_i.
Have I got that straight?
I think so. Yes.
BTW, I agree about KISS and comments about complexity. This is why I
strongly recommend trying to whittle the actual definitions down to
something as minimalist as:
-- Level 1 definition of "defined and continuous" for a point function,
i.e., C(f,a,x) as John gives in his paper
-- Level 2 exception-handling propagation mechanism, i.e.,
p1 & p2 & C(f,a,x1,x2)
for point functions of form f(x1,x2) and just
p1 & p2
for intersection and union.
Nate, thank you for separating levels 1 & 2 in this way. You are right to
point out that at level 2 exceptions can't just grind to a halt with some
operations - there must be a propagation formula in all cases.
I am happy to revise the motion on this minimalist approach, but see
below...
All the rest of the theory and background relating to computation
graphs, DAG, domains, ranges, point-functions vs. non point-functions,
etc. might be useful to put into a rationale or annex. This will help us
elitists remember why we defined things the way we did. :-)
OK
But most software and electrical engineers I suspect aren't going to
care about those details, i.e., they're just going to want a "cookbook"
recipe to show them how to build a conforming implementation in software
or hardware.
Don't forget the application users. Don't forget the people who write
textbooks for application users, with titles like "IEEE-1788 interval
programming in C++/Fortran/whatever". These folk need a simple
explanation of how level 1 and level 2 decorations relate to each other.
So the "theory and background" MUST go into a rationale/annex, explained
as clearly as we can manage. It's not just the elitists who need it.
Yeah
I like George's words
We have been, and we must continue to be, sensitive to KISS. I guess
one path to simplicity is a very carefully worked-out, consistent, and
coherent level model.
And also his warning that whatever we do, people will misuse the system
and blame us. When they do, we need to be able to quote chapter and
verse.
Regards
John
Dr. George F. Corliss
Electrical and Computer Engineering
Marquette University
P.O. Box 1881
1515 W. Wisconsin Ave
Milwaukee WI 53201-1881 USA
414-288-6599; GasDay: 288-4400; Fax 288-5579
George.Corliss@xxxxxxxxxxxxx
www.eng.mu.edu/corlissg