Indiana University Bloomington

Luddy School of Informatics, Computing, and Engineering

Technical Report TR719:
Simplifying Probabilistic Programs Using Computer Algebra

Jacques Carette and Chung-chieh Shan
(Sep 2015), 17 pages
[A slightly abbreviated version of this paper is being submitted to PADL 2016.]
We transform probabilistic programs to run more efficiently and read more easily, by composing three semantics-preserving transformations: (1) apply the denotational semantics; (2) improve the resulting integral; then (3) invert the denotational semantics. Whereas step 1 is a straightforward transformation from monadic to continuation-passing style, the rest builds on computer algebra: step 2 reorders and performs integrals, and step 3 represents density functions as differential operators.

Available as: