2 points on language. Continuing

[D. Tweed]

On Fri, 24 Aug 2001, S.D.Mechveliani wrote:

> I am skeptical too.
> Anyway, if a compiler `knows' the word  CommutativeRing, 
> knows that by definition,  CommutativeRing  requires 
> associativity, commutativity ..., observes the instance  
> CommutativeRing T  for some type T  in some program, sees further
>                       
>                        expr = (2*a + b) - (a+a)  :: T 
> 
> and sees the language version (compiler) flag     -fignore-bottom,
> (something of this sort) then, has it right to convert  
>                          
>                        expr --> b :: T
> ?
> To my mind, there is something more in this than intension.
> In practice, the users do not write explicitly such expressions as 
> expr. But they write them implicitly, by applying functions in 
> special cases, for example, one has  f(x,y)  and applies  
> f(x,2*x) ... 

On a purely pragmatic note ( :-) ) these optimisations can't necessarily
be safely used in three of the four most common cases, namely Int, Float
and Double because of the restricted range of intermediates. In
particular, somewhere in my copy of the source code for MetaFont Donald
Knuth has a routine containing (from memory):

t <- (p-q) + p; {compute t=2p-q without overflow; let us hope an
optimising compiler does not `optimise' this to 2*p-q}

There's a thread on the gcc mailing list (`Unsafe FP optimisations' I
think) that covers some of the even less obvious things that can happen in
floating point. Clearly people who write code which is both likely to use
the entire range of a numeric type and also do enough reasoning to know
that they're particular sequence of operations does not overflow even
though other `equivalent' reorderings will, is a set of measure zero.
However I wouldn't think it was reasonable to ignore the possibility the
program writer knows what he's doing better than the programmer. (In the
fourth case, Integer, there're no problems that I can see with these
optimisations.)

So the potential benefits of optimisations based on commutativity and
associativity seem to be restricted to Integers and non-elementary numeric
types and algebraic types.

___cheers,_dave________________________________________________________
www.cs.bris.ac.uk/~tweed/pi.htm |tweed's law:  however many computers
email: tweed@cs.bris.ac.uk      |   you have, half your time is spent
work tel: (0117) 954-5250       |   waiting for compilations to finish.