Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
    
One way to handle concurrency issues is to make copies of the queue each time (somewhat expensive, but works). –  Job May 18 '11 at 22:28
    
infoq.com/presentations/Functional-Data-Structures-in-Scala You may find this speach insightful. –  deadalnix Feb 27 '12 at 10:34
add comment

4 Answers

up vote 19 down vote accepted

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.

share|improve this answer
1  
+1 Much more complete answer, although I suppose one could quibble that Erlang is not a pure FP language. –  Rein Henrichs May 18 '11 at 23:02
    
@Rein Henrichs: Indeed. In fact, of all currently existing mainstream languages, Erlang is the one which most faithfully implements Object-Orientation. –  Jörg W Mittag May 18 '11 at 23:44
2  
@Jörg Agreed. Although, again, one could quibble that pure FP and OO are orthogonal. –  Rein Henrichs May 19 '11 at 0:52
    
Great answer. Thanks. –  venkram May 19 '11 at 3:06
    
So, for implementing an immutable queue in a concurrent software, messages need to be sent and received between nodes. Where are stored pending messages? –  mouviciel Jan 23 '13 at 8:49
show 5 more comments

Stateful behavior in a FP langauge is implemented as a transformation from a prior state to a new state. For instance, enqueue would be a transformation from a queue and a value to a new queue with the value enqueued. Dequeue would be a transformation from a queue to a value and a new queue with the value removed. Constructs like monads have been devised to abstract this state transformation (and other results of computation) in useful ways

share|improve this answer
3  
If it's a new queue for every add/remove operation, how would two (or more) async operations (threads) share the queue? Is it a pattern to abstract the new-ing of the queue? –  venkram May 18 '11 at 21:06
    
Concurrency is a completely different question. I can't provide an sufficient answer in a comment. –  Rein Henrichs May 18 '11 at 21:13
2  
@Rein Henrichs: "can't provide an sufficient answer in a comment". That usually means you should update the answer to address the comment-related issues. –  S.Lott May 18 '11 at 21:16
    
Concurrency can be monadic too, see haskells Control.Concurrency.STM. –  alternative May 18 '11 at 21:45
1  
@S.Lott in this case it means that the OP should ask a new question. Concurrency is OT to this question, which is about immutable data structures. –  Rein Henrichs May 18 '11 at 21:46
show 2 more comments

...problems that are solved by stateful representations in OOP with immutable ones in FP (For ex: A queue with Producers & Consumer)

Your question is what is called an "XY problem". Specifically, the concept you cite (queue with producers & consumer) is actually a solution and not a "problem" as you describe. This introduces a difficulty because you are asking for a purely functional implementation of something that is inherently impure. So my answer starts with a question: what is the problem you are trying to solve?

There are many ways for multiple producers to send their results to a single shared consumer. Perhaps the most obvious solution in F# is to make the consumer an agent (aka MailboxProcessor) and have the producers Post their results to the consumer agent. This uses a queue internally and it is not pure (sending messages in F# is an uncontrolled side effect, an impurity).

However, it is quite likely that the underlying problem is something more like the scatter-gather pattern from parallel programming. To solve this problem you might create an array of input values and then Array.Parallel.map over them and gather the results using a serial Array.reduce. Alternatively, you might use functions from the PSeq module to process the elements of sequences in parallel.

I should also stress that there is nothing wrong with stateful thinking. Purity has advantages but it is certainly not a panacea and you should make yourself aware of its shortcomings as well. Indeed, this is precisely why F# is not a pure functional language: so you can use impurities when they are preferable.

share|improve this answer
add comment

Clojure has a very well thought out concept of state and identity, which is closely related to concurrency. Immutability plays an important role, all values in Clojure are immutable, and can be accessed through references. References are more than just simple pointers. They manage access to value, and there are multiple types of them with different semantics. A reference can be modified to point to a new (immutable) value, and such a change is guaranteed to be atomic. However, after the modification all other threads still work on the original value, at least until they access the reference again.

I highly recommend you to read an excellent article about state and identity in Clojure, it explains the details much better then I could.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.