Functional Programming – Understanding Immutability

%ffunctional programmingimmutability

I am trying to understand dealing with immutable data in FP (specifically in F#, but other FP’s are ok as well) and break the old habit of state-full thinking (OOP style).
A part of the selected answer to the question here reiterated my search for any write-ups around problems that are solved by stateful representations in OOP with immutable ones in FP (For ex: A queue with Producers & Consumer). Any thoughts or links are welcome? Thanks in advance.

Edit: To clarify the question a little more, how would immutable structures (ex: queue) be shared concurrently across multiple threads (ex: producer and consumer) in FP

Best Answer

Although it's sometimes expressed that way, functional programming¹ doesn't prevent stateful computations. What it does is force the programmer to make state explicit.

For example, let's take the basic structure of some program using an imperative queue (in some pseudolanguage):

q := Queue.new();
while (true) {
    if (Queue.is_empty(q)) {
        Queue.add(q, producer());
    } else {
        consumer(Queue.take(q));
    }
}

The corresponding structure with a functional queue data structure (still in an imperative language, so as to tackle one difference at a time) would look like this:

q := Queue.empty;
while (true) {
    if (q = Queue.empty) {
        q := Queue.add(q, producer());
    } else {
        (tail, element) := Queue.take(q);
        consumer(element);
        q := tail;
    }
}

Since the queue is now immutable, the object itself doesn't change. In this pseudo-code, q itself is a variable; the assignments q := Queue.add(…) and q := tail make it point to a different object. The interface of the queue functions has changed: each must return the new queue object that results from the operation.

In a purely functional language, i.e. in a language with no side effect, you need to make all state explicit. Since the producer and consumer are presumably doing something, their state must be in their caller's interface here as well.

main_loop(q, other_state) {
    if (q = Queue.empty) {
        let (new_state, element) = producer(other_state);
        main_loop(Queue.add(q, element), new_state);
    } else {
        let (tail, element) = Queue.take(q);
        let new_state = consumer(other_state, element);
        main_loop(tail, new_state);
    }
}
main_loop(Queue.empty, initial_state)

Note how now every piece of state is explicitly managed. The queue manipulation functions take a queue as input and produce a new queue as output. The producer and consumer pass their state through as well.

Concurrent programming doesn't fit so well inside functional programming, but it fits very well around functional programming. The idea is to run a bunch of separate computation nodes and let them exchange messages. Each node runs a functional program, and its state changes as it sends and receives messages.

Continuing the example, since there's a single queue, it's managed by one particular node. Consumers send that node a message to obtain an element. Producers send that node a message to add an element.

main_loop(q) =
    consumer->consume(q->take()) || q->add(producer->produce());
    main_loop(q)

The one “industrialized” language that gets concurrency right³ is Erlang. Learning Erlang is definitely the path to enlightenment⁴ about concurrent programming.

Everybody switch to side-effect-free languages now!

¹ This term has several meanings; here I think you're using it to mean programming without side effects, and that's the meaning I'm also using.
² Programming with implicit state is imperative programming; object orientation is a completely orthogonal concern.
³ Inflammatory, I know, but I mean it. Threads with shared memory is the assembly language of concurrent programming. Message passing is a lot easier to understand, and the lack of side effects really shines as soon as you introduce concurrency.
⁴ And this is coming from someone who's not a fan of Erlang, but for other reasons.

Related Topic