Hi. I have reached some kind of local optimum in my coroutine journey so it’s time to freeze the API and bundle the first production release of
cloroutine. Compared to the previous alpha release, the API has been simplified and the implementation doesn’t rely on
core.async anymore, for reasons detailed below.
I’ve identified 3 major categories of problems that may benefit from this programming style and written a howto for each one (see the guides section in the readme). I’m pretty sure the list is not exhaustive but those are the ones matching common clojure patterns.
- generators : the example relies on lazy sequences as it’s pretty straightforward to do so, but it could be easily extended to the fast-path reduce protocols to improve performance.
- asynchronous processes : I chose a future-based example as this style is quite trendy these days but the technique is really transposable to many other concurrency primitives. I dogfooded it in implementation of
missionary's sequential processes (task-based) and made a POC for an implementation of
core.async's go blocks (channel-based).
- transducers : the idea to leverage coroutines to define transducers is not mine but I still found interesting to compare my implementation to the original.
Coroutine-based programming involves two kinds of state :
- accidental state : when the process must be suspended, most of the time the stack is not empty and needs to be moved on the heap in order to survive until the process is resumed, at which point it must be moved back on the stack. Keeping track of this state is the value proposition of
- incidental state : coroutine-based programming is a form of imperative programming, when a function call is split into a suspend part and a resume part it’s very likely that the suspend action will perform some effect and the resume action will somehow depend on this effect. The state associated with this effect is business-related.
core.async IOC machinery is painful to use because it stores both kinds of state in the same object, requiring a basic understanding of its internals. My first attempt to decouple this state consisted of passing suspend and resume code to the
cr macro, which would then rewrite breaking var calls into inlined suspend code followed by inlined resume code. Inlined code was supposed to close over incidental state. This strategy happened to work quite well but was a bit clumsy to work with, mostly because writing stateful stuff in clojure makes ugly code.
It turned out relying on thread-local state was a more elegant solution, given coroutines provide strong guarantees to run synchronously in the caller thread. So the final
cr API simply takes a map of suspend vars to resume vars and introduces a break on suspend var calls, scheduling the resume var call for the next iteration. Breaking var functions are expected to handle incidental state via thread-local context set up around the coroutine call.
I decided to roll my own implementation for various reasons. Since the beginning, I was reluctant with the idea of relying on
core.async's IOC machinery because this is an implementation detail, not easily customizable as some helpers are namespace-private, and there’s no commitment for a stable API. More importantly, a significant amount of defects have been known for a long time and still don’t show any sign of being addressed, and the overall pace of maintenance activity is currently too low for my quality standards. On the technical side, the current design suffers from several flaws making it obvious to me that a major rewrite will eventually become unavoidable. Related issues include :
- exception handling story is still incomplete, showing wrong behavior in some nontrivial cases (ASYNC-220).
letfnbody rewriting is not supported althought it is technically possible to implement (ASYNC-221).
- locals clearing seems not to have been considered (ASYNC-219, ASYNC-223)
On the personal side, the spiritual pleasure of compiler design is a reward in itself, largely worth the effort.
core.async legacy is still visible in the overall strategy with the heavy usage of SSA intermediate representation. It happens to works very well for this particular problem, and most of the improvements were allowed by having this proper structure as plain data through the entire compiler pipeline, performing the following passes :
- AST analysis
- SSA construction
- variable lifespan trace
- variable slot assignment
- code emission
The AST analysis is performed by
clojure.tools.analyzer.jvm for JVM Clojure and
cljs.analyzer.api for ClojureScript.
The SSA construction is performed quite similarly to
core.async, except the entire tree is walked. When an asynchronous form is encountered (e.g a fn body), it is walked as well to keep track of closed over locals, a necessary information to perform locals clearing. Another difference is that exception handling is a first-class citizen, represented as edges in the block graph just like regular branching jumps.
The variable lifespan trace is a pass walking the block graph in the past for each variable read and marking this variable in each walked block until the creator block is encountered. That way we know for each block which variable need to be kept stored.
The variable slot assignment pass looks at variable lifespan overlaps and gives slot indices to each such that overlapping variables have different slots, using a basic graph coloring strategy. That way, no more slots than necessary need to be allocated, improving memory footprint.
The code emission generates clojure code, mapping ssa blocks to functions. A plain array is instanciated to store variables and current running block. Each time a block transition happens, variables not needed anymore in the target block are niled in the array, effectively clearing locals. A loop ensures blocks are run until suspended or terminated state is reached, and the whole stuff is wrapped in a zero-arg function.
This is my first non-toy compiler tech project, and giving birth to this was a very exciting experience. I hope you will find it useful, and of course I’m highly interested in feedbacks of any kind. Special thanks to Tim Baldridge for its initial design inspiration, I probably wouldn’t even have started without it. Thanks to Jean Niklas L’orange for its work on transducers and conduits, very inspiring as well.