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

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.

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.

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.

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.

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.