Re: Position paper on implementing decorations
Nate, P1788
First, thanks to Dan Zuras I've found a few typos in my paper. The most serious is that in the worked examples, I forgot to implement the stickiness! That is, the Dxx decoration of a result is from the current operation only, but it should be "or"ed with the input Dxx's.
As far as I can see that only result that should change is in 5.1, v3=cos(v1) where the result Empty_D10 should be Empty_D11.
On 10 Jun 2010, at 17:46, Nate Hayes wrote:
> It is important for people to understand (and perhaps you, too, John), that
> propagating a tetrit by ANDing and ORing the individual (P,Q) bits is not
> equivalent to propagating the tetrit with bool_set semantics.
I need to spend some time studying how you define bool_set semantics before I come back to you on that. Which email, etc., should I look at for these definitions?
> For example, examining how the priority numbers 0, 1, 2, 3 propagate with
> bool_set semantics gives:
> sqrt(([-1,1],3)) + (Empty,0)
> = ([0,1],2) + (Empty,0)
> = (Empty,0)
>
> However, your "red" and "blue" sticky paper (e.g., Section 5.2) gives:
> sqrt(([-1,1],3)) + (Empty,0)
> = ([0,1],2) + (Empty,0)
> = (Empty,2) // This is bad!!
I think you haven't got it quite right. Writing Dxx for my (ND,SuD) bits, and Hx for the Hayes priority number, from 5.2 of paper the correspondence is
D00 = H3
D01 = H2
D11 = H1
D10 = H0
I get (showing both forms of the prit, and using | for logical or)
sqrt(([-1,1],H3=D00)) + (Empty,H0=D10)
= ([0,1],H2=D01) // I agree so far
+ (Empty,H0=D10)
= (Empty,H1=D11) // I disagree with you
Namely, D10 from current operation, as input box [0,1] x Empty is Empty,
then D(10 | 01 | 10) = D11 using inputs.
This means "nowhere defined, somewhere undefined". You have only given a *fragment* of a computation since the original inputs [-1,1] and Empty didn't both start with a clean sheet, meaning decorated H3=D00. But as far as it goes the final H1=D11 looks exactly right to me.
Let me convert it to what I regard as a complete computation:
function y = f(x1,x2)
v1 = x2
y = sqrt(x1) + v1
end
I compute
Y = f([-1,1], Empty)
Evaluation initialises with
1. x1 = ([-1,1], H3=D00)
2. x2 = (Empty, H3=D00)
It continues:
3. v2 = x2 = (Empty, H0=D10) // as in 5.4 of paper
(But v2 = cos(x2) or any other function does equally well.)
4. y = sqrt(x1) + v1
This is now as in your example, returning
Y = (Empty,H1=D11)
The first bit of D11 says "some elementary function during this evaluation of f was nowhere defined on its inputs".
True: this holds for the assignment (identity map) at step 3, also for the + within step 4.
From this we can deduce "f is nowhere defined on its input". True.
The second bit of D11 says "some elementary function during this evaluation of f was somewhere undefined on its inputs".
From this we can make no further deduction about f. Only when that bit is 0 can we do that.
> which is clearly a serious violation of the priority map. So the "Structural
> induction for DAGs" does not hold.
Can you say just where it fails?
A more realistic case than f above might be
g(x1,x2) = sqrt(x1) + 2*sqrt(x2),
which I write as
function y = g(x1,x2)
v1 = 2*sqrt(x2)
y = sqrt(x1) + v1
end
Let's give it two *nonempty* inputs:
Y = g([-1,1], [-3,-2])
Then I get, following my rules for constants,
v1 = ([2,2],H3=D00)*sqrt(([-3,-2],H3=D00))
= ([2,2],H3=D00)*(Empty,H1=D11)
= (Empty,H0=D10)
after which it reduces to Nate's example. Again, we correctly deduce g is nowhere defined on its input box X = [-1,1] x [-3,-2]. Therefore, if X is occurring in Nate's branch and bound algorithm, we know we should "discard" it.
Nate, I still have the impression you regard "domain" as an attribute of the final interval, rather than of the process that produced that interval.
John