algorithm - Algorithmically identifying pure functions in javascript -

is possible determine whether or not javascript function "pure", using javascript?

a function said pure when behaves in predictable way, in sense each x, function return same associated y value (i.e single-valued map).

for example, pure function:

function pure(x) {   return x * x; } 

and impure:

var x = 0; function impure(y) {   x = x + y;   return x++; } 

while it's easy tell here impure(0) !== impure(0), isn't apparent function such as:

function weird(x) {   if (x === "specificthing") {     return false;   } else {     return true;   } } 

or

var count = 0; function surprise(x) {   count++;   if (count === 10e10 && x === 0) {     return true;   } else {     return false;   } } 

another way of asking is, possible determine whether or not javascript function "impure", using javascript?

theoretically may possible or impossible, practically steps can 1 take start determine this, maybe given set of constraints or assumptions?

another definition of purity includes caveat non-local variables may not changed, i'd consider separate problem. in case considering functions map consistent inputs consistent outputs.

javascript turing complete, it's able parse , analyse javascript other programming language. so, question really: "can javascript functions automatically tested "purity", @ all?"

short answer

only sometimes.

long answer

for functions, ast straight forward , symbols contained, definitely. function(x) { return x * x; } provably pure (for primitive input) because variables used in function body variables passed in function arguments. function not rely on additional api calls, pure arithmetics. can show it's pure.

things change when allow arbitrary content, because javascript has no explicit types, , instead will happily type-coerce complex primitive data type (or primitive primitive data type) when needs perform operation can't have operation applied. calling our above function object, instead of number, performs further function calls underwater, , functions not guaranteed pure @ (see andreas's answer on this, too)

the vast majority of js functions nothing our simple function. functions, need prove not they're pure, functions call internally pure, too. we're running halting problem. let's take ridiculously simple example:

function(x) {   if (typeof window !== "undefined") {     return x * x;   }   return x * x * x; } 

is pure? well, if run in browser, in browser it's pure, since window defined. in node.js, might pure, might not be: can't prove is, nor can prove not, because cannot prove mysterious window variable exists when function runs. while node.js has no global window variable, can trivially introduce 1 whenever like, , function's behaviour change. we're faced proving whether or not entirety of our code ever introduce window variable (and may creatively done, global["win" + _abc] = true _abc string "dow"). lost cause.

the rabbit hole runs deep, , reading halting problem make appreciate how many difference faces halting problem has.