Java: state sharing between threads in functional programming

Question

My question is a more specific instantiation of this question: Functional programming: state vs. reassignment

I'm a newbee to FP and trying to understand it through Java.

I have the following class whose object is shared between multiple threads:

public class Bank
{
    private double[] accounts = new double[1000];

    public synchronized void transfer(int from, int to, double amount)
    {
        account[from] -= amount;
        account[to] += amount;
    }
}

(This is a very simplified example, hence other details such as validation and condition waiting are omitted).

Because 'transfer' method is synchronized, Bank object's mutable state won't be corrupted even if it's shared with multiple threads. If I want to achieve the same thing through FP in Java, how would I write that code? (I would like to see an actual code example).

EDIT: my interest in FP stems from its potential for writing thread-safe, concurrent applications. Following is a link to an article that claims it: http://www.defmacro.org/ramblings/fp.html

EDIT2: just found out about an STM for Java. Not sure about its performance, but it seems to provide what I wanted. http://multiverse.codehaus.org/60second.html

Answer 1

There are many ways to approach your shared, synchronized state variable in a more functional way.

Transactional variables

The classic approach here is to use transactional memory:

• e.g. to implement a transaction account

you have precisely one shared state variable in the program, supporting rollback on conflicting writes. In Haskell, this would be represented via a TVar (transaction variable), in the STM monad (a monad that supports state only via transactional variables).

The benefit of using STM here is that you can guarantee deadlock avoidance (though livelock is still possible).

Memory Variables

You can also use more traditional approaches such as MVars. These are mutable variables that behave as locks:

• they contain only one value
• that value may be removed or put into the variable
• if a thread tries to write to a full MVar, it blocks
• if a thread tries to read from an empty MVar, it blocks

In this way you can support threads updating the shared value atomically.

I'd go for the STM solution, since that's the most idiomatic.

Answer 2

The main thing to turning this into a functional approach is for it compute a new world. In your example the Bank state is your world, so you want to compute a new Bank state for each TX. This might look something like:

class BankState implements Function<Id, AccountState> {
  final Map<Id, AccountState> balances; // ctor injected immutable

  /** initial ctor, build a map of balances computed by from function */
  BankState(Function<Id, Option<AccountState>> from, Iterable<Id> accounts) {
    this.balances = computeMap(from, accounts);//
  }

  /** overlay ctor, if account state provided by the tx use that, 
    * otherwise the old one is used */
  BankState(Function<Id, Option<AccountState>> tx, Map<Id, AccountState> old) {
    this.balances = overlay(tx, old);// special map with overlay
  }

  public AccountState apply(Id id) {return balances.get(id);}

  public BankState update(Function<Id, Option<AccountState>> tx) {
    return new BankState(tx, balances);
  }

  public BankState transfer(final Id from, final Id to, final Money amount) {
    return update(new Function<Id, Option<AccountState>>() {
      public Option<AccountState> apply(Id id) {
        if (id.equals(from) return some(bank.apply(id).debit(amount));
        if (id.equals(to) return some(bank.apply(id).credit(amount));
        return none();
      }
    });
  }
}

You can then simply use an AtomicReference to hold the current state and update it to a new BankState atomically.

You'd need overlay and compute map implementations, but these are pretty easily created using Guava for instance (it already has MapMaker.makeComputingMap(Function) for instance).

This is a naïve implementation for illustrative purposes, a real implementation would contain many optimisations.

The Option I used is here: https://bitbucket.org/atlassian/fugue/src/master/src/main/java/com/atlassian/fugue/Option.java

Answer 3

FP is thread safe, because there is no mutable state. Now your example contains mutable state.

It follwos that you can't make it thread safe by applying FP principles, unless you find a way to achieve what you want without using mutable state.

You could have a number of threads that start out with a balance of 0 for each account and process a number of transactions, thereby maintaining the aggregate effect of the processed transactions. At the end, you could sum up all acounts and the initial amounts, and get the overall result.

Answer 4

The idea of FP is that you avoid mutable state, and when state is essential you simulate mutability using functional constructs. For example, in Haskell you can do this using monads.