Chocola

Chocola is a programming language made for concurrency and parallelism.

It provides three concurrency models:

  1. futures for deterministic parallelism,
  2. actors for message passing, and
  3. transactions to manage shared memory.

We believe typical applications can benefit from using different concurrency models, in each component using whichever model fits best. The unique thing about Chocola is that it allows its three concurrency models to be combined, while maintaining the expected properties of each.

Chocola is an extension of Clojure, a dialect of Lisp that runs on the Java Virtual Machine. It’s open source and was developed as a research artifact during my PhD.

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 in the following papers:

  1. Chocola: Composable Concurrency Language

    In TOPLAS, January 2021
    This is the most complete paper presenting all details of Chocola. We first describe the three constituent models of Chocola – futures, transactions, and actors – and their guarantees. Next, for each pairwise combination, we study which guarantees are broken in a naive combination and ‘fix’ these. This is then unified as Chocola. We briefly describe its implementation in Clojure, and we use three benchmark applications to demonstrate that Chocola can improve their performance for relatively little developer effort. The paper also contains a full formal description of Chocola's semantics and proofs of its guarantees.
    View on the ACM website

  2. Chocola: Integrating Futures, Actors, and Transactions

    At AGERE (at SPLASH), November 2018
    This is an earlier paper presenting Chocola; quite a bit shorter than the one above (and therefore maybe easier to get started with). 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

  3. 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

  4. 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

  5. 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.