Yes, it is possible, depending on the language.
In JavaScript, you can tell if a function is pure by the following criteria:
It only reads parameters and locals;
It only writes locals;
On non-locals, it calls only pure functions;
All functions it calls implicitly are pure, e.g., toString; and
It only writes properties of locals if they do not alias non-locals.
Aliasing is not possible to determine in JavaScript in the general case, because you can always look up properties of an object dynamically (object["property"]). Provided you never do that, and you have the source of the whole program, then I think the problem is tractable. You would also need information about which native functions have side-effects, such as console.log or most anything involving the DOM.
The term “pure” could also use some clarification. Even in a strongly, statically typed, purely functional programming language, where all functions are referentially transparent, a function can still fail to terminate. So when we talk about id :: a -> a, what we’re really saying is not:
Given some value of type a, the function id produces a value of type a.
But rather:
Given some value of type a, the function id does not produce a value which is not of type a.
Because a valid implementation of id is error "Not implemented!". As Peteris points out, this nontotality could be seen as a kind of impurity. Koka is a functional programming language—with syntax modelled on JavaScript—which can infer possible effects such as divergence (nontermination), referential transparency, throwing of exceptions, and I/O actions.
However, from the viewpoint of CalculatorClient, who talks to it only through the IOperationalInterface, it appears to be immutable and the Sum operation appears to be pure in the sense that it could not observe any side effects through that interface.
Whatever you can observe through the interface is irrelevant to the concept of purity. If Sum logged results to a file, it would still be impure even though you wouldn't be able to observe any changes through the interface.
Purity is a very strong condition. If you say that something is pure, I'll take you at your word and assume nothing bad will happen if I run it from multiple threads, cache the results and only call it once for any given set of inputs, or that I can call it 1,000,000 times without exhausting the OS's file handles. Those assumptions can backfire when using CalculatorImpl.
There's nothing wrong with partitioning the interfaces the way you have, but you should be precise. The specification you want for IOperationalInterface is probably closer to: "The return value of these methods must depend only on their arguments, but their execution may have side effects." You can be more specific about the side effects and say that the methods must not perform any kind of I/O. But I wouldn't say that it's pure, because you're very clearly not using it that way.
Best Answer
A pure function could still be an implementation detail. Although the function may cause no harm (from the point of view of not breaking important invariants/contracts), by exposing it both the author and the users of that class/module/package lose. The author loses because now he can't remove it even if the implementation changes and the function is no longer useful to him. The users lose because they have to sift through and ignore extra functions that aren't relevant to using the API in order to understand it.