Can producer-consumer problem be solved without using assignment?

Question

I am interested in finding if producer-consumer problem when there are multiple produce and multiple consumer be solved without using assignment i.e., using functional style of programming? How?

Producer-consumer problem

Thanks

Answer 1

All of the implementations I've seen of producer-consumer in SML were forced to rely on refs (in order to maintain a queue of 'sleeping' items), so I'd be inclined to say "no".

Answer 2

Having multiple threads necessarily requires impure (non-functional) actions. Pure functional programming considers your application to be the evaluation of a function. The concept of concurrently evaluating two things and passing data between them is not meaningful within this framework.

Although one can evaluate multiple parts of a function in parallel, as in Haskell's `par ` operator, this is not the same as the producer-consumer problem, and as such I don't think you'll be able to solve it in a functional way.

Answer 3

There are many way to solve this; each has different drawbacks.

For example, the "put" could spawn a new thread each time. That way, you wouldn't need a buffer at all. If lots of requests come in, you spawn lots of threads until your CPU is more busy with switching between threads than actually executing them. But this just moves the problem from your code into the OS: At a certain point, you always have to synchronize access to a variable in memory. The OS must maintain a list of threads and access to this list must be synchronized.

Either you want to limit the number of threads (then a "put" must be able to read the variable while threads might terminate at the same time and decrement it -> again synchronized access). Or you risk running out of resources because you have too many threads.

You could post a message when "put" is called and the consumers could listen to the message. But that's only a complex way to implement "wait" for threads. And you need a way to make sure that only a single consumer gets the message. Again, you'll need some synchronized data structure.

So in the end, it's not really the assignment, which is the problem, but concurrent access to a single variable and no matter how you try, for any implementation of produce-consumer, you must be able to do this (or the whole will be single threaded).

Answer 4

Yes, you can do it quite nicely with message passing in Concurrent ML. Don't be put off by the age of the system; John Reppy's book and papers are excellent guides to the topic. Beautiful stuff!

Answer 5

Yes. Check out functional reactive programming (FRP), which is related to Concurrent ML (Norman's suggestion) but is purely functional. The semantics of FRP is highly concurrent while having a simple, precise, deterministic, functional semantic model (functions of time).