Re: Draft decoration system for discussion
On 2012-12-01 10:04:08 +0000, John Pryce wrote:
> I attach a reasonably complete draft of the proposed decoration
> system to be used by the set-based interval standard. I submit a
> motion that this be accepted in outline. Specifically
[...]
Here are my comments. This includes parts of the latest comments in
our private discussions, concerning ill on non-empty.
* §8.8.2 and §8.8.3, about the ill decoration (and possibly emp):
from the text, it seems that only Empty could get this decoration,
but consider the following example (an expression put in SSA form
in order to name the intermediate results), similar to the one
given in §8.8.3:
y = x * x
z = - 1 - y (where 1 is converted to the [1,1] interval)
r = sqrt(z)
If x = ([-1,1],dac), this will yield, without trying to do anything
smart:
y = ([-1,1],dac)
z = ([-2,0],dac)
r = ([0,0],trv)
Now, if we consider the real point function f defined by the above
expression, one has f(x) = sqrt(-1-x^2), which is nowhere defined.
So, an implementation able to detect this could set the decoration
of r to ill, thus returning:
r = ([0,0],ill)
Note: one can choose another example by replacing x * x by x - x,
so that f(x) = sqrt(-1), which is also nowhere defined.
In the private discussion, John suggested that if an implementation
is smart enough to know that f is nowhere defined on the input box,
they it's smart enough to know that the range is empty, and return
the empty interval. But I disagree, because returning empty would
*not* be valid. Indeed x * x (resp. x - x) can mean two things:
1. An operation on the point function, evaluated on some interval.
Here the true result would be empty.
2. An interval operation. Here the true result would be [0,0]
(resp. [0,1] for x - x).
When considering decorations, the only valid interpretation is (1),
so that any decoration optimization based on (1) should be regarded
as valid (for decorations only).
When considering the interval part, the implementation cannot know
which interpretation is wanted by the user (possibly except with some
directive or other implementation-defined solution, but IMHO, that
would be out of the scope of the standard). So, in doubt, the result
should follow (2), which also contains the interval implied by (1).
Having different P1788 functions for (1) and (2) could be cleaner,
but I don't think this is necessary. As I've already said, a language
could provide 2 types/classes: one for (1), where the language could
allow expression/code rewriting before binding it to P1788 (that may
be interesting for parallelism), and one for (2), but still using (1)
to determine the decorations. If a language does this, you probably
won't get (non_empty,ill) with a clever implementation, but if only
one type is provided, you may get (non_empty,ill) as a consequence of
some compromise.
I also think that (non_empty,ill) could be obtained if the computation
of the interval part is done by some software (e.g. a library) but the
decorations can sometimes be determined by another software (e.g. the
compiler). This way of doing could make sense in practice since partial
support for decorations would not necessarily require much work, in
particular because (1) is considered, so that the compiler could reuse
features that are already available for integer and FP arithmetic,
such as value range propagation.
Note: user-supplied functions (§8.8.6) would still be the best way to
avoid problems related to correlated inputs.
* §8.8.3, about unbounded dac intervals: one can also obtain them
if the input interval is unbounded. The point I gave in the private
discussion is that if the user typically works with common intervals
(thus bounded on input), then obtaining an unbounded dac interval
would indicate an overflow, because the exact range (at Level 1) of
a dac function over a compact is a compact, thus bounded.
* §8.8.5, last sentence: "How this is done is language-defined."
I would say implementation-defined, in case the implementation would
just be a library, for instance.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)