IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2023 > Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning

Alexander Bagnall

Wednesday, May 31, 2023

3:00pm Zoom3 - https://zoom.us/j/3911012202 (pass: @s3)

Alexander Bagnall, PhD Researcher, Ohio University, USA

Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning

Abstract:

In this talk, we give a brief introduction to probabilistic programming and present Zar: a formally verified compiler pipeline from discrete probabilistic programs with unbounded loops in the conditional probabilistic guarded command language (cpGCL) to proved-correct executable samplers in the random bit model. We exploit the key idea that all discrete probability distributions can be reduced to unbiased coin-flipping schemes. The compiler pipeline first translates cpGCL programs into choice-fix trees, an intermediate representation suitable for reduction of biased probabilistic choices. Choice-fix trees are then translated to coinductive interaction trees for execution within the random bit model. The correctness of the composed translations establishes the sampling equidistribution theorem: compiled samplers are correct wrt. the conditional weakest pre-expectation semantics of cpGCL source programs. Zar is implemented and fully verified in the Coq proof assistant.