Parallel traversal effect handlers for OCaml
This is an idea proposed in 2024 as a Cambridge Computer Science Part II project, and has been completed by Sky Batchelor. It was co-supervised with Patrick Ferris.
Most existing uses of effect handlers perform synchronous execution of handled
effects. Xie et al proposed a traverse handler for parallelisation of
independent effectful computations whose effect handlers are outside the
parallel part of the program. The paper [1] gives a sample implementation as a
Haskell library with an associated λp calculus that formalises the parallel
handlers.
This project aims to:
- implement the
traversehandler in OCaml 5, using single-shot handlers [2] - identify a selection of parallel-friendly data structures that might benefit from such parallel traversals
- investigate handlers for alternative traversal strategies beyond the folds support by
traverse - evaluate the performance of such parallel handlers, for instance using Eio's
Domain_pool[3] on a many core machine (ranging from 8--128 cores)
Sky Batchelor successfully built a traverse handler for their Part II project and submitted it succcessfully in June 2025! A copy of the dissertation is available on request, and we're working on getting the dissertation and code online.
Related reading
-
Parallel Algebraic Effect Handlers describes the
↩︎︎traverseeffect -
Retrofitting effect handlers onto OCaml, PLDI 2021 describes how the effect system in OCaml works.
↩︎︎ -
EIO is a high-performance direct-style IO library we have been developing for OCaml.
↩︎︎
ideas