Automated Debugging with Tractable Probabilistic Programming

Probabilistic programming languages allow domain experts to specify generative models in a high-level language, and reason about those models using domain-independent algorithms. Given an input, a probabilistic program generates a distribution over outputs. In this work, we instead use probabilistic programming to explicitly reason about the distribution over programs, rather than outputs. We propose Tractable Probabilistic Programs (TPP), a language to represent rich probabilistic dependencies between different parts of a program; we make use of the recent work on sum-product networks to ensure that inference remains tractable. We explain how TPP can be applied to the problem of automated program debugging; given a corpus of buggy programs, a TPP model can be learned to capture a probability distribution over the location of the bug. The model can also incorporate additional sources of information, such as coverage statistics on test suites. We also briefly outline how TPP can be used to solve the more ambitious problem of fault correction, i.e. predicting the most probable true program conditioned on a buggy one. The ability to learn common patterns of bugs and incorporate multiple sources of information potentially makes TPP useful as a unifying framework for automated program debugging.