In functional programming, what it means “Order of evaluation does not matter” when function is pure?

In context of pure functions in FP, apart from several benefits mentioned like easy to reason about, testability it also says "order of evaluation does not matter" since output remains same for given input. Probably I being from OO background finding it difficult to understand what it actually means. It would be great if someone can clearly explain this with some example (preferably comparing with impure function where order matters)

To add some more examples, in imperative (OOP) programming, mutability is required to make ordering mattering, while non-local variables — in the presence of mutability — add to the confusion.

First regarding mutability: let's say we have someStack, which:

someStack.Push ( 400 );
someStack.Push ( 500 );
// stack now has (at least) 400, 500 <-- top of stack
var answer = someStack.Pop () / someStack.Pop ();

The order of evaluation of the operands of / (numerator vs. denominator) is significant here because the first to Pop() will get 500 and the second 400.  Thus, one order will compute 400/500 and the other order will compute 500/400.

By the way, the order of evaluation of the operands is undefined in a language like, C so that the compiler can choose the most efficient way.  It is thus a programmer burden to write code that doesn't care about the ordering.  In C we would use sequence points to solidify the ordering:

float numerator = someStack.Pop ();      // happens first because of ";"
float denominator = someStack.Pop ();    // happens second
float answer = numerator / denominator;  // order of operand evaluation doesn't matter
// since they're just simple variables.

Next, non-local variables, in combination with mutability, allow sharing of data (like that stack) without that sharing necessarily being obvious/visible from reading a line of source code.  Thus, in @Christope's example,

f(g(x), h(y))

As we don't know by reading this line of code, what g and h do or might do; each could do a someStack.Pop (), modifying this example stack, if the stack referred to by someStack were accessible to both in some non-local, shared or global variable.  Order of evaluation would then determine whether g sees 500 and h 400, or vice versa.

Some programming languages (other than C) will define an operand evaluation ordering (e.g. left to right) to help reduce confusion.

In pure FP, we do not have mutability — so, all variables, once defined, remain constant, even if accessible via non-local variables.  If mutation is precluded, then all usages of the same variables will see the same values.  Thus, the above examples cannot be coded.  Modification of the stack (push or pop) would yield a new stack data structure, leaving the original in tact, were anyone to look at it.

Note that this is quite different from const declarations in languages like C++ and JavaScript or final in Java or readonly in C#: in these languages, const/final/readonly only means the variable itself cannot be updated, but a data structure the variable points to is still open for mutation!  In pure FP, not only is a variable immutable, but so is the entire data structure it refers to.

Also note that order of evaluation of operands is an independent concept from operator precedence.

Operator precedence is a syntactic concept that is (generally) not ambiguous by definition of the grammar of a language: a+b*c means bind b and c to * and then bind a and the result of the * to +.

Whereas order of evaluation of operands happens after precedence-defined binding is established (in a+b*c: individually the operands a, b, and c can still be evaluated in any order in the C language).

The cost of strict left-to-right evaluation of operands is occasional efficiency, in needing more temporary variables (compiler introduced intermediate) and more such temps that are live across calls.  For example, in a+f(), if the compiler thinks that a could possibly be modified by invoking f() then here it would have to copy a into a temp before calling f() in a left-to-right language, whereas C would invoke f() first, then use a directly, taking advantage of its unspecified operand evaluation ordering.

• +1 for demonstrating that you can achieve the same purity in a non-FP language, but you have to work for it. – RubberDuck Sep 9 '18 at 1:31
• +1 very well explained. thx !!! – Rahul Agarwal Sep 9 '18 at 6:07

This means that the absence of side effects ensures that functions can be evaluated in a different order and give the same result.

Example:

• In a functional f(g(x), h(y)) will give the same result, whether g(x) is evaluated first or h(y) is evaluated first, because their respective result depends only on the input parameters.
• With non functional language, this is not guaranteed, because each function could have side effects that affect the result of the other functions.

I will try to give a very simple example:

def f():
print("Hello")
return 2

def g():
print("World")
return 3

print(f() + g())

What will the result be?

It will be either

Hello
World
5

or

World
Hello
5

depending on the order of evaluation. In some languages, it will be specified that the order of evaluation is left-to-right, for example (giving the first result), but in other languages, there is no defined order of evaluation except the one implicitly given by data dependencies (i.e. arguments are evaluated before the function, but which argument gets evaluated first is left to the compiler). In the latter case, we cannot know which of the two results we are going to get.

However, as you may notice, both in my example and in the other answers, the only thing that allows us to observe the order of operations are side-effects. I/O in my case, mutation in the other answers. In a purely functional language, there are no side-effects. Ergo, the order of operations cannot be observed.

It also cannot be observed how often evaluation occurs! An implementation could memoize the result of an evaluation and re-use it, for example:

f() + f()

may evaluate f once or twice (or even a hundred times), and you wouldn't be able to tell the difference.