Fw: Tetrits and "stickiness"
RBK> The implications of this will require some additional thought.
Agreed.
RBK> if an argument is not totally in the domain of part of the _expression_, we need to say the argument is not wholly within the domain of the entire _expression_.
I think that's generally true, but there are some exceptions; for example, if you implement
d = c ? a : b;
by evaluating both a and b then using c to "select" one of them, only the selected one matters, just as if you evaluated it with a test and conditional branch choosing whether to evaluate a or b..
Another one to think about is
x = y * z;
where y is the singleton [0,0] and z has had a domain (or other) error. Should that be propagated to x? Should it depend on the kind of error or the value of z?
RBK> Do we need both the sticky part and the non-sticky part?
I don't think so, if we handle it carefully. When somebody cares where in an _expression_ a problem occurred, they should ask for it to be checked after each step, and one part is enough. When they don't care about the details, only the sticky part matters. Generally the main question is: Is the result of the calculation is valid, or did some error occur?
Other opinions? Other experience?
- Ian McIntosh IBM Canada Lab Compiler Back End Support and Development
----- Forwarded by Ian McIntosh/Toronto/IBM on 04/15/2010 10:03 AM -----
From: |
Ralph Baker Kearfott <rbk@xxxxxxxxxxxx> |
To: |
Ian McIntosh/Toronto/IBM@IBMCA |
Date: |
04/15/2010 09:40 AM |
Subject: |
Re: Tetrits and "stickiness" |
Dan et al,
The implications of this will require some additional thought. In
particular, how the tetrits will actually
be used in computations should be reviewed carefully. My guess is that,
if an argument is not totally in
the domain of part of the _expression_, we need to say the argument is not
wholly within the domain of
the entire _expression_. This would be important to know in the case of
computational fixed point
theorems. To remind people, an example is
g(x) = \sqrt{x}+1, and take \x = [-2,4]
Then, g([-2,4] = {[1,3],{domainIn,domainOut}}, but the Brouwer fixed
point theorem
would say there is an x in [1,3]\subset [-2,4] with g(x)=x, except for
the DomainOut tetrit.
From this point of view, the sticky part is most important. (Note that
I have not distinguished
sticky and non-sticky here.)
The main potential use of the non-sticky part would be to find out where
in the _expression_
(through a user check of the tetrit, say) the domain condition is violated.
Do we need both the sticky part and the non-sticky part? If we don't,
can we simplify
this even more? I'd be interested in Arnold's and John's opinions,
among others. Otherwise, I don't
see adding an additional bit a problem, but what do hardware people
think? Perhaps we even have
an extra bit of "Lagniappe" (as we say here in South Louisiana), since
perhaps we could even carry a fourth
bit free of charge to make it an even half-byte :-)
Baker
On 4/14/2010 8:41 PM, Dan Zuras Intervals wrote:
>>
>
.
.
.
> Nate,
>
> First let me say this is very clever& I like anything
> that might make the decorations more useful.
>
> It is a bit hard to follow on first reading but that's
> no big deal: We just define the 4 values to mean what
> we want them to mean& how we compute them is mostly
> a circuits issue.
>
> So, with that in mind, I'd say that any rearrangement
> of the 4 bit patterns is mostly as good as any other&
> yours is better than mine for this purpose.
>
> However,& you knew there was a however coming (:-), it
> is not the sqrt() that issues the final decoration but
> the next operation. That is, the domain error was not a
> domain error of the final operation but a domain error of
> the sqrt(). As you are assuming it was a dyadic operation,
> let's assume it was an add just for argument's sake.
>
> So, the _expression_ is:
>
> xx = [1,2];
> yy = [-2,1];
> rr = sqrt(xx) + sqrt(yy);
>
> and the question becomes what is the decoration on rr&
> what does it mean. If we propogate the decorations on the
> sqrts in the manner you suggest we would get (1,0) meaning
> that the result of the add is something like:
>
> rr = {[1,1+sqrt(2)],{domainIn,domainOut}}
>
> as well as any other decorations that don't concern us for
> now.
>
> Now, I will assume that what you meant to say in the above
> propagation rule is that the propagated decoration is the
> infimum of operands TOGETHER with the decoration for this
> operation. (Correct me if I'm wrong here.) I also assume
> that the proper domain of the add is [entire]. (That IS
> right, isn't it?)
>
> So, the user gets rr, looks at the decoration& wonders:
> Is that OK or is there something wrong with my calculation?
>
> The user is kind of lucky in this case in that the domainOut
> cannot have come from the add. The domainIn could have been
> inserted by the add but your assignment of decoration values
> also has the merit of returning (0,0) had either input been
> (0,1) or (0,0) (an empty interval operand). So the user can
> deduce that the input operands must have been either (1,1)&
> (1,0) or both (1,0). The obvious thing is to suspect one or
> the other sqrt& trace back from there.
>
> All in all, not bad.
>
> Still, the decorations as we have been discussing them have
> a flavor of the 'exceptional' to them not unlike the flags
> in 754. Now, I do not mean by that that we should consider
> things like the 754 flags. They have been more pain than
> they are worth in the last 3 decades, IMHO.
>
> But I AM suggesting that the thing about decorations we want
> to retain as sticky is that which concerns us, namely the
> information about anything exceptional that happened for this
> operation or in the past.
>
> In the case of the 'domain' decoration that would mean keeping
> information any past domain errors around for future diagnostic
> use.
>
> Now, my first thought is to expand the tetrits to 3 bits (an
> octit, perhaps? :-) with the first two bits giving information
> about the status of this last operation only& the third bit
> collecting past exceptional behavior as sticky.
>
> In your example that would look something like:
>
> xx = {[1,2],{}}; /* just to start clean */
> yy = {[-2,1],{}}; /* just to start clean */
> zz = sqrt(xx) = {[1,sqrt(2)],{domainIn}};
> ww = sqrt(yy) = {[0,1],{domainIn,domainOut}};
> rr = zz + ww = {1,1+sqrt(2)],{domainIn,wasDomainOut}};
>
> In this case there is not propagation rule for the first two
> bits as they are a function of the current operation only.
> The sticky bit (wasDomainOut, or whatever) would be the 'or'
> of all of the input domainOut's in the input sticky's. That
> way the fact the the domain error was from some previous
> operation does not depend on the luck of the operation& the
> other bits are as simple as the interval calculations themselves.
>
> In this case, the status can just be read off:
> domainIn = true means that the add could handle both
> operands,
> domainOut = false means that nothing was exceptional
> to the add,
> wasDomainOut = true means that some previous operation
> had operands exceptional to THAT operation not
> the add.
>
> Still, this involves more bits.
>
> Yours does not.
>
> I'm not sure which is best.
>
> Mine has K.I.S.S. on its side.
>
> Yours has fewer bits& almost the same information.
>
> What does everyone else think?
>
> Got to go now. The rest of my life has come calling. :-)
>
>
> Dan
>
>