Parallel traversal effect handlers for OCaml

This is an idea proposed in 2000 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 traverse handler 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