From: "Nate Hayes"<nh@xxxxxxxxxxxxxxxxx>
To: "P1788"<stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: Include language bindings? Re: Draft Standard Text, V02.1
Date: Tue, 16 Mar 2010 10:04:24 -0500
I think to study the algebraic properties of intervals and make sure these
semantics are clearly delineated in the standard will be helpful along this
direction. For example, if an implementation violates the algebraic
properties, then it would be clear the implementation is non-conforming.
Also, if some sorts of expression rearrangement are allowed, this will
particularly ensure various compiler optimizations by different vendors will
be more consistent accross implementations.
Nate
When Nate speaks of the algebraic properties of intervals
he is including issues peculiar to interval expressions
which have no analogy among real or floating-point
expressions.
Let me illustrate with 3 different ways of evaluating some
polynomial pp(xx):
pp = ((((c0*xx + c1)*xx + c2)*xx + c3)*xx + c4)*xx + c5;
tt0 = c0;
tt1 = tt0*xx + c1;
tt2 = tt1*xx + c2;
tt3 = tt2*xx + c3;
tt4 = tt3*xx + c4;
pp = tt4*xx + c5;
tt[0] = c0;
for (i = 1; i< n; i++) tt[i] = tt[i-1]*xx + c[i];
pp = tt[n-1];
All are exactly the same. If implemented in floating-point,
all would be implemented with exactly the same sequence of
floating-point operations. (Let's pass on the FMA issue for
now.) In a very real sense, all have the same 'meaning'.
However, as we discussed at length in the stds-1788-er
subgroup, the resulting interval would be unnecessarily wide
unless one recognises that each instance of the interval
variable 'xx' are the SAME variable. That is, all of the
instances co-vary rather than vary independently of one
another.
Nate calls this an 'algebraic' property of the expression.
And while this observation may be arrived at algebraically,
I believe it is a mistake to think of it in this way.
Co-variance is not an algebraic property. And the way we
must account for it is peculiar to interval expressions
apart from their algebraic properties.
(There are mathematical objects that deal with the issue of
co-variance in different ways. Probablity is one. The
mathematics of motion on continuous curved surfaces is
another. Intervals is different from both.)
Now, part of what Nate is trying to preserve here is the
very clever work he& others have done in looking at
expressions& algebraically reformulating them in a way
which minimizes the width of the resulting interval to
something more closely resembling the 'actual' variance
available in the expression. While this reformulation
is itself a reinterpretation of the expression beyond that
which is written in the source, it is often essential to
obtain adequately narrow intervals.
Nate is right. We must have these optimizations available
if we are to present meaningful results.
But look at the difficulty the compiler faces in implementing
these things.
In the first expression, all that is needed is to recognise
that each instance of 'xx' is the same interval variable.
In the second expression, this observation must be extended
beyond each assignment. And in the third, it must be extended
in time through each iteration of the loop.
Further, if we are to have a standard which is reproducible
across all implementations, any modification of an expression
beyond that which is written in the source must ITSELF be
standard in a way that the programmer can predict. These
modifications (which often involve separating the positive
coefficients from the negative ones) must be either discoverable
at compile time or possibly reformulated on the fly.
At the time we had this discussion in the stds-1788-er subgroup,
I took a hard line& said that the default must be to use no
reinterpretation of the expression beyond that which is written.
I may have erred in that position.
Still, I believe that the programmer must be able to predict
exactly how the expressions written into the source are to
be evaluated. So if we are to make 'algebraic' optimizations
they must be THEMSELVES standard& clearly spelled out in both
the 1788 document& the specification of the language itself.
I have insufficient compiler experience to know how much this
is asking of our target compilers. Others will have to fill
in with their expertise.
It may still be true that no reformulation of any kind is the
correct default. But Nate& others have convinced me that
these sorts of optimizations must be clearly spelled out in
our standard& offered to the programmer in some way.
Have you got your toes wet yet, folks?
You're still in the shallow end.
Wait until you have to dive into the matrix expression pool.
That one can be intractably deep.
Exponentially so. :-)
Enjoy,
Dan