Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
share|improve this question
6  
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. –  MichaelT 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. –  MichaelT 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
6  
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
    
Given the quantity of low quality answers and up/down votes, I think this is a definite candidate for Computer Science Stack Exchange, as it's clearly far too academic Programmers . –  mattnz Nov 22 '12 at 8:59
show 2 more comments

5 Answers

up vote 12 down vote accepted

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.

share|improve this answer
    
+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
1  
@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
    
@OlegV.Volkov: Thanks, edited to add. –  Jon Purdy Nov 22 '12 at 19:33
add comment

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.

share|improve this answer
3  
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
-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
2  
By this logic, any void function would be "pure", which is clearly false. –  Greg Hewgill Nov 22 '12 at 2:13
1  
@Greg:By extension, void foo(void) would also have to be pure. –  mattnz Nov 22 '12 at 2:17
add comment

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.

share|improve this answer
4  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.