Boost logo

Boost :

Subject: Re: [boost] [review][constrained_value] Review of ConstrainedValueLibrary begins today
From: Robert Kawulak (robert.kawulak_at_[hidden])
Date: 2008-12-08 11:12:12


> From: Stjepan Rajko

> The epsilon is what makes the difference. Suppose that the invariant
> condition that we want to enforce is:
>
> x < y
>
> The problem is that x (and perhaps y, but let's ignore that for
> simplicity) can at a later point in time go up or down by some dx as a
> result of truncation.
>
> If the condition function tests for x < y, the following things can
> happen when testing before truncation (I might have mess up some < or
> <= in there):
>
> 1. if x + dx < y, then the condition passes, and it will always pass
> even after truncation
> 2. if y <= x - dx, then the condition fails, and it will always fail
> even after truncation
> 3. if x < y <= x + dx, then the condition passes, but after truncation
> it can fail (*this is the problem*)
> 4, if x - dx < y <= x, then the condition will fail, but after
> truncation it might pass (this is unfortunate, but does not break the
> invariant - in any case, it can trigger the policy and the policy can
> either throw or force truncation and retest or whatever is
> appropriate).
>
> If we keep the invariant at x < y, but the condition actually tests
> for x + epsilon < y where epsilon >= delta, then you have x + epsilon
> < y ==> x < y (a passing test guarantees the invariant), as well as x
> + epsilon < y ==> x + dx < y (a passing condition test guarantees that
> the validity of the *invariant* won't change). Sure, the passing test
> does not guarantee that the results of the *test* don't change (the
> problem pointed out in the quoted text at the beginning), but we don't
> care about that - we just care that the passed test guarantees that
> the desired *invariant* does not change. In effect, we are throwing
> out case 3 above at the expense of expanding the interval in which
> case 4 (a much more acceptable case) occurs.
>
> Another way of describing this would be to say that the library should
> not necessarily require that the condition test passes if and only if
> the invariant is satisfied - it should only require that the test
> fails if the invariant is not satisfied (but if the invariant is
> satisfied, the test is allowed to fail).

So what's the conclusion in the context of separation of invariant and the test?
That we may end up having bounded float with value a bit greater than the upper
bound, but that's fine, because the difference will never exceed some
user-defined epsilon? Is the epsilon constant? The "delta" (difference between
extended and truncated value) may have a very big value for big numbers and very
small for small ones, so epsilon should rather be scaled according to the
magnitude of compared numbers.

Did I get things right so far?

Then why complicate things with epsilon at all? If we allow for values outside
of the bounds but only a "delta" away, we may simply stay with the "<"
comparison. Even better, I would love to see a solution to force truncation of a
value, so the comparisons are always performed on truncated values and we may
stay with the "test == invariant" approach.

And another issue is NaN -- it breaks the strict weak ordering, so it may or may
not be allowed as a valid value depening on the direction of comparison ("<" or
">"). I guess NaN should not be an allowed value in any case, but I have no idea
yet how to enforce this without float-specific implementation of within_bounds.

Regards,
Robert


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk