Can referential transparency be assumed when dealing with floating-point arithmetic?

Question

A pure function is assumed to produce the same outputs given the same inputs. Suppose an (otherwise) side-effects free function computes with floating-point numbers. Due to numerical error, these outputs may differ (dependent on the system, parallelism, compiler optimisations ...) For instance https://stackoverflow.com/questions/2342396/why-does-this-floating-point-calculation-give-different-results-on-different-mac. So technically the function is not referentially transparent.

A different but related issue is when we define an addition monoid over floating-point numbers. The key underlying assumption, in FP, is of addition associativity, which is violated under finite precision: cf. http://www.walkingrandomly.com/?p=5380 for a basic example.

Is there any practical relevance of such violations to functional programming? If not, should we simply assume referential transparency? Or should we strive for maximal RT, eg, by choosing a language with better reproducibility of numerical results at the expense of their precision?

Answer 1

Is there any practical relevance of such violations to functional programming?

I think you've made a pretty clear case that the answer is 'yes'.

If not, should we simply assume referential transparency?

The only way I can see this being OK is if the only thing you care about is whether the results are approximately the same. But this has major pitfalls since small inconsistencies can become much bigger when multiplication and division are involved.

Or should we strive for maximal RT, eg, by choosing a language with better reproducibility of numerical results at the expense of their precision?

I don't think you need to reduce precision. What would eliminate these issues is to use a type that avoids using binary fractions to attempt to do math with numbers in another base (and/or doesn't have all the historical weirdness of floating-point.) A type with infinite decimal precision would work as would a type with fixed decimal precision. If you want it to occupy the same space as the floating-point types, you might have to sacrifice some precision.

Answer 2

It all depends on the quality of your implementation (and sometimes the implementation will have to give up speed to preserve properties of the implementation that you want).

In C, C++ etc. the exact same statement on the same implementation could give different results. For example, in a loop all even iterations might calculate a result one way, and all odd iterations might calculate it in another way. That's the most extreme case. Less extreme: Same code in different places might give different results. Same code on two different runs of the program might give different results. Same code on two different implementations might give different results. I would assume that only the most extreme case - the same statement giving different results - would be a problem as far as your question is concerned.

Whether this happens should be under control of your implementation. But the example that you gave (two implementations giving different results) is not a problem (well, it's a problem, but completely unrelated to referential transparency). Your implementation just has to guarantee that on the same program run, executing the same code with the same data once, multiple times, delayed, whatever, will always give the same result. Even having two different functions that ought to give the same results but don't isn't a problem in that respect.

Of course your language is free to define floating point arithmetic in a way that gives less freedom to the implementation and the problem goes away.

Answer 3

The violation of referential transparency is a problem iff you build on it. One can build on it only by reasoning about a function, and in that reasoning actually using the RT property. Feeling from your text : i guess : at the place where the referential transparency is violated [by the under-specification of floating point calculation] [for example inter-computer communication] : you do not even apply functional programming. The whole software system does not need to be expressed fully in a functional way in order to enjoy the benefits of functional programming. With other words : the application of functional programming can be partial, and still be enormously beneficial. Functional programming is not an (all or nothing) but a (the more the better) paradigm.

You worry about the violation of some algebraic properties by floating point operations. This issue is not strongly related to functional programming, as algebraic reasoning and functional programming can both be practiced without the other.

But the worry is still valid. Those algebraic properties build on an equality function on the number type. If that equality test is IEEE-defined [the default in most programming environments], then the floating point number summation is not associative, hence the type can not truly implement a Semigroup interface. But one can wrap that number type into an "Approximate" wrapper type, lift the summation function of the raw number type to the level of Approximate and give an approximate equality test function for Approximate [would return true constantly]. Then Approximate can implement Semigroup in the strict algebraic sense. This would be a principled coding practice, but some software engineers in some situations choose not to undergo the practical hassle, and rather just remember that the Semigroup implementation of the raw floating point number types should be interpreted in an approximate sense.