Why do we use persistent data structures in functional programming?

Question

Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would happen if the data structure is not persistent? Would the program crash more often?

Answer 1

When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs. This makes it easier to conceptualize computations and get them right. It also makes them easier to test.

That is just a start. Since mathematics has long worked with functions, there are plenty of reasoning techniques that we can borrow from mathematics, and use them for rigorous reasoning about programs. The most important advantage from my point of view is that the type systems for functional programs are well-developed. So, if you make a mistake somewhere, the chances are very high that it will show up as a type mismatch. So, typed functional programs tend to be a lot more reliable than imperative programs.

When you work with mutable data objects, in contrast, you first have the cognitive load of remembering and managing the multiple states that the object goes through during a computation. You have to take care to do things in the right order, making sure that all the properties you need for a particular step are satisfied at that point. It is easy to make mistakes, and the type systems are not powerful enough to catch those mistakes.

Mathematics never worked with mutable data objects. So, there are no reasoning techniques we can borrow from them. There are plenty of our own techniques developed in Computer Science, especially Floyd-Hoare Logic. However, these are more challenging to master than standard mathematical techniques, most students can't handle them, and so they rarely get taught.

For a quick overview of how the two paradigms differ, you might consult the first few handouts of my lecture notes on Principles of Programming Languages.

Answer 2

It is easier to correctly work with persistent data structures than it is to work with mutable data structures. This, I would say, is the main advantage.

Of course, theoretically speaking, anything we do with persistent data structures we can also do with mutable ones, and vice versa. In many cases persitent data structures incure extra costs, usually because parts of them have to be copied. These considerations would have made persistent data structures much less attractive 30 years ago when supercomputers had less memory than your mobile phone. But nowadays the main bottlenecks in production of software seem to be development time and maintainance costs. Thus we are willing to sacrifice some efficiency in execution for efficiency in development.

Why is it easer to use persistent data structures? Because humans are really bad at tracking aliasing and other kinds of unexpected interactions between different parts of a program. They automatically think that because two things are called x and y, then have nothing in commmon. Afer all, it takes effort to figure out that "the morning star" and "the evening star" are really the same thing. Similarly, it is very easy to forget that a data structure may change because other threads are working with it, or because we called a method which happens to change the data structure, etc. Many of these concerns are just not present when we work with persistent data structures.

Persistent data structures also have other, technical advantages. It is typically easier to optimize them. For example, you're always free to copy a persistent data structure onto some other node in your cloud if you wish, there is no worry of synchronization.

Answer 3

Adding to others' answers, and reinforcing a mathematical approach, functional programming also has a nice synergy with Relational Algebra, and Galois Connections.

This is extremely useful in the area of Formal Methods.
For instance:

• Formal proofs in program verification are simplified with Extended Static Checking;
• A number of properties from Relational Algebra are useful in SAT solving, with tools such as Alloy;
• Galois Connections allow a calculational approach to software specification, as seen in this blog, with a reference to a paper, by Shin-Cheng Mu and José Nuno Oliveira.
• Galois Connections (and Functional Programming) can be used in a Design by Contract fashion, since they are a more general concept than Hoare Logic.

Example

The Hoare triple $\{p\} P \{q\}$ can be expressed as the contract $[P] \cdot \phi_p \subseteq \phi_q \cdot [P]$, where

• $[P]$ is the relation that denotes the semantics of program $P$;
• $\phi_p$ (resp. $\phi_q)$ denotes the coreflexive relation that captures predicate $p$ (resp. $q$);

This approach also allows weakest pre-condition and strongest post-condition calculation, which comes in handy in a number of situations.

Answer 4

I want to understand at a low level what would happen if the data structure is not persistent?

Let's look at a pseudorandom number generator with a huge state space (like "Mersenne twister" with a state of 2450 bytes) as a data structure. We don't really want to use any random number more than once, so there seems to be little reason to implement this as an immutable persistent data structure. Now let's ask outselves what might go wrong in the following code:

mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

Most programming languages don't specify the order in which MonteCarloIntegral_Bulk and MonteCarloIntegral_Boundary will be evaluated. If both take a reference to a mutable mt_gen as an argument, the result of this computation can be platform dependent. Worse yet, there might be platforms where the result is not reproducible at all between different runs.

One can design an efficient mutable data structure for mt_gen such that any interleaving of the execution of MonteCarloIntegral_Bulk and MonteCarloIntegral_Boundary will give "a correct" result, but a different interleaving will in general lead to a different "correct" result. This non-reproducibility makes the corresponding function "impure", and also leads to some other problems.

The non-reproducibility can be avoided by enforcing a fixed sequential execution order. But in that case the code could be arranged in such a way that only a single reference to mt_gen is available at any given time. In a typed functional programming language, uniqueness types could be used to enforce this constraint, thereby enabling safe mutable updates also in the context of pure functional programming languages. All this might sound nice and dandy, but at least in theory Monte Carlo simulations are embarrassingly parallel, and our "solution" just destroyed this property. This is not just a theoretical problem, but a very real practical issue. However, we have to modify (the functionality offered by) our pseudorandom number generator and the sequence of random numbers it produces, and no programming language can do this automatically for us. (Of course we can use a different pseudorandom number library that already offers the required functionality.)

At a low level, mutable data structures easily lead to non-reproducibility (and hence impurity), if the execution order is not sequential and fixed. A typical imperative strategy to deal with these problems is to have sequential phases with fixed execution order, during which mutable data structures are changed, and parallel phases with arbitrary execution order, during which all shared mutable data structures stay constant.

---

Andrej Bauer raised the issue of aliasing for mutable data structures. Interestingly enough, different imperative languages like Fortran and C have different assumptions about the allowed aliasing of function arguments, and most programmers are quite unaware that their language has an aliasing model at all.

Immutability and value semantics might be slightly overrated. What's more important is that the type system and the logical framework (like the abstract machine model, the aliasing model, the concurrency model, or the memory management model) of your programming language offers sufficient support for working "safely" with "efficient" data structures. The introduction of "move semantics" to C++11 might look like a giant step back in terms of purity and "safety" from a theoretical point of view, but in practice it is the opposite. The type system and the logical framework of the language have been extended to remove huge parts of the danger associated to the new semantics. (And even if rough edges remain, this doesn't mean that this couldn't be improved by a "better" extension of the framework.)

---

Uday Reddy raised the issue that mathematics never worked with mutable data objects, and that the type systems for functional programs are well-developed for immutable data objects. This reminded me of Jean-Yves Girard's explanation that mathematics is not used to work with changeable objects, when he tries to motivate linear logic.

One might ask how to extent the type system and logical framework of functional programming languages to allow working "safely" with "efficient" mutable non-persitent data structures. One problem here might be that classical logic and boolean algebras might not be the best logical framework for working with mutable data structures. Perhaps linear logic and commutative monoids might be better suited for that task? Perhaps I should read what Philip Wadler has to say on linear logic as type system for functional programming languages? But even if linear logic should not be able to solve this problem, this doesn't mean that the type system and logical framework of a functional programming language couldn't be extended to allow "safe" and "efficient" mutable data structures.