CAREER : Filling In the Design Landscape of Probabilistic Programming Languages

Probabilistic behavior is pervasive in computing, so it is critical that we have tools for reasoning about it in our programs. Probabilistic programming languages (PPLs) address this need by enriching programming languages with probabilistic semantics, enabling applications in software verification and artificial intelligence that rely on reasoning about the uncertain behavior. The challenge is scalability: probabilistic inference is computationally hard, even for very restricted programming languages. However, scaling inference is not hopeless: its inherent hardness can be tamed by careful language design. There are special PPLs, called tractable probabilistic models, for which inference is computationally easy. Unfortunately, tractable probabilistic models are too low-level to ergonomically program in. The goal of this project is to bridge the gap between high-level ergonomic languages and low-level tractable languages. This project's novelty is a new compiler-oriented approach to designing and implementing PPLs: the team will (1) develop new high-level ergonomic PPLs that compile to low-level tractable probabilistic models; (2) develop new compilation targets that enable scalable probabilistic inference for richer classes of programs; and (3) create new PPLs for teaching probability to broad audiences. This project's impact is a new generation of scalable, reliable, and usable PPLs, enabling new applications in software verification and artificial intelligence. To achieve these goals, the project will fill in the design landscape for probabilistic programming language design and implementation. The key tradeoff in designing a PPL is between tractability and expressivity of the language. More tractable languages afford efficient and scalable inference strategies but are not easy to program in. More expressive languages have ergonomic programming features like loops, data structures, and modules, but these features make performing inference hard. The project's first research thrust will develop and grow a new expressive compiled PPL that supports a significant subset of the Racket programming language. The project's second thrust will use type systems to develop new tractable probabilistic programming languages that ensure high-performance Markov-Chain Monte-Carlo sampling with guarantees on mixing times. The project's final thrust will develop a sequence of increasingly rich PPLs for teaching probability to broad audiences. The project's education plan will enable (1) a new pedagogy for teaching probability using probabilistic programs; and (2) new courses on probabilistic programming. The project's broader impacts are (1) development of new educational tools for teaching probability to broad audiences; (2) technology transfer of probabilistic programming tools and techniques into industry and government; and (3) empowering a broader set of developers to create machine learning models. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.