Purity Analysis is equivalent to solving the Halting Problem, and thus cannot be done statically in the general case. There will always be infinitely many functions for which your purity checker can neither prove that they are pure nor that they are impure.

Which means any possible purity checker can only do one of two things:

• Play it safe, and reject any function for which it cannot positively prove that it is pure. This means there are infinitely many pure functions that the purity checker will not allow you to write.
• Accept any function for which it cannot positively prove that it is impure. This means there are infinitely many impure functions that the purity checker will allow you to write.

The proper way to do this, really, is to design the language, the type system, and the libraries from the ground up to be 100% pure. Then, and only then, will you have a chance to automatically check for purity in a sensible way. It is of course still impossible to check in the general case, but designing the language, the type system, and the libraries to be easily checkable helps making the checker more useful.

The trivial case would be to design a language which doesn't allow you to write impure functions in the first place, but such a language would not be terribly useful. As one of the designers of Haskell has said: all that a pure program can do is make the CPU warm. To which someone from the audience responded: making the CPU warm is actually a side-effect, too!