Why do some functional languages need software transactional memory?

Question

Functional languages, by definition, should not maintain state variables. Why, then, do Haskell, Clojure, and others provide software transactional memory (STM) implementations? Is there a conflict between two approaches?

Answer 1

There is nothing wrong with a functional language maintaining mutable state. Even "pure" functional languages such as Haskell need to maintain state in order to interact with the real world. "Impure" functional languages like Clojure allow side effects which can include mutating state.

The main point is that functional languages discourage mutable state unless you really need it. The general style is to program using pure functions and immutable data, and only interact with "impure" mutable state in the specific parts of your code that require it. That way, you can keep the rest of your code base "pure".

I think there are several reasons why STM is more common in functional languages:

• Research: STM is a hot research topic, and programming language researchers frequently prefer to work with functional langauges (a reasearch topic in themselves, plus it is easier to create "proofs" about program behaviour)
• Lock don't compose: STM can be seen as an alternative to lock-based approaches to concurrency, which starts to run into problems when you scale up to complex systems by composing different components. This is arguably the main "pragmatic" reason for STM
• STM fits well with immutability: If you have a large immutable structure, you want to make sure it stays immutable, so you don't want some other thread coming in and mutating some sub-element. Likewise, if you can guarantee immutability of said data structure, you can reliably treat is as a stable "value" in your STM system.

I personally like Clojure's approach of allowing mutability, but only in the context of strictly controlled "managed references" that may participate in STM transactions. Everything else in the language is "purely functional".

  ;; define two accounts as managed references
  (def account-a (ref 100))
  (def account-b (ref 100))

  ;; define a transactional "transfer" function
  (defn transfer [ref-1 ref-2 amount]
    (dosync
      (if (>= @ref-1 amount)
        (do 
          (alter ref-1 - amount)
          (alter ref-2 + amount))
        (throw (Error. "Insufficient balance!")))))

  ;; make a stranfer
  (transfer account-a account-b 75)

  ;; inspect the accounts
  @account-a
  => 25

  @account-b
  => 175

Note the above code is fully transactional and atomic - an external observer reading the two balances within another transaction will always see a consistent atomic state, i.e. the two balances will always sum to 200. With lock-based concurrency, this is a surprisingly hard problem to solve in a large complex system with many transactional entities.

For some extra enlightenment, Rich Hickey does an excellent job of explaining Clojure's STM in this video

Answer 2

Sometimes a program requires mutable state (for instance, database contents for a web app) and it would be great to be able to use it without losing the benefits of functional programming. In non-functional languages, mutable state permeates everything. If you make it explicit with some kind of special API, then you can confine it to a small identifiable region while everything else remains purely functional. Benefits of FP include easier debugging, repeatable unit testing, painless concurrency, and multicore/GPU friendliness.

Answer 3

I would imagine that it's for performance reasons.

Immutable structures are easy to reason about from a concurrency viewpoint, but it's difficult to justify recreating a tree or list from whole cloth every time you want to add a node to it. Consequently, many functional programming languages provide some mechanism under the hood for dealing with this sort of thing. STM is one such mechanism.

Consider the StringBuilder in C#. Every C# programmer knows that you don't combine string objects in a loop directly, because strings are immutable in C#, and you have to create a brand new one every time you want to concatenate. StringBuilder does not suffer from this problem.

See Also
http://en.wikipedia.org/wiki/Software_transactional_memory

Answer 4

Functional languages, by definition, should not maintain state variables

Your definition is wrong. Language that cannot maintain state simply cannot be used.

The difference between functional and imperative languages is not that one of them has state and the other does not. It's in a way they maintain the state.

Imperative languages have state spread all over the program.

Functional languages isolate and maintain the state explicitly via type signatures. And that's the reason they provide sophisticated state management mechanisms like STM.