Why do functional languages disallow reassignment of local variables?

Question

Fair warning: I don't actually know a functional language so I'm doing all the pseudocode in Python

I'm trying to understand why functional languages disallow variable reassignment, e.g. x = x + 1. Referential transparency, pure functions, and the dangers of side effects are all mentioned, but the examples tend to go for the low-hanging fruit of functions that depend on mutable globals, which are also discouraged in imperative languages.

My question involves variables created and mutated within the function. For example:

def numsum1(n):
    sum = 0
    i = 1
    while i <= n:
        sum = sum + i
        i = i + 1
    return sum

The functional way of doing this seems to be tail recursion, where the updated sum and i are passed from function call to function call. I know that there are existing higher-order functions for this, but I think this illustrates the similarity to numsum1 more plainly:

def numsum2(n): return numsumstep(0, 1, n)

def numsumstep(sum, i, n):
    if i <= n:
        return numsumstep(sum + i, i + 1, n)
    else:
        return sum

numsum1 and numsum2 do the exact same thing (with tail call optimization) and are both referentially transparent. I do see why numsum1 is internally referentially opaque; the expressions i + 1 and sum + i change in value with each iteration and thus cannot be replaced by a constant value. But why does that matter if numsum1 itself is referentially transparent? Are there examples of functions that become referentially opaque solely because of reassigning local variables?

Answer 1

In a pure functional programming language, there is no real notion of time at all. So, saying that a variable x has value a at one point and then b later simply doesn't make any sense – it's like asking a character in a painting why she always stares in the same direction.

The advantage of having no time is that you never^† need to worry about the order in which computations happen. If a variable is in scope then it also has the correct value, i.e. the value it has been assigned. (Which assignment may actually be “after” the computation in which it is needed – definitions can be reordered at will.)

Whereas in an imperative language – well, consider this program:

def numsum1(n):
    sum = 0
    i = 1
    while i <= n:
        sum = sum + i
        i = i + 1
    midterm = sum
    while i >= 0:
        sum = sum - i
        i = i - 1
    return (midterm, i)

If for some reason you need to refactor and pull the midterm definition behind the second loop, overlooking that it actually mutates sum again, then you would get the wrong result.

Now, you might well argue that this is defeated if you need to use recursion to basically fake mutation. Isn't there just as much, or even more, potential for mistakes if you have a recursive call using a parameter still called x that is effectively the same variable anyway?
– Not quite, because outside of the recursive calls the variable is guaranteed to stay the same. The refactoring problem with the above example wouldn't happen in a functional language.

Furthermore, as Odalrick already wrote, recursion isn't actually what's normally used to replace loops in functional languages. The idiomatic Haskell version of your program is

import Data.List (sum)

numsum :: Int -> Int
numsum n = sum [1..n]

...or, using more general-purpose tools,

numsum n = foldl' (+) 0 . take n $ iterate (+1) 1

---

^†_{That's a bit of an exaggeration. Of course, you do sometimes need to take time into account even in a functional language. Obviously, if it runs somehow interactively (IO monad in Haskell), then those parts are subject to latency considerations. And even for completely pure computations, one side effect that you can't possibly avoid is memory consumption. And that's indeed the one thing that Haskell truely isn't good at: it's really easy to write code that typechecks, works, is correct, but takes gigabytes of memory (when a few kilobytes should have been enough) because some thunks are never garbage-collected.}

Answer 2

I can only share my perspective. The way I think of it is that mainstream functional languages typically combine two themes: (1) support for higher-order functions, and (2) a preference for pure computation (referential transparency, no side effects, no mutation). In principle those two could potentially be separable, but they often go together in many mainstream functional languages.

Why is it considered beneficial to avoid mutation? Arguably, avoiding mutation makes it easier to reason about the correctness of code. This is especially so in the presence of concurrency, and also relevant when you have complex mutable data structures that are shared among multiple code modules. Variable reassignment is one form of mutation -- perhaps not the most dangerous, but if you set out to build a language that prefers pure computation, there is a certain conceptual clarity and cleanness in avoiding all mutation.

You can certainly have a function that is referentially transparent, yet that internally reassigns to local variables. However, verifying referential transparency can be more challenging in the presence of mutation. In contrast, if there is no mutation whatsoever, then it is becomes more trivial to verify that code is referentially transparent. So, there can be value to restrictions that are stricter than absolutely necessary, if they make it easier to verify correctness of code. We see this idea all over the place in programming languages, including in type systems (e.g., type systems: code that violates type-safety can potentially still be correct, but may be harder to verify is correct).

Answer 3

If we want to be very precise with our words, we should say that in functional programming you don't assign a value to a variable, because assignment is a thing that you "do", and if you are telling the computer what to "do" then you are doing imperative programming instead of functional programming.

In a functional programming language, the code let x = 1 is not an instruction to assign the value 1 to the variable x; it is a declaration that the variable x is equal to 1. That is, the = symbol is used in its mathematical meaning to say that those two things are the same, interchangeable; not in its imperative programming meaning as an instruction "take the value 1 and store it in the memory location labelled x".

So, variables cannot be reassigned because they cannot be assigned in the first place. If you write let x = 1 and let x = 2 in a functional language, you are declaring that x is equal to 1 and equal to 2, which means you are declaring that 1 is equal to 2, because mathematical equality is transitive. It would not be useful for a language to allow you to declare that 1 is equal to 2.

Answer 4

There are several reasons, but they boil down to three main points:

• It's easier to reason about correctness, especially in the context of complex semantics (e.g. existential types, lazy evaluation) and security.
• It allows for optimisations that are not possible if data can change underneath.
• It allows for a transparent models of multi-threading, since read-only data does not need to be protected.

It's worth noting that non-functional languages do it too, and for much the same reasons. Java, for example, has an immutable String type. This allows static string data to be stored in read-only memory (e.g. on a microcontroller or smart card), and also makes for a more efficient and easy-to-prove security model when running potentially untrusted code.

You can't pass a String to a security-conscious part of the standard library such as the SecurityManager and then modify it after the event or in another thread. Nor can you use a String as a key in a binary search tree or hash table and then modify it, thus invalidating the data structure's guarantees.

Answer 5

In functional programming, great pains are taken to be able to know exactly what a computation depends on. The way in which you make variables be mutable, there can be cascading effects on the rest of the language.

If you just make them mutable, in that they are reference cells, then what you are effectively doing is wrapping the entire language in a state monad, where every variable in every closure becomes part of global state. For example, this is something that mutable variables let you do (in Python 3):

def make_counter():
    val = 0
    def count():
        nonlocal val
        val += 1
        return val
    return count

c = make_counter()
print(c()) # 1
print(c()) # 2
print(c()) # 3

That is not so good for analyzing the behavior of a program. Analysis is much easier if you can ignore the order in which expressions are evaluated.

It is easier to simply disallow mutable variables entirely than to develop a well-designed system that gives you useful, safe, and analyzable mutation.

One language that seems to have succeeded in this regard is Lean 4. It has a system that automatically inserts the correct folds into a monadic do-notation block to implement mutable variables. Here is an example translation of your program (using $0 \leq i < n$ rather than $1 \leq i \leq n$):

def numsum1 (n : Nat) : Nat := do
  let mut sum : Nat := 0
  for i in [0:n] do
    sum := sum + 1
  sum

This is using the "identity monad" and gets turned, effectively, into your numstep2. When it is compiled to C, it should even be a for loop with a mutable sum variable (though I didn't check).

Other monads, like the IO monad, also get local mutable variables through this system.

To be clear, the variable isn't "really" mutating since each iteration of the loop is essentially a new sum variable containing the updated value. However, the language doesn't have an interface where you can get a pointer to a mut variable, so you can't really say whether it is "really" updating in-place or not. And in fact, the runtime takes advantage of this with the Perceus functional-but-in-place paradigm.

Answer 6

What would it be like to have variable reassignment in functional programming?

First i is 0, then you do something and change i to 1 ...

But that is "do this, then that". Imperative programming; not functional.

Functional programming is declarative. You write a whole bunch of functions and the computer takes care of calling them as needed. If you had i = 0 and then a bit later i = 1 in the same scope, the compiler could decide to set i to 1 first and then to 0.

Obviously no one wants a language to do that so it is simply disallowed.

So the answer is ultimately, because it is a functional language. If it allowed reassignment it would be an imperative language.

---

edit: I think what you are actually after is a more loopish way of functional coding.

While recursion is common and powerful, the loop equivalent in functional programming is genererally map or reduce.

It's a bit awkward in Pyhon but:

import itertools
import operator

def numsum3(n):
    all_numbers = itertools.count(0)
    sums = itertools.accumulate(all_numbers, operator.add, initial=0)
    n_and_forward = itertools.islice(sums, n + 1, None)
    return next(n_and_forward)

Make a list of all the numbers. For all the numbers, sum the previous number and put it in an list. Discard all numbers up to the (n+1)th number (+1 because you used <= ). Return the first number in that list.

It is awkward in Python, but in functional languages this would be much easier to write.

---

"computer takes care of calling them as needed"

Exacly how this works depends on the language. Haskell uses monads; Elm has a "core" that does things outside the language; Erlang has a VM that does stuff.

This is one of the strengths of functional programming. The programmer actually cannot write very specific code so the "compiler" is free to do whatever it needs to.

Answer 7

Optimizers in C++ turn traditional C++ code into static single assignment when it can.

You can think of traditional imperative programming as chaining together functional steps.

struct state {
  int sum;
  int i;
};

auto numsum1 = [](int n){ 
  return fpipe{} |
    []{ return state{0, 1}; }
    | while_loop( [n](state s){ return s.i<=n; }
    )(
      [](state s){ return {s.sum+s.i, s.i+1}; }
    )
    | [](state s){ return s.sum; };
}

this is a purely functional version of the same imperative code with no recursion in "psudeo-code" that I could literally make compile in C++. [capture](arguments){body} is a C++-esque definition of a lambda, and | represents "piping the previous return value as an argument to the next function".

In this case, everything is immutable, nothing can be changed in any line of code above.

Converting traditional procedural code to this format makes reasoning about it by the compiler insanely easier, which in turn makes optimization easier.

The same is true for a human who gets used to it. Variables don't change their meaning or value in a given function call; they always have the same meaning.

This pattern "variables mean one thing", "data flows are explicit", "build algorithms out of smaller algorithms" is pretty fundamental to functional programming.

Answer 8

The answer is really purity. Pure functional languages strive to be pure functional languages. That involves not doing impure things.

I'm just learning F# right now. I notice that it has a policy of "variables are immutable by default, but can be declared to be mutable." So F# would be an example of a language that chose not to go the purist route.

Thanks to the Church-Turing Thesis, we know that you can convert between any lambda calculus problem and a corresponding Turing machine. This implies that there's always a way to go from functional programming constructs to imperative constructs, and back. We can always construct a pure functional program which is isomorphic to a functional program that has some mutable variables. Yakk's answer points at Single Static Assignment (SSA) which is one algorithm which helps tease apart assignments, shepherding it towards pure functional languages if one wishes.

Its all a matter of the intent of the language designer. Most of the big functional languages I know of were designed by people who wanted to explore pure functional languages and who believed that the notation of functional languages was superior to that of imperative languages. Their languages reflect these philosophies.

As a practical manner, as a language designer, consider the details that have to be handled when permitting something like re-assignment in a functional language. You have to make sure of two things:

• Reassignment of variables does not break assumptions that you relied on for the effectiveness of your language (referential transparency being the big one)
• Your users need to not be surprised by where reassignment works, where it doesn't work, and how it acts. Surprised users are unhappy users when it comes to programming languages.

Personal anecdote: I just dealt with the fun of the opposite of the question you ask -- the addition of functional bits into an imperative language. I just found out that C++'s std::function does not provide any guarantees regarding the use of dynamic memory, even in situations where it is clear that such dynamic memory could be avoided. It depends on the language implementer to decide when and where dynamic memory is needed.

Having now written a library using std::function in an environment where such dynamic memory is forbidden, I now need to go back through it and basically rewrite the entire API... Its quite exciting. You can hear the thrill in my voice as you read this, can't you? I am a user that got surprised.

Answer 9

Disallowing assignment is part of the definition of "functional programming" and "functional language". On one level, you're simply asking why the definition of "functional language" is correctly being applied, so that languages which allow mutation of local variables are not eligible.

Why is variable mutation excluded from the definition of "functional"? Firstly, variable mutation will not achieve anything unless you have multiple execution code paths which can reach the same point. For instance:

let a = 0
if condition
  a = 4
else
  a = 5

but this doesn't exist in functional programming also. There are no statements. An if/then conditional in a functional language is an expression which calculates a value. In a functional language, the body of a function can consists of zero or more variable binding constructs, followed by an expression. Those binding constructs are not statements, though; they are just a way to factor out values from the body expression by giving them names, like in mathematics.

Since there are no statements in functional programming, variable assignments serve no purpose, because a variable assignment is a statement which alters a variable in order to induce a change in the calculation performed in other statements. And, not to mention, that since there are no statements and variable assignment is a kind of statement, it is ruled out that way.

A functional language can allow rebinding a variable in the same scope. For instance:

let x = 0
let x = x + 1

this is not assignment though; these are two different x variables, where the second one shadows the first one. A functional language would provide no way for the first let x = 0 to be skipped; e.g. this would not be featured in a functional language:

goto label
let x = 0
label:
let x = x + 1

To reiterate, the let bindings are not imperative statements. The notation:

let x = 0
let x = x + 1
x + x  # body expression

is just a verbose spelling of:

let x = 0 + 1
x + x

which is just another spelling of:

1 + 1

which is just another spelling of

2

"Functional" is all about functions: calculating by applying functions to values. In the purest form of functional programming, lambda calculus, there are no variables, other than function parameters.

The Lisp language (not functional, by the way, but supporting functional programming concepts) originally had no let operator at all for binding local variables. lambda came first, and let was invented as a syntactic sugar for a lambda. So that is to say if we have:

(let ((x 1)
      (y 2)
  (+ x y))

This can be written as a call to an anonymous function:

((lambda (x y) (+ x y)) 1 2)
  ^^^^^^^^^^^^^^^^^^^^^ ^^^
    function            args

These two expressions notate exactly the same thing: binding x to 1, y to 2 and evaluating(+ x y) producing 3.

So when you think of a variable in the context of functional programming, you should think "function parameter". If you look hard enough, you will see the function.

When local variables are bound prior to the evaluation of some expression that references them, you can think of it as the parameters of an anonymous function receiving formal argument values.

In functional programming, every variable is a actually a formal parameter, and the only way it receives a value is by receiving a formal argument as part of a function call. And, so, that's the nutshell of why there is no assignment and why it's called "functional".

Answer 10

numsum1 can be mechanically translated into numsum2. In fact, the translation is essentially the same as the one performed anyway by virtually all optimizing compilers, as Andrew Appel pointed out in the paper SSA is Functional Programming. *

Since it can be done automatically, you could argue that there's no reason to make the human programmer do it.

I think the strongest argument against this is that there's nothing stopping you from writing your entire program as one big function. Then you can mutate global variables, since they are local to the current function. The automatic translation to SSA/functional form will convert the globals to hidden parameters, so everything will work. But the larger the program gets, the more those parameters will truly be hidden from the human programmer, which is the problem that pure functional programming is meant to avoid.

If limited to small functions like your example, where the usage patterns are obvious, I think the automatic translation would be harmless, but also not very useful since it's easy to transform by hand. When it's difficult to do the transformation by hand, it's because it's hard to analyze all of the dependencies in the code, and that's when you should do it by hand, since functional programming is about making those dependencies explicit (and ideally minimizing them).

---

* I'd say rather "SSA is a hacky subset of functional programming", since the functional form includes the SSA flowgraph, the dominance tree, and additional information not found in either of them in a nice unified way, and I think it's easier to understand.

Answer 11

It’s closer to what an optimizing compiler does

Back in the olden days, on compilers that couldn’t optimize worth a DRAM, it was necessary to tell the compiler to throw out the old value we no longer needed, and replace it with an updated one. Early programming languages tried to stay close to the low-level operations of the processor, which would update a variable in a register or memory. But modern compilers perform dependency analysis, code movement and register allocation. They’re better at figuring out when they can drop or spill a variable from a register than a human is. So you can now declare every variable you need as a static single assignment, and let the compiler transform your high-level computation into efficient code.

Traditional functional languages transform code into continuation-passing style, moving blocks of code around so that the computations execute after their dependencies. They also allocate registers so that any quantity that’s no longer needed gets discarded, freeing up a register for another quantity that will be needed soon. They do this better than humans ever could: if you keep around a variable that you no longer need, you wast a register, and if you drop it too soon, you cause a bug the compiler can’t catch.

Unmodifiable variables are in many ways easier to optimize, since you’ll know for sure that you can do the computation once and re-use the value, you know for sure when it’s safe to use a reference instead of cloning the object, you know for sure on modern processors that reading the variable is thread-safe, and so on. Some computer scientists go further and try to prove that certain program transformations are provably correct on pure functions, in category theory.

Even many compilers for procedural languages transform code like x = x + 1 into a static single assignment, equivalent to x_1 = x + 1.=, and then treat x and x_1 as if they were different, immutable variables with a dependency between them. More complicated expressions, such as conditional assignments, get transformed into phi functions on the right-hand side. There’s an efficient algorithm to transform an abstract syntax tree in SSA form into one in CPS form and then apply all the optimizations from that.

If the optimizer is going to try to produce good code by transforming the program into a series of pure computations anyway, it’s less likely to get confused if the source code is written that way.

It prevents certain bugs

In this pseudocode,

y = f(x)

if (a > b)
  x = x + 1

z = g(x)

What is the value of x when z is computed? Are we sure that x always gets properly initialized? If this code gets refactored so z = g(x) gets moved right after y = f(x), which you might want to do for clarity, its meaning sometimes changes, giving you a Heisenbug. If you’re reviewing a large function with many possible paths of execution, when we see x being used, how was it set in this context?

In a functional language (or even a hybrid like Rust), you might write something like

let y = f(x0)
    x1 = if   (a > b)
         then x0 + 1
         else x0
    z = f(x1)

In many languages, you could even initialize z before x1, and there will be no doubt what you meant. Declaring x0 and x1 is completely unambiguous and the meaning of the same symbol does not change if you move it elsewhere in the same block. You can also be certain that x0 and x1 were initialized once and only once, and what they were initialized to.

It’s easier to analyze

It isn’t, in general, possible to deduce whether a code path in an arbitrary program is reachable. However, if you restrict the language so that only certain safe operations are possible, you can more safely prove what will and won’t happen. For example, when variables are immutable, many complex special cases involving modification through an alias cannot occur. C++ even introduced a special form of immutability, constexpr, specifically to make it possible for the compiler to perform calculations on constants at compile time and fold them into the executable.

Or, let’s take the great example you gave:

def numsum1(n):
    sum = 0
    i = 1
    while i <= n:
        sum = sum + i
        i = i + 1
    return sum

We want an optimizing compiler to be able to tell that this is all equivalent to return n. Optimizers for imperative languages are heavily-focused on analyzing loops, and this while loop is simple enough that I’d expect a modern C, C++, Java or Rust compiler to be able to figure the translation out.

Functional languages have equivalents

A functional language can also have variables that mutate within each iteration of a loop, only it would refactor into a tail-recursive function:

numsum1 n = go 1 0 where
  go (n+1) sum  = sum
  go i sum = go (i+1) (sum+1)

Or, if we’re not worried about negative numbers as inputs (although we could easily handle those too):

numsum1 n = go 0 n where
  go sum 0 = sum
  go sum i = go (sum+1) (i-1)

Tail recursion on a pattern match like this is exactly equivalent to the loop: you perform a test at the beginning of each repetition to see whether you continue, and if so, increment the loop counter (which on a modern ABI means updating registers and re-using the same stack frame) and jump back to the start of the loop/tail-recursive function. Both versions have a local variable named i within the block of code whose value changes every time it runs. Since imperative-language compilers also want to be able to optimize tail-recursive functions, it’s simpler for the compiler to be able to rely on a great optimizer for recursive code, and not need to analyze arbitrary while loops too.