Order of execution of functions in functional programming

Question

Since past 6 months, I started to learn the concepts of functional programming. While reading many sources, one of the things I found was that in functional programming, order of execution is undefined! I don't clearly understand this.

From this other Stack Overflow answer: https://stackoverflow.com/a/23290/1276021, "A functional language" (ideally) allows you to write a "mathematical function".

But, as in mathematical functions, f(g(x)) !== g(f(x)) - meaning, order of execution matter.

It seems like I was wrong in understanding the concept that "order of execution is undefined". Where am I wrong?

Answer 1

f(g(x)) !== g(f(x)) - meaning, order of execution matter.

No, those are different expressions/programs, not only different order of execution.

It seems like I was wrong in understanding the concept that "order of execution is undefined"

The correct, more verbose statement would be "the order of evaluation of the parts of an expression is irrelevant" (and will always lead to the same result). This means that such a functional language has no side effects and referential transparency - two very important properties for proofs that "mathematical" functions have as well.

If we define two functions

f(x) = x*3
g(y) = y+1

and then try to evaluate the expression f(g(1)), it doesn't matter whether we first do

  f(g(1))
= f(1+1)
= f(2)
= 2*3
= 6

or

  f(g(1))
= g(1)*3
= (1+1)*3
= 2*3
= 6

We always arrive at 6, regardless of which of the functions we apply first.

Answer 2

Yes the order of execution is left up to the compiler and to you the programmer it is not important.

But what the inputs to each function are is important:

• f(g(x)) means the result of calling f with the result of g(x)
• g(f(x)) means result of calling g with the result of f(x)

Consider this example:

a(b(x)) + b(x) + c(b(x))

The compiler will decide to figure out the result of b(x) first and then use that result in the a and c function calls. But a very poorly optimized compiler might decide to figure out b(x) then call a with the result then figure out b(x) again and then figure out c(b(x)). Ultimately they will both come up with the same answer, so as far as you the programmer is concerned the order of execution is irrelevant. Most of the time a well written compiler will figure out the best order of execution far far better than you could by hand using an imperative language, particularly when things get complex, and so it's best not to think about the order of execution, rather leave that as an implementation detail for the compiler to solve.

Answer 3

In functional programming, as in mathematics, functions are valid values as parameters.

Take these 2 functions

f(x) = x ^ 2
g(x) = 2x - 4

Take the following composition f(g(x)). If we evaluate f first :

F = f(g(x)) = (g(x)) ^ 2

Our new F is still a valid function in mathematics, as it would be in functional programming.

Then, if we evaluate g(x) to g(3) we get:

g(3) = 2 * 3 - 4 = 2

We can then evaluate F

F = (2) ^ 2 = 4

The order of evaluation doesn't matter.