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?

  • 2
    Can you provide an example? To my knowledge, a floating point computation error is consistent across the board. – Neil Jan 31 at 14:31
  • 1
    For example, non-associative addition: 0.1 + (0.2 + 0.3) = 0. 59999 ... and (0.1 + 0.2) + 0.3 = 0.600000000000009. Computation error: multiplication (or inversion) of large matrices (eg in Matlab) on different machines on 32 vs 64 bit machines; lots of discussion on people.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf . Also, stackoverflow.com/questions/2342396/… – Tupolev._ Jan 31 at 15:20
  • 3
    Ok, but those are two separate functions. One adds a and b first and the other adds b and c first. I promise if you were to run one or the other multiple times, the result would be the same. Of course you could make it randomly pick which order to add them together, but then it would no longer be a pure function. – Neil Jan 31 at 15:28
  • 3
    @Neil: FP error is not guaranteed consistent in many languages because FP registers are higher precision than FP stack slots, and compilers are free to choose whether to enregister locals at their whim. Note that jit compilers run at runtime, so the runtime behaviour of any float operation on locals can change arbitrarily at runtime based on the phase of the moon. Numerous SO questions about C# cover this issue. – Eric Lippert Jan 31 at 15:40
  • 2
    I'm not sure distributed computing is very relevant here as you are then already talking about IO and the possibility of network failure etc. – jk. Jan 31 at 16:44
up vote 3 down vote accepted

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.

  • 2
    I agree, there's definitely a trade-off between precision and memory, as well as the running time. Seems like the RT issue also joins in. I guess one can't ignore this, but has to be pragmatic: run tests at different precision levels, etc. Hopefully, the precision issue is orthogonal to other issues addressed by FP, like shared mutable state. – Tupolev._ Feb 1 at 16:02
  • I wonder why one needs to choose a different language to get rational numbers. They are widely available, including Haskell, and work without loss of precision within its range. But surely they cannot easily represent the same range, are slower, and you have hard time doing e.g. trigonometry. – 9000 Feb 15 at 21:38
  • @9000 I re-read this answer and there's nothing in it that suggests using a different language. That's in the question. – JimmyJames Feb 15 at 21:53
  • @JimmyJames: Sure; the suggestion is in the question quoted («choosing a language with better reproducibility»); I made the comment for the benefit of the question author, not to augment your answer. – 9000 Feb 15 at 21:58

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.

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.