1

Using Functional language, How can 2 different parties achieve the result of increment/decrement operations concurrently?

For the below scenario, Let's say, I've 2 quantities in stock and 2 users in e-commerce site block 1 quantity each concurrently. How can I mark the remaining stock as '0' in FP given the state is shared and immutable? I assume that each flow gets the copy of initial stock '2' and operates upon. If so, how will it reach '0' unless serialized?

Kindly narrate this with some sample working code.

How is this different from CAS operations on AtomicInteger (in JAVA) where the client is expected to retry on failure? (Both in terms of approach and efficiency)

10
  • 2
    The same way it deals with state in synchronous code
    – Caleth
    Jan 3, 2018 at 9:54
  • 3
    How can you decrement without serialising the operations? The simple answer is, "you can't". Operations on shared variables always have to be serialised with some sort of locking. And in-keeping with your previous question, such code ceases to be "functional", since the program result becomes dependent on undeclared variables: the starting state of the counter, and the timing of when each concurrent user submits the request.
    – Steve
    Jan 3, 2018 at 10:31
  • 2
    This is probably too broad, it seems like you're after a description of how Software Transactional Memory works. Also, your tags are inappropriate - as you've phrased this question language-agnostically, consider removing the haskell and clojure tags.
    – hnefatl
    Jan 3, 2018 at 11:57
  • 2
    STM would probably be the most common approach to this in FP (the main advantage being that FP code should be able to transparently handle the retries that are required for STM without worrying about repeated side effects).
    – Jules
    Jan 3, 2018 at 12:04
  • 3
    Along with your other question, you can't just go line by line (or even block by block) and translate imperative code to functional code (if you could we'd just write a compiler to do it for us). The concepts are different, not just the idioms. You can certainly refactor an imperative codebase to a functional one, but you have to understand FP first. Learning FP is not like learning another imperative/OO language ("how do I say this in blub?"). If you want to migrate to haskell and or clojure you're going to have to start from the ground up and actually learn them. Jan 3, 2018 at 13:19

2 Answers 2

8

You are asking how functional languages handles shared mutable state. Functional languages do prefer and encourage immutable data structures, but they all (AFAIK) have provisions for mutable shared state. There is a variety of approaches, just as for imperative and OO languages, but in the case of an inventory the state would typically be a database, which would handle concurrency and locking.

A FP language running on the JVM (e.g. Clojure) can use AtomicInteger just like Java can.

For pure functional languages it is a bit more tricky since a pure language in principle does not allow any kind of mutable state. In Haskell this just means operations on shared mutable state happens in the IO monad, indicating that such operations are not pure.

In short, there is nothing magic about FP, and there is no free lunch: You cannot have purity and shared mutable state at the same time.

1
  • 1
    If there was a free lunch it would put all the lunch vendors out of business, so, good thing!
    – user251748
    Jan 3, 2018 at 13:14
7

In Haskell, a possible approach is to use software transactional memory for this.

-- silly example mixing IO and STM

doOperation :: TVar Int -> IO ()
doOperation x = do -- IO monad
   putStrLn "Incrementing value!"
   atomically $ do -- STM monad
      v <- readTVar x
      -- putStrLn "We can't do I/O here, in the middle of STM!"
      -- print v
      writeTVar x $! v+1
   putStrLn "Incrementing complete."

Using atomically, we can run STM actions in the middle of the IO actions. This allows us to read and write x, so to increment it. Alternatively, modifyTVar' (+1) would also do the increment more conveniently, but above I wanted to separate the reading from the writing.

By comparison, there is no way to run IO actions in the middle of the STM atomic transaction. If we try to uncomment the IO actions in the code above, the compiler raises a type error because IO is not STM. This is important, since we must not print v in the middle of a transaction which could still be rolled back -- we can't undo the print v, or in general other IO computations which might even use the disk or the network. (The GHC devs use launchMissiles as the archetypal example of IO having international side effects, with no possible "undo".)

Operationally, the STM monad implementation keeps track of the changes to the variable x. When reading, it logs the old value of x (no locks at this time). When writing, the new value is also logged, but not written (no locks). Subsequent reads within the transaction read the new value of x (no locks).

At the very end of the transaction, we enter the commit phase: we lock all the involved variables (using a deadlock-free lock ordering). We then test if they still contain the old values. If they don't, we rollback the transaction, and retry it again. If they do, we write the new values (from the log), unlock the variables, and we are done.

STM is not as efficient as custom algorithms for mutual exclusion / deadlock-avoidance which can be used for specific problems. It is however very general, and unlike basic locks, very composable and flexible. Pure FP makes the approach safer by checking that the programmer only uses safe operations in the transactions (no IO).

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