Does functional programming allow mutability of locally scoped objects?

Question

I learnt that mutability of an object is defined with respect to its state but not with its identity.

Below program changes state of a locally scoped object referred by name count within function hailstone().

def hailstone(n):
    count = 1
    """Print the terms of the 'hailstone sequence' from n to 1."""
    assert n > 0
    print(n)
    if n > 1:
        if n % 2 == 0:
            count += hailstone(n / 2)
        else:
            count += hailstone((n * 3) + 1)
    return count

if (__name__ == '__main__'):
    result = hailstone(10)
    print(result)

After reading the below paragraph of this article, I see that the above code looks fine as regards changing the state of the locally scoped object that name count refers to (i.e. count += hailstone(n / 2)):

Ignore all that. Functional code is characterised by one thing: the absence of side effects. It doesn't rely on data outside the current function, and it doesn't change data that exists outside the current function. Every other “functional” thing can be derived from this property. Use it as a guide rope as you learn.

So, how do I understand the meaning of this statement from this answer:

In functional programming, it is not proper to ever change the value of a variable.

Does functional programming allow changing the state of the locally scoped object referred by name count in my above program?

Answer 1

There is no clearcut definition of functional programming. However, it typically is meant to imply the absence, or at least the minimisation, of side effects -- sometimes people speak of pure functional programming to emphasise their complete absence. But what is a side effect?

A common definition is that a side effect is anything that breaks referential transparency. Referential transparency in turn can be defined in various ways, but perhaps the most enlightening definition is that order of evaluation should be irrelevant. That is, a program is referentially transparent (or pure) if you can simplify any of its subexpressions, in any order, merely by substituting definitions, without changing the outcome of the program. In particular, you can always replace a variable with its (unique!) definition.

Clearly, an assignments to a mutable variable breaks this condition, so it has to be considered a side effect -- even if it is merely local. Likewise a print statement, by the way.

There are ways to have mutable state, or IO, without breaking referential transparency. That is the mystical concept of a monad. But I won't go into that here.

Answer 2

Not knowing Python, I assume count is a "local" variable, not visible from outside, and every invokation of hailstone gets its own instance of count. If this is so, then, as @jonrsharpe explained, it is immaterial what you do to count.

Observe, however, that your code is needlessly verbose. Why not simply:

if n > 1:
    if n % 2 == 0:
        return 1 + hailstone(n/2)
    else:
        return 1 + hailstone(n*3+1)
else:
    return 1

It turns out that the variable is not needed at all, not to speak of the need to update it.

Answer 3

Your function has no side effects (aside from the print) at the function level. That's a necessary, but not sufficient, condition to be called functional. Functional programs consist of one big expression. Your example is expressions at the function level, interspersed with imperative statements in the function body. An if without an else is a statement, as is a variable reassignment.

That's not to say that an imperative function without side effects isn't better than an imperative function with side effects. There are certainly advantages to your example, even if it isn't considered purely functional.

Answer 4

This program mutates x:

x = 2
x = x * 3
x = x + 4
return x

In functional programming you don't use mutation. Your code should define each variable exactly once:

x1 = 2
x2 = x1 * 3
x3 = x2 + 4
return x3

It is possible that the compiler will allocate the same memory location for x1, x2 and x3, and mutate in place, as the original program does. However, this is an implementation detail and shouldn't be important.

Unlike the previous sequential program, you can think of the new one as a system of equations and read it in arbitrary order. In this case the computation still has to be done top-to-bottom due to data dependency, but this does not have to in general.

You can get rid of the "=" symbol altogether, by using functions. To get rid of "x1 = 2", parametrize the remaining lines by x1 and pass 2 to the function:

(function(x1) {
    x2 = x1 * 3
    x3 = x2 + 4
    return x3
})(2)

and continue this process to remove "x2 = x1 * 3" and "x3 = x2 * 4".

Sometimes you assign to a variable in a loop to accumulate something (e.g. add items in an array for x in A: sum += x). In this case, instead of repeated assignment you can rewrite the program to use functions such as "sum", "reduce", "map", "filter", which are high-level abstractions of loops.

---

I was lying. It is possible to have local mutable state in a pure functional program, as long as the mutability does not "leak" outside of the scope. In Haskell, there is a library called "ST" for this purpose. It embeds a small imperative language with commands 'create variable', 'read variable', 'write variable', and if your program does not leak a mutable variable, you can retrieve its result in a pure function. However, it is more awkward to use (see this answer) and not used as much as you use assignment in imperative languages.