Reagents.jl: Towards composable and extensible nonblocking programming for Julia
Reagents.jl implements reagents (Turon, 2012) which provides higher-order concurrency primitives for expressing nonblocking algorithms and concurrent synchronizations in a composable manner.
For example, op1 | op2
is the combinator that combines the "lazy"
representation of operations (called reagents) and expresses that only one of
the operations take place. This is similar to Go's select
statement on
channels (Ref:
specification) but Reagents.jl
has other combinators and is extensible to any user-defined data structures.
Note: 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.
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, 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