Compute if a function is pure

Question

As per Wikipedia:

In computer programming, a function may be described as pure if both these statements about the function hold: The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

I am wondering if it is possible to write a function that compute if a function is pure or not. Example code in Javascript:

function sum(a,b) {
 return a+b;
}
function say(x){
 console.log(x);
}
isPure(sum) // True
isPure(say) // False

• user40980: This might be candidate for the Computer Science Stack Exchange. This tends more to the realm of theory ("possible") rather than practical and design... It is a bit beyond my ken.
• user40980: ... and even though it is "possible" and "theory" there is very likely a real answer to it (a good fit for Q&A) that may even involve a proof... which again takes it back to the computer science world.
• Giorgio: I think you can determine if a function is pure by looking at the type of functions that are invoked in its definition. I mean, you can define purity by induction on the structure of functions.
• SK-logic: It is not possible to do without platform-specific reflection hacks. If a function is a black box, no experiment can prove it is pure. E.g., if there is something like if (rand(1000000)<2) return WRONG_ANSWER, probing the function many times for a consistent behaviour won't help. But, if you have an access to the function definition, proof is trivial.
• user40980: @user470365 From the definition of a pure function - "Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices." -- Anything that writes to IO is impure by definition. In the example, say calls console.log which is impure thus say is impure too.

Answer 1

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.

• mattnz: +1 - Given the answer by Peteris got so many upvotes.....
• Greg Hewgill: I suppose you would need to add "It only calls pure functions" to the list of criteria.
• Jon Purdy: @GregHewgill: Good catch. I updated the answer accordingly. It’s fine to call mutating functions on locals, as long as they’re not otherwise side-effectful. "Pure" is too overloaded a term...
• Oleg V. Volkov: You also need to check if toString is pure for any object you use as string.
• Jules: I don't think this answer is correct, because there are only a subset of circumstances where you can actually make these determinations. Consider: is this function pure? function a (o) { return o.method(); } -- we can't actually answer this, because it depends on what parameter o is passed. Also, we can't account for what happens if a previously-certified-pure function is changed to a non-pure implementation, which is always a potential issue with javascript.

Answer 2

No. You can easily check if a function only does "pure-safe" operations, as described in Jon Purdy's answer, but that is IMO not enough to answer the question.

Consider this function:

function possiblyPure(x) {
 if (someCheck(x)) {
 return x+1; // pure code path
 }
 else {
 console.log("I'm so unpure..."); // unpure code path
 }
}

Obviously, if someCheck is unpure, so is possiblyPure. But, if someCheck is pure and returns true for every possible value of x, possiblyPure is pure, since the unpure code path is unreachable!

And here comes the hard part: determining whether or not someCheck returns true for every possible input. Trying to answering that question immedately leads you into the realm of the halting problem and similar undecidable problems.

EDIT: Proof that it is impossible

There is some uncertainity wether or not a pure function must terminate on every possible input. But in both cases, the halting problem can be used to show that the pureness check is impossible.

Case A) If a pure function is required to terminate on every possible input, you have to solve the halting problem to determine whether or not the function is pure. Since this is known to be impossible, by this definition, pureness cannot be computed.

Case B) If a pure function is allowed to not terminate on some inputs, we can construct something like that: Let's assume that isPure(f) computes if f is a string defining a pure function.

function halts(f) {
 var fescaped = f.replace(/\"/g, '\\"');
 var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
 return isPure(upf);
}

Now isPure has to determine whether or not f halts on it's own source as input. If it halts, upf is unpure; if it doesn't terminate, upf is pure iff f is pure.

If isPure worked as expected (returns correct results and terminates on every input), we would have solved the halting problem(*)! Since this is known to be impossible, isPure cannot exist.

(*) for pure JavaScript functions, which is enough to solve it for the turing machine, too.

• SK-logic: True. It is always possible to do a conservative analysis - to check if a function is definitely pure, but not possible to check if it is definitely not pure.
• user281377: Many cases are trivially decidable - those pure functions described by Jon Purdy or unpure functions which unconditionally do something dirty; but in general, one can construct cases which are undecidable.
• JacquesB: If a function sometimes have side-effects it wouldn't be considered pure by any reasonable definition. So I think this argument is a red herring. The question is if a function can be proven to never have side effects.
• user281377: @JacquesB That's why I wrote "if someCheck is pure and returns true for every possible value of x" - while this might not seem like a useful scenario at all, it might just happen if someCheck is actually redundant because a similar or stricter check has happened before the call to someCheck. This makes the function acutally pure by definition even though it contains unpure code in an unreachable branch. (I admit that this is not something many people would be interested in, since unreachable code is not desirable anyway)
• JacquesB: @user281377: Fair enough, but that seems more like a "gotcha" than a useful answer. If you can't prove that a branch is never executed, and that branch has side effects then by all reasonable definitions the function is not pure.

Answer 3

This stackoverflow question has an answer by yfeldblum that is relevant here. (And has a downvote for some reason I can't fathom. Would it be bad etiquette to upvote something that is 3 years old?) He gives a proof that whether a function is pure is reducible to the halting problem in a comment.

I think from a practical point of view it wouldn't be too hard for some languages if you let the function return yes, no, or maybe. I was watching a video about Clojure a couple of days ago, and the speaker had done a count of instances of impurity in a codebase by searching for about 4 different strings (like "ref"). Because of Clojure's emphasis on purity and segregation of impure things, it was trivial, but it wasn't quite exactly what you're looking for.

So, theoretically impossible, practically possible if you tweak the question a bit, and I think how hard it would be would depend greatly on the language. Simpler/cleaner languages with a focus on immutability and good reflection would be easier.

• SK-logic: I reckon, it had been downvoted because it's wrong. bottom is a valid, first class value, it does not deserve being discriminated this way.

Answer 4

Great question.

The best you can do in practice, assuming no ability to listen to i/o actions to call the function as many times as feasible. Then see if the return value is consistent.

But you cannot do this in general. Arguably, non-halting programs are non-pure, and we cannot decide the halting problem.

• mattnz: -1: It would be beyond trivial to write a function that passes this test and is anything but pure.
• Greg Hewgill: By this logic, any void function would be "pure", which is clearly false.
• mattnz: @Greg:By extension, void foo(void) would also have to be pure.

Answer 5

Not possible in the general case. See halting problem. Briefly, it is impossible to write a program that, given an arbitrary function and input, determines whether the program will halt or run forever. If it runs forever, it's not a pure function fitting the definition you gave.

• whatsisname: Running forever doesn't seem to discount a function from fitting his criteria for a pure function.
• mattnz: +1 : There is an implicit required that the functiuon terminates by " The function always evaluates the same result value give...."
• SK-logic: Consistently running forever without modifying any state is perfectly "pure". But, of course, it is a terminology issue here.
• SK-logic: @mattnz, such a function will always evaluate to the bottom value.
• rwong: I can see where the terminology issue comes in. In some interpretations, a "pure" function is one that is deterministic as well as never communicating any state or value with the outside during its execution. In other interpretations, halting is added to the requirements. With the first interpretation, it is easy to determine if a function is pure: a machine that executes a particular language ought to be able to determine if a program in that language makes any communication with the outside.