Imp

Imprecise probabilistic programming via BDDs in Haskell.

Imp is a domain-specific language for discrete probabilistic programs with Knightian uncertainty, where some probabilities are not precisely known. Programs compile to binary decision diagrams (BDDs) for inference via weighted model counting.

Unlike standard probabilistic programming, Imp computes credal sets. These are convex sets of distributions that capture all possibilities consistent with the specified uncertainty, enabling reasoning under ambiguity in settings like decision-making, planning, and robust inference.

Key ideas

Quick start

{-# LANGUAGE DataKinds, QualifiedDo, RebindableSyntax, TypeApplications #-}
import Imp

data Ball = Red | Black | Yellow deriving (Eq, Ord, Show)

-- Ellsberg's urn: 30 red, 60 either black or yellow
ellsberg :: Imp '["split"] Ball
ellsberg = Imp.do
  isRed   <- flip (1/3)
  isBlack <- interval @"split" 0.0 1.0
  Imp.return $ if isRed then Red
               else if isBlack then Black
               else Yellow

Running inference

-- Per-value marginal bounds (exact enumeration)
marginal ellsberg
-- fromList [(Red,(0.333,0.333)),(Black,(0.0,0.667)),(Yellow,(0.0,0.667))]

-- Lower/upper probability of an event
intervalProbability ellsberg (== Red)
-- (0.333, 0.333)

intervalProbability ellsberg (\b -> b == Red || b == Yellow)
-- (0.333, 1.0)

Precise marginals can be calculated for programs with no Knightian uncertainty:

fairCoin :: Imp '[] Bool
fairCoin = flip 0.5

preciseMarginal fairCoin
-- fromList [(False,0.5),(True,0.5)]

Building and running

Requires GHC 9.10+ and Cabal. Add imp-ppl to build-depends, then import Imp.

# Build the library
cabal build

# Run the test suite
cabal test

# Dev tooling below (requires the `dev` flag)

# Benchmarks (each emits CSV to stdout: N,method,time_s):
cabal run -f dev bench-ellsberg  # n-way Ellsberg, N = 2..15
cabal run -f dev bench-robot     # n-step robot IMDP, N = 1..8

# Visualization tool (generates index.html with credal set plots and BDD diagrams)
cabal run -f dev viz
open index.html

Modules

GHC extensions

Users need only four pragmas plus one import:

{-# LANGUAGE DataKinds, QualifiedDo, RebindableSyntax, TypeApplications #-}
import Imp

The single import provides both unqualified access (DSL combinators, ifThenElse for RebindableSyntax, and the inference API) and the Imp. qualifier that QualifiedDo desugaring uses (Imp.do, Imp.return). RebindableSyntax also rebinds ordinary monadic do, so put driver code in a separate module importing Imp.Inference (not Imp, which shadows return, flip, and fmap), or keep one module and use import qualified Prelude as P with P.do for IO.

Internally, the library uses DataKinds, DerivingStrategies, GADTs, and TypeFamilies as cabal default-extensions, plus per-file UndecidableInstances and AllowAmbiguousTypes where needed.

Main features

Probabilistic and Knightian choices

flip p creates a coin flip that returns True with probability p. knight @"name" creates a Knightian binary choice returning True with unknown probability. interval @"name" lo hi is shorthand for a Bernoulli with unknown probability in [lo, hi].

Conditioning

observe conditions on a Boolean being True:

conditioned :: Imp '["bias"] Bool
conditioned = Imp.do
  biased <- interval @"bias" 0.3 0.7
  observe biased
  Imp.return biased

Tagging and iteration

tag @"name" scopes all Knightian choices in a subprogram under a tag, enabling reuse. Combinators like foldN, scanN, and foldMN iterate over numbered tags for multi-step models:

-- Robot taking 5 steps with interval transition probabilities
trajectory :: Imp '["step1.d", "step2.d", "step3.d", "step4.d", "step5.d"] [Position]
trajectory = scanN @5 @"step" dynamics startPos step

Inference modes

Where k = number of Knightian variables.

Examples

See Imp.Examples.* for worked examples:

• Basic: simple coin flips
• Ellsberg: the classic ambiguity-aversion paradox (30 red, 60 black/yellow unknown split)
• Knightian: dependent/independent showing how Knightian names control correlation
• IMDP: robot navigation on a line with interval transition probabilities, including compositional reuse via tag
• Iteration: random walks using intervalMap
• MontyHall: Monty Hall problem with Knightian host bias
• Polytope: composed interval choices forming higher-dimensional credal sets
• TwoChild: an imprecise variant of the two-child problem, demonstrating observe

Accompanying paper

The library accompanies the paper Imprecise Probabilistic Programming, Precisely (Functional Pearl) (to appear). The corresponding code is tagged icfp2026. The current version differs from the paper as follows.