Purity analysis is indeed trivially decidable, if you limit yourself to "probably always pure", not "pure when executed on a Tuesday". It boils down to "is this function calling only pure functions and not using any of the impure operators?". The trouble comes with dynamic languages where you usually don't know shit about a function's arguments, though. In that case you need a control flow Analysis of the whole program.