Concurrency in Clojure, Haskell and Erlang
Tuesday, January 04, 2011
The most significant challenge when writing a concurrent program is managing shared data. Sharing data requires that multiple threads of execution coordinate their actions. Concurrent programming would be easy without this coordination. Each process could go merrily on its way without consideration of what every other process is doing. But concurrent programming is not that easy.
Each programming languages takes a different approach to solving this coordination problem. Some languages emphasize the use of locks to control shared data. But locks quickly become difficult to manage and leave much to be desired.
Other languages rely on immutability to protect shared data. Immutability is a characteristic of a data structure that distinguishes it from a mutable data structure. An immutable data structure is one whose state cannot be changed after it is created [Liskov 2001]. Thus, a mutable data structure is one who state can be changed after creation.
In this post, I will examine the concurrency mechanisms provided by four languages: Java, Clojure, Haskell, and Erlang. Each language provides something unique to concurrent programming.
Java
In Java, mutable objects are the default. Concurrency is implemented using independent flows of execution called threads. If multiple threads can reach the same mutable objects, the programmer must protect that state with locks that allow only one thread access at a time. Java provides several mechanisms to support this model. Among those mechanisms are two keywords:
The synchronized keyword allows a programmer to protect access to methods and statements. For the purpose of this document we will focus on protected methods. For example, we could implement a counter class as follows:
Defining the increment method as synchronized has two effects. First, it prevents invocations of the method from different threads from interleaving. Second, it guarantees that a change to the state of the object will be visible to all threads. It is important to note the synchronized keyword actually locks the object – not just the method. So the decrement method, which is also synchronized, participates in the same locking as the increment method.
It is possible to make a data structure in Java that is immutable, but it is also easy to violate that immutability. Mäntylä et al. [2008] found that Java’s mechanisms for immutability (the final and private keywords) are only effective as documentation of immutability. And errors relating to these mechanisms are difficult to find in code reviews.
With the release of Java 5.0, the language introduced a new API for concurrent programming. These include:
The most important of these new features is the Task Scheduling Framework, which we will illustrate later in this post. It provides a framework for scheduling and executing asynchronous tasks. Also of significance is the new Lock framework. While locking is built into Java with the synchronized keyword described above, there are a number of limitations. The new Lock framework provides a more robust set of locking features – such as timeouts and interrupt threads.
Clojure
In Clojure, immutable state is the default. The few parts of a program that are mutable are distinct and must be explicitly defined as using certain concurrency mechanisms provided by the language. These mechanisms include:
For the purpose of this document we will focus on the Refs. Refs provide a mutable reference to an immutable object. For example, we could create a ref to current song playing in a music program:
The ref wraps and protects access to the internal state, which is the string “Canon in D”. We can read the current-song using the deref form:
The statement above would return the string “Canon in D”. We cannot change the internal value of current-song, which is “Canon in D”, but we can change where the ref points with ref-set:
However, the above statement will throw an exception because the change must be protected. In Java and Python, this would be done with locks. But in Clojure, this is done with transactions. The dosync form is used to define a transaction:
Clojure provides an implementation of Software Transactional Memory (STM). This guarantees that updates are atomic, consistent and isolated (the ACI of ACID).
Haskell
Like Clojure, Haskell provides an implementation of Software Transactional Memory (STM). However, the STM is a relatively new extension to the Glasgow Haskell Compiler [Harris 2005]. It was introduced in 2005, and reuses the mechanisms introduced by Concurrent Haskell [Jones 1996]. For the purpose of this post, we will refer to it all as Haskell.
The Haskell STM is implemented with a monad. A monad is an abstract data type that is used in functional languages to represent a computation. This is similar to how an object-oriented language would use objects to represent data. The STM monad allows programmers to write atomic transactions. This allows them to avoid common concurrency problems such as race conditions and deadlocks. For example, the following Haskell code implements a function, putR, that reads a value from a resource, and writes back to the same location after incrementing the value.
This function takes two arguments. The first is a transactional variable, r, of type TVar Int. The first line, the type declaration, simply gives a name to this type. The second argument is the value that will be add to the transactional variable. Finally, the function returns an STM monad.
Both the readTVar and writeTVar operations return STM monads – this demonstrates how STM monads can be composed into largers STM actions. The putR function can then be passed to the atomic function as follows:
The atomic function takes a memory transaction of type STM and runs it atomically with respect to all other memory transactions. The atomic function and the STM type are built on top of the framework described by Harris et al. [2005].
Erlang
Erlang takes a significantly different approach to protected shared data: it doesn't allow for any data to be shared! Instead, Erlang provides a robust framework for passing messages between processes. It does this by following the Actor model.
Inter-process communication works via a shared-nothing asynchronous message passing system: every process has a "mailbox" -- a queue of messages that have been sent by other processes and not yet consumed. A process uses the receive primitive to retrieve messages that match desired patterns. A message-handling routine tests messages in turn against each pattern, until one of them matches. When the message is consumed and removed from the mailbox the process resumes execution. A message may comprise any Erlang structure, including primitives (integers, floats, characters, atoms), tuples, lists, and functions.
The following code creates a new process and invokes the function web:start_server(Port, MaxConnections).
We can then send an asynchronous message to the ServerProcess. The message in the example below consists of a tuple with the atom "pause" and the number "10".
Finally, we can define how to receive messages that are sent to the process:
There are several advantages to this model. Because there is no shared data, is no need to control access. The message that passed to an actor is immutable.
A Closer Look at Clojure
To illustrate the differences between a language that relies on locks, and a language that relies on STM, consider the following two examples in Java and Clojure. Both programs create a vector of integers and use multiple threads to iteratively increment each item in the vector, which creates extreme contention. The Clojure example returns the correct result because it executes within a transaction. This allows it to protect access to the vector of integers.
The Java example, however, does not have a way to protect access to the vector of integers. So the Java program will yield different results each time it is executed.
The problem with the Java example is that it does not control the critical section in which the program reads a value from the “refs” vector and updates it (line 19). The only mechanism Java provides for protecting a critical section is a lock. However, a lock around line 19 would not be sufficient if other operations had access to the “refs” vector. Thus, we would need a more complicated locking scheme. However, the “dosync” form in the Clojure example provides sufficient means to protect the critical section no matter what the circumstances.
The advantage of having an STM in Clojure and Haskell is that the STM simplifies the understanding of concurrent programs and helps make them more maintainable. It does this by seamlessly integrating itself into the existing high-level abstractions of the language – such as modules and objects [Cascaval 2008]. A disadvantage of STM, however, is the need to abort failed transactions. This means that transactions cannot perform any operation that cannot be undone – such as most I/O.
Conclusion
Java provides sufficient mechanisms to accomplish concurrent programming. But its implementation is difficult to understand, and makes it easy for a programmer to introduce bugs. Clojure, Haskell and Erlang provide a more structured environment for concurrent programming, making it less likely that a programmer will introduce a bug. This is due to immutability and STM in the case of Clojure and Haskell. But it is due to the Actor model in the case of Erlang.
It is important that a concurrency model allow the programmer to maintain an internal understanding of the program. An internal understanding means that the programmer does not need to watch the program execute in order to predicate what it will do. This is similar to the "independent coordinate system" that Dijkstra favored in his GOTO Considered Harmful letter.
Clojure, Haskell and Erlang provide models that lead to programs that can be understood with less difficult than the locking model of Java (and other mainstream languages).
References
CASCAVAL, C. BLUNDELL, C. MAGED, M. CAIN, H. W. WU, P. CHIRAS, S. CHATTERJEE, S., 2008. Software Transactional Memory: Why is it only a Reasearch Toy? ACM Queue, October 24, 2008.
GOETZ, B., 2006. Java Concurrency in Practice. Addison-Wesley Professional (May 19, 2006).
HARRIS, T. MARLOW, S. JONES, S. P. 2005. Composable Memory Transactions. In ACM Symposium on Principles and Practice of Parallel Programming 2005 (PPoPP'05).
HOLLOWAY, S., 2008. Programming Clojure. Pragmatic Bookshelf (May 21, 2009).
JONES, S. P. GORDON, A. FINNE, S., 1996. Concurrent Haskell. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (PoPL).
LISKOV, B. GUTTAG, J. 2001. Program Development in Java, Addison-Wesley (2001).
MÄNTYLÄ, LASSENIUS. 2008. What types of defects are really discovered in code reviews. In IEEE Transactions on Software Engineering, pp. 430-448.
Each programming languages takes a different approach to solving this coordination problem. Some languages emphasize the use of locks to control shared data. But locks quickly become difficult to manage and leave much to be desired.
Other languages rely on immutability to protect shared data. Immutability is a characteristic of a data structure that distinguishes it from a mutable data structure. An immutable data structure is one whose state cannot be changed after it is created [Liskov 2001]. Thus, a mutable data structure is one who state can be changed after creation.
In this post, I will examine the concurrency mechanisms provided by four languages: Java, Clojure, Haskell, and Erlang. Each language provides something unique to concurrent programming.
Java
In Java, mutable objects are the default. Concurrency is implemented using independent flows of execution called threads. If multiple threads can reach the same mutable objects, the programmer must protect that state with locks that allow only one thread access at a time. Java provides several mechanisms to support this model. Among those mechanisms are two keywords:
• synchronized –provides a locking mechanism, which allows only one thread to access a method or statement at a time.
• volatile – creates a memory barrier for a variable. It effectively synchronizes all cached copies of variables within main memory.
The synchronized keyword allows a programmer to protect access to methods and statements. For the purpose of this document we will focus on protected methods. For example, we could implement a counter class as follows:
Defining the increment method as synchronized has two effects. First, it prevents invocations of the method from different threads from interleaving. Second, it guarantees that a change to the state of the object will be visible to all threads. It is important to note the synchronized keyword actually locks the object – not just the method. So the decrement method, which is also synchronized, participates in the same locking as the increment method.
It is possible to make a data structure in Java that is immutable, but it is also easy to violate that immutability. Mäntylä et al. [2008] found that Java’s mechanisms for immutability (the final and private keywords) are only effective as documentation of immutability. And errors relating to these mechanisms are difficult to find in code reviews.
With the release of Java 5.0, the language introduced a new API for concurrent programming. These include:
• Task Scheduling Framework
• Concurrent collections
• Atomic variables
• Synchronizers
• Locks
• Nanosecond-granularity timing
The most important of these new features is the Task Scheduling Framework, which we will illustrate later in this post. It provides a framework for scheduling and executing asynchronous tasks. Also of significance is the new Lock framework. While locking is built into Java with the synchronized keyword described above, there are a number of limitations. The new Lock framework provides a more robust set of locking features – such as timeouts and interrupt threads.
Clojure
In Clojure, immutable state is the default. The few parts of a program that are mutable are distinct and must be explicitly defined as using certain concurrency mechanisms provided by the language. These mechanisms include:
• Refs, which manage coordinated, synchronous changes to shared state.
• Atoms, which manage uncoordinated, synchronous changes to shared state.
• Agents, which manage asynchronous changes to shared state.
• Vars, which manage thread-local state.
For the purpose of this document we will focus on the Refs. Refs provide a mutable reference to an immutable object. For example, we could create a ref to current song playing in a music program:
The ref wraps and protects access to the internal state, which is the string “Canon in D”. We can read the current-song using the deref form:
The statement above would return the string “Canon in D”. We cannot change the internal value of current-song, which is “Canon in D”, but we can change where the ref points with ref-set:
However, the above statement will throw an exception because the change must be protected. In Java and Python, this would be done with locks. But in Clojure, this is done with transactions. The dosync form is used to define a transaction:
Clojure provides an implementation of Software Transactional Memory (STM). This guarantees that updates are atomic, consistent and isolated (the ACI of ACID).
Haskell
Like Clojure, Haskell provides an implementation of Software Transactional Memory (STM). However, the STM is a relatively new extension to the Glasgow Haskell Compiler [Harris 2005]. It was introduced in 2005, and reuses the mechanisms introduced by Concurrent Haskell [Jones 1996]. For the purpose of this post, we will refer to it all as Haskell.
The Haskell STM is implemented with a monad. A monad is an abstract data type that is used in functional languages to represent a computation. This is similar to how an object-oriented language would use objects to represent data. The STM monad allows programmers to write atomic transactions. This allows them to avoid common concurrency problems such as race conditions and deadlocks. For example, the following Haskell code implements a function, putR, that reads a value from a resource, and writes back to the same location after incrementing the value.
This function takes two arguments. The first is a transactional variable, r, of type TVar Int. The first line, the type declaration, simply gives a name to this type. The second argument is the value that will be add to the transactional variable. Finally, the function returns an STM monad.
Both the readTVar and writeTVar operations return STM monads – this demonstrates how STM monads can be composed into largers STM actions. The putR function can then be passed to the atomic function as follows:
The atomic function takes a memory transaction of type STM and runs it atomically with respect to all other memory transactions. The atomic function and the STM type are built on top of the framework described by Harris et al. [2005].
Erlang
Erlang takes a significantly different approach to protected shared data: it doesn't allow for any data to be shared! Instead, Erlang provides a robust framework for passing messages between processes. It does this by following the Actor model.
Inter-process communication works via a shared-nothing asynchronous message passing system: every process has a "mailbox" -- a queue of messages that have been sent by other processes and not yet consumed. A process uses the receive primitive to retrieve messages that match desired patterns. A message-handling routine tests messages in turn against each pattern, until one of them matches. When the message is consumed and removed from the mailbox the process resumes execution. A message may comprise any Erlang structure, including primitives (integers, floats, characters, atoms), tuples, lists, and functions.
The following code creates a new process and invokes the function web:start_server(Port, MaxConnections).
We can then send an asynchronous message to the ServerProcess. The message in the example below consists of a tuple with the atom "pause" and the number "10".
Finally, we can define how to receive messages that are sent to the process:
There are several advantages to this model. Because there is no shared data, is no need to control access. The message that passed to an actor is immutable.
A Closer Look at Clojure
To illustrate the differences between a language that relies on locks, and a language that relies on STM, consider the following two examples in Java and Clojure. Both programs create a vector of integers and use multiple threads to iteratively increment each item in the vector, which creates extreme contention. The Clojure example returns the correct result because it executes within a transaction. This allows it to protect access to the vector of integers.
The Java example, however, does not have a way to protect access to the vector of integers. So the Java program will yield different results each time it is executed.
The problem with the Java example is that it does not control the critical section in which the program reads a value from the “refs” vector and updates it (line 19). The only mechanism Java provides for protecting a critical section is a lock. However, a lock around line 19 would not be sufficient if other operations had access to the “refs” vector. Thus, we would need a more complicated locking scheme. However, the “dosync” form in the Clojure example provides sufficient means to protect the critical section no matter what the circumstances.
The advantage of having an STM in Clojure and Haskell is that the STM simplifies the understanding of concurrent programs and helps make them more maintainable. It does this by seamlessly integrating itself into the existing high-level abstractions of the language – such as modules and objects [Cascaval 2008]. A disadvantage of STM, however, is the need to abort failed transactions. This means that transactions cannot perform any operation that cannot be undone – such as most I/O.
Conclusion
Java provides sufficient mechanisms to accomplish concurrent programming. But its implementation is difficult to understand, and makes it easy for a programmer to introduce bugs. Clojure, Haskell and Erlang provide a more structured environment for concurrent programming, making it less likely that a programmer will introduce a bug. This is due to immutability and STM in the case of Clojure and Haskell. But it is due to the Actor model in the case of Erlang.
It is important that a concurrency model allow the programmer to maintain an internal understanding of the program. An internal understanding means that the programmer does not need to watch the program execute in order to predicate what it will do. This is similar to the "independent coordinate system" that Dijkstra favored in his GOTO Considered Harmful letter.
Clojure, Haskell and Erlang provide models that lead to programs that can be understood with less difficult than the locking model of Java (and other mainstream languages).
References
CASCAVAL, C. BLUNDELL, C. MAGED, M. CAIN, H. W. WU, P. CHIRAS, S. CHATTERJEE, S., 2008. Software Transactional Memory: Why is it only a Reasearch Toy? ACM Queue, October 24, 2008.
GOETZ, B., 2006. Java Concurrency in Practice. Addison-Wesley Professional (May 19, 2006).
HARRIS, T. MARLOW, S. JONES, S. P. 2005. Composable Memory Transactions. In ACM Symposium on Principles and Practice of Parallel Programming 2005 (PPoPP'05).
HOLLOWAY, S., 2008. Programming Clojure. Pragmatic Bookshelf (May 21, 2009).
JONES, S. P. GORDON, A. FINNE, S., 1996. Concurrent Haskell. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (PoPL).
LISKOV, B. GUTTAG, J. 2001. Program Development in Java, Addison-Wesley (2001).
MÄNTYLÄ, LASSENIUS. 2008. What types of defects are really discovered in code reviews. In IEEE Transactions on Software Engineering, pp. 430-448.
posted by Joe Kutner at 1:34 PM
0 Comments:
Post a Comment
<< Home