Programatically determine that some functions are pure

Question

I saw this question that shows it is impossible to programatically determine if a javascript function is pure, but is it sometimes possible to affirm that a function is pure - so something like...

function sq_a(x){ return x * x; }; // no side effects, all variables local
function sq_b(x){ return pow(x, 2); }; // if `pow` is pure, this function is pure
function sq_c(x){ return mathlib.pow(x, 2); }; // not pure, because mathlib.pow could be changed
function definitelyPure(fn){
 if(/* criteria to check if we can know for sure fn is pure */){
 return true;
 } else {
 return false;
 }
}
function isPure(fn){
 if(/* fn is pure */){
 return 0;
 } else if(/* fn might be pure */) {
 return -1;
 } else { // fn is not pure
 return 1;
 }
}
definitelyPure(sq_a); // true
definitelyPure(sq_b); // false
definitelyPure(sq_c); // false
isPure(sq_a); // 0
isPure(sq_b); // -1
isPure(sq_c); // 1

Clarification:

I know it is not possible to determine if any javascript function is pure as answered in linked to question, but I am asking if it is possible to programatically affirm purity of some functions - as in I expect that it is possible for example sq_a using some code analysis, but I understand it is not possible for sq_b.

I am interested to know if there are any tools out there to do this already, and what criteria determine if it is possible to programatically declare a function as either pure, unknown, or impure.

• Wildcard: There doesn't seem to be a question here.
• Billy Moon: sorry, question: is it sometimes possible to programatically affirm that a javascript function is pure?
• Wildcard: You just linked to a page with many answers specifying that it is not possible to programmatically determine that a JS function is pure.
• Robert Harvey: Exact duplicate of Compute if a function is pure
• Billy Moon: Guys, this is not a duplicate, it's related to that question, but is a follow on question in it's own right.

Answer 1

It is possible, in general, to analyse the parse tree of a function and check a set of constraints that ensure we know if the function is definitely pure:

• If the function only calls other functions that are pure
• And doesn't reference or modify any global variables

Then it is pure.

There is, however, a problem with doing this in Javascript (and many other dynamic languages), which is that they provide a mutable environment. You state that your function sq_b is pure, but you can't actually prove that unless you can determine the behaviour of all other code that may run before it, because that code may do something like this:

window.nextPowResult = 1;
window.pow = function (a,b) { return nextPowResult ++; }

This changes the behaviour of your function (and any other function that uses pow), and makes it non-pure. Unfortunately, determining whether or not something like this could happen is an undecidable question, so in Javascript specifically we cannot ever be certain that any function is pure, unless we have control over all code that executes in the same context.

• Billy Moon: Thanks for your answer - just to clarify, I do not state sq_b is pure, I state that "if pow is pure, this function is pure" and "fn might be pure". a, b and c are intended to be examples of a pure, unknown purity and impure function.
• Billy Moon: how about if in the same enclosure, pow is defined as var pow = ... so it is not attached to the window and is itself analysable as a pure function (as sq_a should be possible for) for example... perhaps there are times when it could also be programatically determined to be definitely pure..?
• Billy Moon: well, I am sure browser vendors will replace javascript one day so that our kids will not have to suffer the slings and arrows of dynamic typing in their programming forays, but that is a problem beyond my influence :(
• Jules: It's not necessary for browser vendors to do that, as Javascript is a perfectly adequate target for compiling code in other languages to... see github.com/jashkenas/coffeescript/wiki/…
• Ixrec: @BillyMoon For the record, this nonsense has nothing to do with dynamic typing. You can break C just as easily with well-placed #defines and pointer arithmetic and whatnot. The real problem is that Javascript (as well as C and C++) does not yet have a standardized, widely-implemented modules system that genuinely isolates one module of code from all other modules.

Answer 2

var sneaky3 = { 
 valueOf: () => { console.log('look, a side effect'); return 3; } 
} 
>> sq_a(sneaky3) 
look, a side effect
9

As shown above, side effects can happen even in simple arithmetic operations.

Basically, the only operations that can be proven pure are operations on literals using built-in operators, like 2 + 2. This is so limited as to be useless.