Imprecise Probabilistic Programming, Precisely: Credal Sets via Graded Monads, BDDs, and Semiring-Parametric Inference (Functional Pearl)
For developers of probabilistic programming languages, this provides a principled and practical way to incorporate imprecise probability without changing the core inference pipeline.
The paper shows that imprecise probability (convex sets of distributions) can be handled by the standard BDD compilation and weighted model counting pipeline used in discrete probabilistic programming, by leaving weights free. They introduce Imp, a Haskell-embedded DSL with a graded monad for commutativity and semiring-parametric inference, supporting exact, differentiable, and interval-bounded inference.
Imprecise probability generalizes standard probability theory by replacing a single distribution with a convex set of possible distributions. We show that this generalization requires no change to the standard BDD compilation and weighted model counting pipeline used by discrete probabilistic languages. An imprecise coin flip is simply a BDD variable whose weight is left free rather than fixed. We introduce Imp, a Haskell-embedded DSL for imprecise probabilistic programming. A graded monad, indexed by finite sets of named sources of epistemic uncertainty, restores the commutativity that the standard convex powerset monad lacks, and GHC's type system enforces this at compile time. Weighted model counting is parametric in the semiring, so the same compiled BDD supports exact, differentiable, and interval-bounded inference.