Probabilistic modeling and reasoning are central tasks in artificial intelligence and machine learning. A probabilistic model is a rough description of the world: the model-builder attempts to capture as much detail about the world’s complexities as she can, and when no more detail can be given the rest is left as probabilistic uncertainty. Once constructed, the goal of a model is to perform automated inference: compute the probability that some particular fact is true about the world. It is natural for the model-builder to want a flexible expressive language – the world is a complex thing to describe – and over time this has led to a trend of increasingly powerful modeling languages. This trend is taken to its apex by probabilistic programming languages (PPLs), which enable modelers to specify probabilistic models using the facilities of a full programming language. However, this expressivity comes at a cost: the computational cost of inference is in direct tension with the flexibility of the modeling language, and so it becomes increasingly difficult to design automated inference algorithms that scale to the kinds of systems that model builders want to create.

This thesis focuses on the central question: how can we design effective probabilistic programming languages that profitably trade-off expressivity and tractability for inference? The approach taken here is first to identify and exploit important structure that a probabilistic program may possess. The kinds of structure considered here are discrete program structure and symmetry. Programs are heterogeneous objects, so different parts of programs may exhibit different kinds of structure; in the second part of the thesis I show how to decompose heterogeneous probabilistic program inference using a notion of program abstraction. These contributions enable new applications of probabilistic programs in domains such as text analysis, verification of probabilistic systems, and classical simulation of quantum algorithms.

Abstraction is a fundamental tool for reasoning about a complex system. Program abstraction has been utilized to great effect for analyzing deterministic programs. At the heart of a program abstraction is a connection between the abstract program, which is simple to analyze, and the concrete program, which may be extremely complex. Program abstractions, however, are typically not probabilistic. In this thesis I generalize a particular class of non- deterministic program abstractions known as sound over-approximations to the probabilistic context. Sound over-approximations are a family of abstract programs which are guaranteed to contain the original program as a subset of their behavior. This thesis shows that when imbued with a probabilistic semantics, sound over-approximations define a family of probabilistic programs which capture key properties of the original program. It then introduces a mechanism for generating sound probabilistic over-approximations as a generalization of a well-known program abstraction technique known as predicate abstraction. Finally, the problem of inference and learning in the context of probabilistic program abstractions are briefly described.