Reagents.jl
Reagents.jl is still work-in-progress.
Reagents
— ModuleReagents.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))
nothing
# output
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
nothing
# output
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)()
nothing
# output
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
nothing
# output
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