Re: [boost] [review][constrained_value] Review of Constrained ValueLibrary begins today

Subject: Re: [boost] [review][constrained_value] Review of Constrained ValueLibrary begins today
From: Stjepan Rajko (stjepan.rajko_at_[hidden])
Date: 2008-12-06 19:17:00

On Sat, Dec 6, 2008 at 4:07 PM, Gordon Woodhull <gordon_at_[hidden]> wrote:
> Robert wrote:
>>
>> The epsilon solution has already been proposed, but as I understand this
>> (correct me if I'm wrong) it wouldn't work either:
>>
>>        > From: Zach Laine
>>
>>        > Yet another use case would be "close enough is good enough".  If
>> the
>>        > bounds are within a user-defined epsilon of either boundary.
>>
>>        If I understand correctly, this does not solve the problem either.
>> Let's
>> assume you have two values: x and y, where x = y + eps (eps being the
>> user-defined margin of error). One comparison of x and y would indicate
>> their
>> equality (the difference is not greater than eps), while another one might
>> not
>> if x got truncated in the meantime (and y didn't).
>
> Thanks, I understand the problem now.
>
> I think we are all agreed that the library is orthogonal to any concerns
> about floating point and nothing needs to be changed in the code.  IMO the
> warning should be toned down in the documentation.  I wish the definition
> that Stjepan suggests were possible, but I don't see how a test can be
> designed that only only switches from unsatisfied to satisfied.
>

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).

Stjepan