Algorithmically identifying pure functions in javascript

Question

Is it possible to determine whether or not a javascript function is "pure", using javascript?

A function is said to be pure when it behaves in a predictable way, in the sense that for each x, the function will always return the same associated y value (i.e a single-valued map).

For example, a 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 to tell here that impure(0) !== impure(0), it isn't as apparent with a 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 this is, is it possible to determine whether or not a javascript function is "impure", using javascript?

Theoretically it may be possible or impossible, but practically what steps can one take to start to determine this, maybe given a set of constraints or assumptions?

Another definition of purity includes the caveat that non-local variables may not be changed, but I'd like to consider that a separate problem. In this case we are considering functions that map consistent inputs to consistent outputs.

Answer 1

JavaScript is Turing complete, so it's just as able to parse and analyse JavaScript as any other programming language. So, the question is really: "can JavaScript functions be automatically tested for "purity", at all?"

Short answer

Only sometimes.

Long answer

For some functions, for which the AST is straight forward and all the symbols are contained, definitely. Something like function(X) { return X * X; } is provably pure (for primitive input) because the only variables used in the function body are variables that are passed in as function arguments. This function does not rely on any additional API calls, but pure arithmetics. We can most definitely show it's pure.

Things change when we allow arbitrary content, because JavaScript has no explicit types, and instead will happily type-coerce from complex to primitive data type (or even from primitive to primitive data type) when it needs to perform an operation that can't have that operation applied. Calling our above function with an object, instead of a number, performs further function calls underwater, and those functions are not guaranteed pure at all (see Andreas's answer on this, too)

The vast majority of JS functions are nothing like our simple function. For most functions, we need to prove not only that they're pure, but that all the functions they call internally are pure, too. Now we're running into the halting problem. Let's take a ridiculously simple example:

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

Is this pure? Well, if we run this in the browser, then in the browser it's pure, since window is always defined. But in something like Node.js, it might be pure, but it might not be: we can't prove it is, nor can we prove it is not, because we cannot prove that this mysterious window variable exists when the function runs. While Node.js has no global window variable, we can trivially introduce one whenever we like, and the function's behaviour will change. Now we're suddenly faced with proving whether or not the entirety of our code will ever introduce a window variable (and that may be very creatively done, like global["win" + _abc] = true where _abc is the string "dow"). This is a lost cause.

The rabbit hole runs deep, and reading about the halting problem will make you appreciate how many difference faces the halting problem has.