# Compute if a function is pure

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
``````
• 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 Nov 21 '12 at 23:02
• ... 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. – user40980 Nov 21 '12 at 23:10
• 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. – Giorgio Nov 21 '12 at 23:16
• 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. – SK-logic Nov 21 '12 at 23:17
• @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. – user40980 Nov 26 '12 at 15:37

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.

• +1 - Given the answer by Peteris got so many upvotes..... – mattnz Nov 22 '12 at 2:15
• I suppose you would need to add "It only calls pure functions" to the list of criteria. – Greg Hewgill Nov 22 '12 at 2:18
• @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… – Jon Purdy Nov 22 '12 at 4:00
• You also need to check if `toString` is pure for any object you use as string. – Oleg V. Volkov Nov 22 '12 at 12:29
• 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. – Jules Jun 9 '16 at 23:23

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.

• 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. – SK-logic Nov 22 '12 at 10:25
• 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. – user281377 Nov 22 '12 at 10:27

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.

• 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. – SK-logic Nov 22 '12 at 9:45

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.

• -1: It would be beyond trivial to write a function that passes this test and is anything but pure. – mattnz Nov 22 '12 at 2:10
• By this logic, any `void` function would be "pure", which is clearly false. – Greg Hewgill Nov 22 '12 at 2:13
• @Greg:By extension, void foo(void) would also have to be pure. – mattnz Nov 22 '12 at 2:17

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.

• Running forever doesn't seem to discount a function from fitting his criteria for a pure function. – whatsisname Nov 22 '12 at 4:03
• +1 : There is an implicit required that the functiuon terminates by " The function always evaluates the same result value give...." – mattnz Nov 22 '12 at 8:58
• Consistently running forever without modifying any state is perfectly "pure". But, of course, it is a terminology issue here. – SK-logic Nov 22 '12 at 9:42
• @mattnz, such a function will always evaluate to the `bottom` value. – SK-logic Nov 22 '12 at 9:43
• 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. – rwong Nov 23 '12 at 22:52