Is this JavaScript function, taking a mutable reference argument, a pure function?

I have the same question as this one, but in the context of JavaScript.

From Wikipedia:

[a pure function's] return value is the same for the same arguments

It's further claimed there that a pure function is not allowed to have a variation in return value with "mutable reference arguments". In JavaScript, every normal object is passed as a "mutable reference argument". Consider the following example:

const f = (arr) => arr.length

const x = []
console.log( f(x) ) // 0
x.push(1);
console.log( f(x) ) // 1

Is the above proof that f is impure? Or would you argue that we're not calling f with the "same" argument in the two cases?

I can see how it would make sense to call f impure in a language/environment where other threads could potentially mess with the mutable reference argument while f is executing. But since f is not async, there is no way for this to happen. x is going to stay the same from the moment f is called to when it's done executing. (If I'm understanding correctly, this interpretation seems to be supported by the definition of "same" put forth in § 4.1 of Verifiable Functional Purity in Java.)

Or am I missing something? Is there an example in JavaScript where a function containing no asynchronous code loses the property of referential transparency simply because it's taking a mutable reference, but it would be pure if we used e.g. an Immutable.js data structure instead?

When taking the Wikipedia definition to the letter, a function that takes as argument a reference to a mutable data structure (such as a native Array) is not pure:

Its return value is the same for the same arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams from I/O devices).

Equivalence

Although this clearly says "no variation with mutable reference arguments", we could maybe say this is open to interpretation and depends on the meaning of "same" and "variation". There are different definitions possible, and so we enter the area of opinion. Quoted from the paper your referred to:

There is not a single obviously right answer to these questions. Determinism is thus a parameterized property: given a definition of what it means for arguments to be equivalent, a method is deterministic if all calls with equivalent arguments return results that are indistinguishable from within the language

The functional purity proposed in the same paper, uses the following definition of equivalence:

Two sets of object references are considered equivalent if they result in identical object graphs

So with that definition, the following two arrays are considered equivalent:

let a = [1];
let b = [1];

But this concept can not really be applied to JavaScript without adding more restrictions. Nor to Java, which is the reason why the authors of the paper refer to a trimmed-down language, called Joe-E:

objects have identity: conceptually, they have an “address”, and we can compare whether two object references point to the same “address” using the == operator. This notion of object identity can expose nondeterminism.

Illustrated in JavaScript:

const compare = (array1, array2) => array1 === array2;

let arr = [1];
let a = compare(arr, arr);
let b = compare(arr, [1]);
console.log(a === b); // false

As the two calls return a different result, even though the arguments had the same shape and content, we should conclude (with this definition of equivalence) that the above function compare is not pure. While in Java you can influence the behaviour of the == operator (Joe-E forbids calling Object.hashCode), and so avoid this from happening, this is not generally possible in JavaScript when comparing objects.

Unintended side effects

Another issue is that JavaScript is not strongly typed, and so a function cannot be certain that the arguments it receives are what they are intended to be. For instance, the following function looks pure:

const add = (a, b) => a + b;

But it can be called in way to give side effects:

const add = (a, b) => a + b;

let i = 0;
let obj = { valueOf() { return i++ } };
let a = add(1, obj);
let b = add(1, obj);
console.log(a === b); // false

The same problem exists with the function in your question:

const f = (arr) => arr.length;

const x = { get length() { return Math.random() } };
let a = f(x);
let b = f(x);
console.log(a === b) // false

In both cases the function unintentionally called an impure function and returned a result that depended on it. While in the first example it is easy to still make the function pure with a typeof check, this is less trivial for your function. We can think of instanceof or Array.isArray, or even some smart deepCompare function, but still, callers can set a strange object's prototype, set its constructor property, replace primitive properties with getters, wrap the object in a proxy, ...etc, etc, and so fool even the smartest equality checkers.

Pragmatism

As in JavaScript there are just too many "loose ends", one has to be pragmatic in order to have a useful definition of "pure", as otherwise almost nothing can be labelled pure.

For example, in practice many will call a function like Array#slice pure, even though it suffers from the problems mentioned above (including related to the special argument this).

Conclusion

In JavaScript, when calling a function pure, you will often have to agree on a contract on how the function should be called. The arguments should be of a certain type, and not have (hidden) methods that could be called but that are impure.

One may argue that this goes against the idea behind "pure", which should only be determined by the function definition itself, not the way it eventually might get called.