Functional Programming – Order of Evaluation in Pure Functions

functional programmingprogramming practicesprogramming-languages

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)

Best Answer

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.

Related Solutions

Functional Programming – How to Manage Without Assignment Statements

If there is no assignment statement,how can this be done?How to change the balance variable?

You can't change variables without some sort of assignment operator.

I ask so because I know there are some so-called pure functional languages out there and according to the Turing complete theory,this must can be done too.

Not quite. If a language is Turing complete that means that it can calculate anything that the any other Turing complete language can calculate. It doesn't mean that it has to have every feature other languages have.

It's not a contradiction that a Turing complete programming language has no way of changing the value of a variable, as long as for every program that has mutable variables, you can write an equivalent program that does not have mutable variables (where "equivalent" means that it calculates the same thing). And in fact every program can be written that way.

Regarding your example: In a purely functional language you simply wouldn't be able to write a function that returns a different account balance each time it's called. But you'd still be able to rewrite every program, that uses such a function, in a different way.

Since you asked for an example, let's consider an imperative program that uses your make-withdraw function (in pseudo-code). This program allows the user to withdraw from an account, deposit to it or query the amount of money in the account:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Here's a way to write the same program without using mutable-variables (I won't bother with referentially transparent IO because the question wasn't about that):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

The same function could also be written without using recursion by using a fold over the user input (which would be more idiomatic than explicit recursion), but I don't know whether you're familiar with folds yet, so I wrote it in a way that doesn't use anything you don't know yet.

Functional Programming – Why Use Space for Function Application?

which seems to be the more mathematical way

functional languages are inspired by lambda calculus. In this field, parentheses are not used for function application.

I also think that the latter style is much more clear and readable than without the parens.

Readability is in the eye of the beholder. You are not used to reading it. It is a bit like mathematical operators. If you understand the associativity, you only need a few parens to clarify the structure of your expression. Often you don't need them.

Currying is also a good reason to use this convention. In haskell, you can define the following:

add :: Int -> Int -> Int
add x y = x + y

x = add 5 6 -- x == 11
f = add 5
y = f 6 -- y == 11
z = ((add 5) 6) -- explicit parentheses; z == 11

With parens, you could use two convention: f(5, 6) (not curried) or f(5)(6) (curried). The haskell syntax helps to get used to the currying concept. You can still use a non-curried version, but it is more painful to use it with combinators

add' :: (Int, Int) -> Int
add' (x, y) = x + y
u = add'(5, 6) -- just like other languages
l = [1, 2, 3]
l1 = map (add 5) l -- [6, 7, 8]
l2 = map (\x -> add'(5, x)) l -- like other languages

Notice how the second version forces you to register x as a variable, and that the subexpression is a function which takes an integer and adds 5 to it? The curried version is much lighter, but also considered by many as more readable.

Haskell programs makes extensive use of partial application and combinators as a mean of defining and composing abstractions, so this is not a toy example. A good function interface will be one where the order of parameters provides a friendly curried usage.

Another point: a function without parameters should be called with f(). In haskell, since you only manipulate immutable lazy evaluated values, you just write f, and consider it as a value which will need to perform some computations when needed. Since its evaluation won't have any side effect, it makes no sense to have a different notation for the parameterless function and its returned value.

There are also other conventions for function application:

Lisp: (f x) -- prefix with external parentheses
Forth: x f -- postfix

Best Answer

Related Solutions

Functional Programming – How to Manage Without Assignment Statements

Functional Programming – Why Use Space for Function Application?

Related Topic