  Inference algorithms for probabilistic programming are complex imperative
programs with many moving parts. Efficient inference often requires customising
an algorithm to a particular probabilistic model or problem, sometimes called
inference programming. Most inference frameworks are implemented in languages
that lack a disciplined approach to side effects, which can result in
monolithic implementations where the structure of the algorithms is obscured
and inference programming is hard. Functional programming with typed effects
offers a more structured and modular foundation for programmable inference,
with monad transformers being the primary structuring mechanism explored to
date.
  This paper presents an alternative approach to inference programming based on
algebraic effects. Using effect signatures to specify the key operations of the
algorithms, and effect handlers to modularly interpret those operations for
specific variants, we develop two abstract algorithms, or inference patterns,
representing two important classes of inference: Metropolis-Hastings and
particle filtering. We show how our approach reveals the algorithms' high-level
structure, and makes it easy to tailor and recombine their parts into new
variants. We implement the two inference patterns as a Haskell library, and
discuss the pros and cons of algebraic effects vis-a-vis monad transformers as
a structuring mechanism for modular imperative algorithm design.
