Re: Constructors & decorations
Dan and John,
I, for one, REALLY appreciate the care you are giving to this. We are all the wiser for your wisdom.
I continue to advocate for simplicity to the extent possible.
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
On Feb 23, 2010, at 6:17 AM, Dan Zuras Intervals wrote:
>> Subject: Re: Constructors & decorations
>> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
>> Date: Tue, 23 Feb 2010 08:58:05 +0000
>> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> Folks,
>
> I will try to give brief but detailed responses to
> John's comments here.
>
> I will fail on the brief part. :-)
>
> I would normally edit this down a bit to make it more
> readable for everyone but as John & I both chose to
> define nomenclature in our arguments, its hard to
> eliminate that & still have the arguments make sense.
>
> The best I can say is that, in summary, we basically
> agree on the nature of decorations & are arguing the
> nature of the wings on the angels dancing on the head
> of our pin here.
>
> Unless that interests you, you can safely ignore this
> note.
>
> John,
>
> If we go further, perhaps we can take this offline
> until we come to some understanding before we bug
> everyone else with this.
>
>>
>> Dan & P1788
>>
>> I will try to get to grips with Dan's specific examples
>> about decorations on 9 Feb.
>>
>> For brevity I write V, D, C, B for the Valid, Defined,
>> Continuous and Bounded attributes and + 0 - for the
>> values "is", "possibly", "not". Then e.g., D0 means the
>> same as possiblyDefined. And e.g.,
>> ([1,2],V+,D0)
>> means interval [1,2] with its V attribute set to +, its
>> D attribute set to 0, and not saying anything about its
>> C and B attributes.
>>
>> Response interspersed below.
>>
>> On 9 Feb 2010, at 23:44, Dan Zuras Intervals wrote:
>>
>>>> On 9 Feb 2010 22:24:56 +0000, John Pryce wrote
>>>> Dan
>>>> On 9 Feb 2010, at 21:54, Dan Zuras Intervals wrote:
>>>>> This may be a bit of a topic drift but what is the difference
>>>>> between Valid & Defined?
>>>> Ah. There are 3 conceptually different groups.
>>>>
>>>> isValid: The result of a valid constructor call, or of an operation =
>>>> whose inputs were isValid. So recursively, an interval value that makes =
>>>> sense, "not NaI".
>>>>
>>>> isDefined, isContinuous]: Only make sense in the context of evaluating =
>>>> the interval version yy=ff(xx1, ..., xxn) of a point function y=f(x1, =
>>>> ..., xn). If the original xx's are all isDefined [resp. isContinuous], =
>>>> and the resulting yy is isDefined [resp. isContinuous] then one has =
>>>> proved f is defined [resp. continuous] at each point of the input box =
>>>> (xx1 cross ... cross xxn) in R^n. (cross = cartesian product).
>>>>
>>>> isBounded: Unlike the others, not about history. Just says that xx is =
>>>> mathematically bounded even though a bound might have overflowed to oo.
>>> ...
>>> John,
>>>
>>> While all of this makes sense to me I'm not sure it answers
>>> my questions. Let me try some examples:
>>>
>>> Let f = sqrt(x^2 - 1)
>>>
>>> So, if I understand your argument correctly, the evaluation
>>> of yy = ff(xx) is,
>>>
>>> (1) Valid (Bounded) iff the input is Valid (Bounded),
>> Yes.
>>> (2) Defined (Continuous) for all Defined (Continuous) inputs
>>> except for xx such that xx \intersect (-1,1) is non-empty,
>> Yes again. I make it that if xx is D+ then yy is
>> D+ if xx \intersect (-1,1) is empty,
>> D- if xx \subseteq (-1,1),
>> D0 otherwise.
>> The situation for C is the same, in this example.
>
> Ah, in this case your interpretation of the uncertainty
> associated with the word 'possibly' is in the fact that
> the result in the D0 case was evaluated on an interval
> that containes SOME numbers that are defined & SOME
> numbers that are not. Therefore, we say the resulting
> interval is 'possiblyDefined' in that, for any given
> point in the input interval, it might or might not be
> defined depending on which point you are looking at.
>
> I'm OK with this interpretation of 'possibly' in this
> case.
>
>>
>>> Also ff could return possiblyBounded in the case where the
>>> input is Bounded but the intermediate expression x^2 overflows.
>> Ah, no! The whole point of Bounded, as I understand it, is to
>> remember a _mathematical_ truth that floating-point may have
>> forgotten. Suppose BIG is such that BIG^2 overflows. Then
>> yy=ff([1,BIG]) is evaluated as sqrt([1,BIG]^2-1) =
>> sqrt([1,oo]-1) = sqrt([0,oo]) = [0,oo]
>> but the initial [1,BIG] is B+, and this is preserved all
>> through, hence yy is B+.
>
> So, if we break down the evaluation of ff into its
> component steps, you would have us propagate B as:
>
> xx = {[1,BIG],B+}
> uu = {[1,BIG],B+}^2 = {[1,oo],B+}
> vv = {[1,oo],B+} - 1 = {[0,oo],B+}
> yy = sqrt({[0,oo],B+}) = {[0,oo],B+}
>
> Again, I am OK with this.
>
> It allows us to distinguish intervals with infinite
> endpoints arrived at via overflow from those arrived
> at via the evaluation of a function that returned an
> infinity for some point in the input interval. Those
> would be B-, of course.
>
>>
>> This brings me to another point. When if ever should we use the
>> B0 value? Suppose xx is an interval containing 0. Is yy=1/xx
>> notBounded, or is it possiblyBounded? We believe that xx encloses
>> some "true set of values" ss, and we don't know ss contains 0.
>> So why should we assert yy is definitely B- ? It seems B0 is
>> correct. Someone help me with semantics here.
>>
>> Same with tan(xx) where xx contains \pi/2, say.
>
> These are the propagation issues I'm wrestling with.
> I believe that the evaluation of a function with the
> property that f(oo) = oo should propagate
> 'possiblyBounded' if the input is 'possiblyBounded'.
>
> But that just recursively begs the question.
>
> The most obvious example is the creation of an
> interval with a constructor along the lines of
>
> xx = intervalConstruct(1,oo,B0).
>
> This uncertainty derives from the original sin that
> the user was uncertain whether or not the input was
> infinite but knew no upper bound. I think this is
> contrived, though.
>
> You mention the example of tan(xx) on an input of,
> say, xx = [0,\pi/2+eps] where, \pi/2+eps is the
> smallest representable number larger than \pi/2.
> In this case the mathematical evaluation becomes
>
> yy = tan(xx) = [0,oo] \union [-oo,-1/eps]
>
> where the second interval represents the amount the
> tangent was evaluated just past its first pole.
>
> Unless some form of the tangent along the lines of
> Motion 11 is used, we probably have to return Entire
> in this case.
>
> The fact that xx may have been created slightly wider
> than was physically possible for the problem at hand
> is irrelevant. That is what was asked of the tangent
> function & that should be returned.
>
> Should we decorate it with B0 or B-? I will argue
> B- in this case on the grounds that any uncertainty
> due to roundoff error was not tracked in any way
> that might lead us to consider otherwise. In other
> words, it may be uncertain whether or not the physical
> problem can pass through this pole but it IS certain
> that the computed interval did so.
>
> I can think of no example off the top of my head that
> is less contrived than B0 caused because someone SAID
> it was B0.
>
> All that having been said, I don't think it will cause
> us any difficulty with the propagation rules.
>
>>
>> Dan continued:
>>> Now let f = 1/sqrt(x^2 - 1)
>>>
>>> I believe we have,
>>>
>>> (1) Valid iff the input is Valid,
>>> (2) Defined for all Defined inputs except for xx such that
>>> xx \intersect (-1,1) is non-empty,
>>> (3) Bounded (Continuous) for all inputs except for xx such
>>> that xx \intersect [-1,1] is non-empty,
>> I agree with you on all these, I think.
>>
>>> Note that this last is [-1,1] rather than (-1,1).
>> Yes
>>> And that overflow cannot happen in this case.
>>
>> Why not? With my BIG as above, let xx=[2,BIG], say. Doesn't
>> floating point compute
>> ff(xx) = ... overflow ... = 1/[sqrt(3),oo] = [0,1/sqrt(3)]
>> (upper bounded rounded up of course)?
>
> Ah, no. Well, an overflow in the floating-point
> evaluation of the intermediate expression can happen
> just as before. But, as we have dealt with that case
> unambiguously, there is no further overflow possible
> in the divide. There is an exact evaluation of 1/0
> which happens in this case but that means B- not B0.
>
> To extend the example above by one more step we have:
>
> xx = {[1,BIG],B+}
> uu = {[1,BIG],B+}^2 = {[1,oo],B+}
> vv = {[1,oo],B+} - 1 = {[0,oo],B+}
> ww = sqrt({[0,oo],B+}) = {[0,oo],B+}
> yy = 1/{[0,oo],B+} = {[0,oo],B-}
>
> All quite certain. Nothing possibly about any of it.
>
> I only mentioned that the overflow cannot happen because,
> to use a simpler example, the expression 1/(x - 1) may
> evaluate to oo for x = 1 but there is no eps small enough
> so that 1/eps overflows for x = 1 + eps.
>
> In any non-pathalogical floating-point system the exponent
> range far exceeds the precision. Thus the difference
> between two representable numbers near the middle of the
> range (like (1 + eps) - 1) is proportional to the precision
> so the reciprocal (1/eps) may be large but it is far FAR
> smaller than the range available.
>
> No overflow.
>
>>
>>> Do I have that correct?
>>>
>>> Now, can you give me an example of an interval that is Defined
>>> but not Valid?
>>
>> I believe not. I think the intention of Motion 8 is that once
>> an interval is set notValid, _all_ its other attributes become
>> meaningless. It has fallen into a black hole. So a V- interval
>> is essentially the same as NaI. It follows that all query-functions
>> on it should give results of maximum meaninglessness:
>> - Its other decorations should be D0 C0 B0.
>> - Its lower & upper bounds, midpoint, radius etc., should all return NaN.
>
> So it seems that you are reserving the interpretation
> of 'Valid' things to those things which are imported
> into intervals from other arithmetics. Constructors,
> converters, & the like.
>
> Does that not seem like a particularly narrow use for
> a decoration? Would not 'Defined' do as well?
>
> I say this because decoration bits might end up being
> expensive things some day. If we are successful &
> intervals find their way into hardware, decoration bits
> will become state bits. They will have interlocks &
> busses devoted to them. They will be saved on context
> switch. They will become involved in issues of
> parallelism & cache coherency. We should make sure
> they are useful.
>
> On the one hand, I will argue that parsimony suggests
> that overloading constructor issues into the 'Defined'
> decoration might be desired.
>
> On the other hand, before we are done I suspect we may
> need decorations beyond 'Defined', 'Continuous', &
> 'Bounded'. For example, 'Standard' (versus
> non-standard). As well as 'Accurate'. And possibly
> 'Empty'.
>
> While these things are expensive to future generations
> of hardware guys, failing to account for some important
> property carries its own expense to future generations
> of software guys.
>
>>
>>> As for Bounded, it seems to me that any result interval with
>>> an infinite endpoint is notBounded only if it were evaluated
>>> over a pole of some kind. Otherwise, in the overflow case,
>>> I think possiblyBounded is the best answer.
>>
>> Yes. And, because we only "do" outer enclosures, not inner ones,
>> we can never (except for cases like 1/[0,0]) be sure that we
>> _have_ evaluated over a pole; see above.
>>
>>> I think I would like to explore these issues further in a
>>> discussion of propagation rules.
>>
>> Thanks for raising these issues Dan. I also would like to look
>> at them in more detail. If the semantics of decorations turn out
>> to be too complicated to explain to the ordinary user, we need
>> to re-think.
>>
>> Regards
>>
>> John
>
> I think the semantics of decorations can be simplified
> to the same 3-state state machine for all decorations
> if they are named properly. Only the sense of the name
> (the usual thing versus the unusual thing) needs to be
> pinned down. Then the state machine will work.
>
> But I will save my arguments for a future note.
>
> Motion 11 is on the table today. We should devote our
> time to that.
>
> Also, the rest of my life has intervened to prevent me
> from writing up my thoughts on this matter so I'm not
> ready yet. :-)
>
> I'm sure there are many of you who know how that feels.
>
> Until then,
>
> Dan
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