Re: Include language bindings? Re: Draft Standard Text, V02.1

[Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>]

> 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