Chocola

Examples

1. Futures

   (defn pmap [f xs]
     (let [futs (map
                  (fn [x] (fork (f x)))
                  xs)]
       (map
         (fn [fut] (join fut))
         futs)))

   pmap implements a parallel map. First, we fork a new future for each element in the list, which computes (f x) in parallel. Next, all results are joined and returned.

2. Transactions

   (def checking (ref 150))
   (def savings  (ref 500))
   
   (defn transfer [from to amount]
     (atomic
       (ref-set from (- @from amount))
       (ref-set to   (+ @to   amount))))
   
   (transfer checking savings 100)

   In this example, checking and savings are two bank accounts stored in transactional variables (ref). atomic encapsulates a transaction that transfers $100 from the checking to the savings account.

3. Transactions + Futures

   (def my-accounts [(ref 150) (ref 500) (ref 30)])
   
   (defn add-interest [accounts pct]
     (atomic
       (pmap
         (fn [acc] (ref-set acc (* @acc pct)))
         accounts)))
   
   (add-interest my-accounts 1.01)

   This example adds 1% interest to each of my bank accounts. We use the pmap function of the first example to do this in parallel. Chocola guarantees that this does what you expect.

4. Actors

   (def interface
     (behavior [id accounts]
       [:print-accounts]
         (println "Customer " id
           " has: " accounts)
       [:add-account account]
         (become :same
           id (cons account accounts))))
   
   (def my-actor (spawn interface 1 []))
   (send my-actor :add-account 500)
   (send my-actor :print-accounts)
   ; => Customer 1 has: [500]

   This example uses actors. behavior defines the interface of an actor. This consists of the actor’s internal state (here an id and list of accounts) and its reaction to messages: a list of patterns and the code to execute. An actor can read its internal state and the data passed in the message (extracted using pattern matching). It can modify its behavior and internal state using become (here the interface stays the same but the state changes).

   The example spawns one actor and sends two messages, to add a bank account and print all accounts.

5. Actors + Transactions + Futures

   (def interface
     (behavior [id accounts]
       [:transfer from to amount]
         (transfer from to amount)
       [:add-interest]
         (add-interest accounts 1.01))
   
   (def checking (ref 150))
   (def savings  (ref 500))
   (def my-accounts [checking savings])
   (def my-actor
     (spawn interface 1 my-accounts))
   (send my-actor :add-interest)

   In this example, all three concurrency models are combined. We create one actor and send it a message to calculate the interest. In the actor, a transaction is started, and in this transaction, several futures are created. This demonstrates Chocola’s ability to freely use and combine whichever concurrency model suits the problem.

Download

We have implemented Chocola as an extension of Clojure. It can be downloaded on GitHub.

It can easily be included in existing Clojure projects that use Leiningen: by injecting Chocola in the project's project.clj, Clojure will be patched on start up with Chocola's modifications. This is decribed in more detail in the README file.

Chocola is released under the Eclipse Public License (same as Clojure).

Publications

You can find a complete description of Chocola in my PhD thesis. It describes the motivation behind Chocola, the semantics of each of its parts, a formalization of its semantics, some details on its implementation, and the benchmark applications we used to evaluate it.

We also published about (the ideas behind) Chocola at academic conferences, in the following papers:

1. Chocola: Integrating Futures, Actors, and Transactions

   At AGERE (at SPLASH), November 2018

   This paper presents Chocola. It builds upon our previous work to unify futures, actors, and transactions in one framework. We first describe the guarantees of each separate model. Next, for each pairwise combination, we study which guarantees are broken in a naive combination and describe how these can be maintained in our modified semantics. Finally, we unify these modified semantics in Chocola. We also present its implementation in Clojure.

   Download paper

2. Transactional Tasks: Parallelism in Software Transactions

   At ECOOP, July 2016

   This paper studies the combination of futures and transactions. It introduces transactional futures: a construct that allows futures to be created in a transaction. They make it possible to exploit the parallelism inside a transaction, while providing safe access to the state of their encapsulating transaction. Transactional futures maintain serializability and do not introduce non-determinism. We also demonstrate that introducing transactional futures can improve performance.

   Download paper

3. Transactional Actors: Communication in Transactions

   At SEPS (at SPLASH), October 2017

   This paper the combination of combination of actors and transactions, resulting in transactional actors. By using transactions in an actor, memory can be shared safely between actors. By using the actor model in a transaction, transactions can communicate. Hence, transactional actors combine transactions and actors while maintaining their properties.

   Download paper

4. Towards Composable Concurrency Abstractions

   At PLACES (at ETAPS), April 2014

   This paper is a case study of the combinations of the six concurrency models supported by Clojure. We study all pairwise combinations of these models, noting which ones compose without issues and which don’t. This motivated the creation of Chocola.

   Download paper

Applications

We have used Chocola to create three example applications. These are applications from STAMP, a benchmark suite of applications that use transactions (paper). We modified these applications to show that better performance can be achieved by combining transactions with either futures or actors.

1. Vacation2

   vacation2 is a simulated reservation system for hotels, flights, and rental cars. It uses actors to process several customers in parallel, and transactions to manage the shared data (hotels, flights, and car reservations).

   GitHub repository

2. Labyrinth

   The Labyrinth application simulates the placement of electrical wires between transistors on a computer chip. This is a bit like searching for paths through a “labyrinth”, but the electrical wires between the transistors should not overlap. Several threads search for paths at the same time, and write their result to transactional memory. Using transactions ensures paths do not overlap. However, inside each transaction there’ a search algorithm that can also be parallelized. We use futures in the transaction to improve the performance of this application.

   GitHub repository

3. Bayes

   The Bayes benchmark implements an algorithm that learns the structure of a “Bayesian network”. This network is a graph, in which a node can be accessed by multiple threads. Hence, each node is stored as a transactional variable, and modifications to the graph occur in a transaction. Sometimes, this requires expensive computations, which can be parallelized using futures. Thus, this application benefits from better performance by combining futures and transactions.

   GitHub repository

PLT Redex

We created an executable implementation of parts of the operational semantics of Chocola using PLT Redex. You can download it on GitHub.

Background

Chocola was developed by Janwillem Swalens at the Software Languages Lab of Vrije Universiteit Brussel, in Belgium.

The name Chocola is based on “composable concurrent language” and an extra h just because I like chocolate.