[std-interval] Draft standard based on csets

Sylvain Pion Sylvain.Pion at sophia.inria.fr
Sun Jul 9 12:51:16 PDT 2006


Dear George and the ISL team,

I have read through your modified proposal as well as your cset paper.
They contain interesting ideas, and many should be integrated in
the final proposal.  As far as I understood them, it seems that many
of these ideas are orthogonal to csets, so, for the purpose of
discussion here, it would be nice to consider them separately.
In this mail, I will focus on the cset model itself.

As far as I understood, the cset approach is mostly motivated by
the needs to handle :
1- discontinuity of functions (e.g. division by zero)
2- construction from floating-point infinity
3- re-association capabilities
(am I missing other important ones ?)

In practice, the cset model implies that intervals are enlarged so
as to verify new properties.  To define the cset functions, you have
to look at how the function is defined outside the input intervals,
and take all possible limits of values of the function outside the
intervals. (forgive the short imprecise summary).

This produces "strange" effects, like :
- [0;+inf]*[0;+inf] returns [-inf;+inf], whereas "the simple" model
   can simply return the more "natural" [0;+inf].
- 1/[0;1] returns [-inf;+inf]  ([1;+inf] for the "simple" case)
- sign([0;5]) returns [-1;1] ([0;1] for the "simple" case)
You mention these effects in your paper, although you do not really
propose a way to take care of this.

I understand that the cset model brings in some consistency, which
is a most definitely desired feature.  But it does not come without
constraints.  I am also not convinced that the same kind of consistency
cannot be achieved using a non-cset model.

The main question I have is that I do not find convincing arguments,
in practice, to justify the cset model.  For example, the wrap-around
model is nicely motivated by functions like : f(a,b) = 1/(1/a+1/b).
I miss the equivalent for csets.  I believe that, in the 3 main
reasons listed above, 1- and 3- can be specified in a non-cset model
as well (by a non-cset or "simple" model, I mean a model which does
not have to take into account values of functions outside the input
intervals, this is the most distinctive feature of cset, and the most
problematic to me).
For 2-, I am not sure yet what to think, but I hardly see this as a
reason to justify the cset cost anyway.  I see this cost as :
- larger intervals
- slightly slower implementation
- more complicated definition/specification


As far as the proposal is concerned, we can still propose several
models.  The std::interval could have a policy parameter specifying
the model.  If we do that, we add a lot of complexity to the proposal,
which really needs to be motivated.  We are already not considering
the integration of a wrap-around model or Kaucher model (is it a
mistake ?).  I believe that most people care about speed and tightness
of the intervals, so if we need to choose one model, my current
personnal opinion is that a (well-defined of course) non-cset is
the best choice.


I would be more than happy to read opinions of interval experts on
this issue.  Concrete use-cases requiring csets would be a must.

-- 
Sylvain



More information about the Std-interval mailing list