Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Version 2.11, Proposal for interval standardization

(I reply to the last 3 mails in this thread in one mail)

Thanks Michel for pointing out my typo, and most importantly
the consequences on reproducibility of these transformations.


Arnold Neumaier wrote:

Sylvain Pion schrieb:

[...]

Well, I *think* it is indirectly, but explicitly forbidden in your
current proposal, and that's the whole point.  The reason I think
so is that in your proposal, functions are defined in isolation,
and at best they each return the "tightest" accuracy, and the refer
only to their arguments.  So, if x=[1,1], evaluating x/[3,3] *must*
return an interval y which is the tightest result and not a singleton,
and y*[3,3] then *must* return the tightest of this, which is not
a singleton.  So the transformation to [1,1] is not allowed.


The standard is supposed to define interval arithmetic on machines,
not what people can do with it.


Well, this standard will serve, among other things, as a base for building
language standards.
So, my question is: if a C++ implementation performs the transformations
I mentioned, will it still be able to claim that it conforms to IEEE-1788,
or is it violating it?

Floating-point arithmetic, as in the IEEE-754-2008 standard, is subject
to many kinds of similar transformations.  Have a look at section
"10.4 Literal meaning and value-changing optimizations" in IEEE-754-2008
for example.

I don't see why IEEE-1788 should be any different here.
Thus we specify single operations, but not how they may be combined, and under which conditions better results are obtained. This is a matter of theory on interval methods, not of a standard. 

Theory tells (or does not tell) what gives best results in
infinite-precision interval arithmetic; the standard guarantees that
if you program this using a standard-conforming implermentation, you'll get correct enclosures of the theoretical result. 

A programming system with elaborate syntax transformation capabilities
can implement some or all of the theory - but then it must still call
routines that do the elementary operations. How to do these (and only
that) must be specified by the standard.


I think a description of valid transformations should be part of IEEE-1788,
just like there are some in IEEE-754 for floating-point arithmetic.

Your section 2.6 is even one of them, I just propose to improve it.

So far, you have not given any concrete arguments against what I proposed
(I mean, in terms of applications where this would be a problem to allow
tighter intervals for expressions if the containment property is maintained).



Moreover, if that was already allowed, it would automatically apply
to constants, and then you would probably not have felt the need
to add section 2.6 either... (?)


The point is that many compilers do constant folding at compile time,
while they cannot fold variables. Thus the user should have a way to
pass a constant that is to be accurate as a string.


Compilers don't fold variables, but they do a lot of expression transformations,
on floating-point or integers.  Things like -(-x) -> x, or (-a)+b -> b-a...
Some of these still conform to the relevant standards, some violate
the standards and compilers provide them only when you pass some special flag
(e.g. -ffast-math of GCC).

(I even implemented some of these transformations in GCC a while back,
for the sake of interval arithmetic...)


In constraint programming, constants behave differently than variables,
so tight enclosures for the latter are a benefit.


If some fields have higher requirements on interval constants, this is good to know,
and we can try to specify this in IEEE-1788.  Currently your section 2.6
only allows something, but does not mandate anything (apart from the possibility
to parse some text for some expressions, which I find orthogonal to the
tighter constant intervals issue).

In C++0x, there is a new facility named "constexpr".  This facility allows
to build compile-time constants for elaborate types such as interval,
and allows to force constant propagation through some functions, in order
to build such constants (Gabriel Dos Reis knows everything about it).

All this is specific to C++0x, but one could imagine, if IEEE-1788 specified
some additional requirements for some constant expressions over intervals,
that this would be implemented using this facility, rather than parsing
some text/string as your section 2.6 mentions.  One could also imagine that
the additional precision requirements (tighter intervals) -- if we end up
mandating something like that -- could be done by the compiler transparently,
and required by the C++-interval standard for such constants, maybe.

From a language point of view, this would be much cleaner than requiring

to build special constants from strings representing expressions.

So, my points are still:
- the notion of "text" is not relevant to the tight interval constants
 requirements of applications.
- the possibility of tighter intervals for expressions (combinations of functions)
 should not be restricted to the kind of expressions found in section 2.6,
 and it is useful to generalize it.
- if some application domains have special precision requirements for
 some interval constant expressions, we should maybe _mandate_ something
 (and not in terms of text).
My suggestion is to remove the special case of those constant expressions (which in fact only *allows* shaper intervals in this case), and replace it by a general authorization for the implementation to perform any such transformation. This could be phrased, I think, without any explicit list 
of transformations (which I agree would not be realistic).
I can suggest the following wording:

 For any expression combining functions over a set of input intervals,
 an implementation is allowed to return a shaper interval than the one
 required by the involved functions taken separately, provided that the
containment property is still ensured for the result of the expression, 
 for all possible real values in the input intervals.

 Examples of valid such transformations:

   - (1/interval(3))*3   ->  interval(3)
   - (x/2)*2             ->  x
   - sqrt(square(x))     ->  abs(x)


This would require talking about text containing variables.
I don't think so: I was not referring to text, I was referring to expressions, 
which are compositions of functions, basically.


The standard is supposed to be language-independent.


Of course.  But there is no particular language in the examples I mentioned.
I am only composing functions, this is an abstract concept easily built over
the "function" one which we already have.  We may want to have a look at
IEEE-754 if it provides good wording for this concept.


But expressions are usually parsed by the compiler, and are no
longer available in a language-independent form, unless passed as text.


That's not true: they are still available to the compiler, or any tool
that might access the internal compiler representation of the program.
Expressions are in the compiler's internal program representation, and
the compiler can do a lot of transformations on it (or any plugin that
may be hooked to the compiler if it has access to the internal representation).

And I agree that not only compilers can do such transformations, as you
mentioned.  But this is not a reason for preventing compilers from doing
them!  Traditional compilers can do the most "trivial" and easily proved
such transformations, and moreover, one can imagine that some complex
re-writing systems that you mentioned can be hooked into compilers.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature