Reagents.jl: Towards composable and extensible nonblocking programming for Julia

Reagents.jl implements and extends reagents by Turon (2012). It provides higher-order concurrency primitives for expressing nonblocking¹ algorithms and synchronizations of concurrent tasks in a composable manner.

For example, op1 | op2 is the choice combinator that combines the "lazy" representation of operations (called reagents) and expresses that only one of the operations take place. This is similar to the select statement popularized by Go as a mechanism for expressing rich concurrency patterns. This is a form of the selective communication that is implemented by numerous other languages (and libraries) such as Erlang (receive expression), occam (ALT statement), and Concurrent ML² (select expression), to name a few. However, unlike Go that only supports synchronization of channels in select³ or Erlang that only supports selecting incoming messages, Reagents.jl's choice combinator supports arbitrary user-defined data structures. Furthermore, it provides other combinators such as ⨟ and & for declaring atomicity of the operations, similar to the software transactional memory mechanism.

Reagents.jl is a foundation of Julio.jl, an implementation of structured concurrency for Julia. For supporting this, Reagents.jl extends the original description of reagents (Turon, 2012) by adding more primitives such as WithNack from Concurrent ML (which is a natural extension due to the influence of Concurrent ML on reagents, as Turon (2012) noted).

---

¹ Due to the simplistic implementation of the k-CAS, Reagents.jl is not yet nonblocking in the strict sense. However, as discussed in Turon (2012), it should be straightforward to switch to a k-CAS algorithm with more strict guarantee.

² This includes other languages such as Racket and GNU Guile that implemented the Concurrent ML primitives.

³ But perhaps for good reasons for Go.

Example: Treiber stack

Let us implement Treiber stack which can be represented as an atomic reference to an immutable list:

using Reagents

struct Node{T}
    head::T
    tail::Union{Node{T},Nothing}
end

const List{T} = Union{Node{T},Nothing}

struct TreiberStack{T,Ref<:Reagents.Ref{List{T}}}
    head::Ref
end

TreiberStack{T}() where {T} = TreiberStack(Reagents.Ref{List{T}}(nothing))

The push and pop operations can be expressed as reagents:

pushing(stack::TreiberStack) =
    Reagents.Update((xs, x) -> (Node(x, xs), nothing), stack.head)

popping(stack::TreiberStack) =
    Reagents.Update(stack.head) do xs, _
        if xs === nothing
            return (nothing, nothing)
        else
            return (xs.tail, xs.head)
        end
    end

The execution ("reaction") of the reagent can be invoked by just calling the reagent object. So, it's straightforward to wrap it in the standard function API:

Base.push!(stack::TreiberStack, value) = pushing(stack)(value)
Base.pop!(stack::TreiberStack) = popping(stack)()

These user-defined reagents can be composed just like pre-defined reagents. For example, we can move an element from one stack to another by using the sequencing combinator ⨟:

s1 = TreiberStack{Int}()
s2 = TreiberStack{Int}()
push!(s1, 1)
(popping(s1) ⨟ pushing(s2))()
@assert pop!(s2) == 1

Here, the element in the stack s1 is popped and then pushed to the stack s2 atomically. Similar code works with arbitrary pair of containers, possibly of different types.

For more examples, read the documentation or see the examples directory.

Resources

• Turon, Aaron. 2012. “Reagents: Expressing and Composing Fine-Grained Concurrency.” In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, 157–168. PLDI ’12. New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/2254064.2254084.

• The original implementation by Turon (2012): https://github.com/aturon/ChemistrySet

• Sivaramakrishnan, KC, and Théo Laurent. “Lock-Free Programming for the Masses,” https://kcsrk.info/papers/reagents_ocaml16.pdf

• LDN Functionals #8 KC Sivaramakrishnan: OCaml multicore and programming with Reagents - YouTube

• Reagent implementation for OCaml: https://github.com/ocaml-multicore/reagents