Exact Recursive Probabilistic Programming

Recursive calls over recursive data are useful for generating probability distributions, and probabilistic programming allows computations over these distributions to be expressed in a modular and intuitive way. Exact inference is also useful, but unfortunately, existing probabilistic programming la...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of ACM on programming languages 2023-04, Vol.7 (OOPSLA1), p.665-695, Article 98
Main Authors: Chiang, David, McDonald, Colin, Shan, Chung-chieh
Format: Article
Language:English
Subjects:
Formal language definitions
Mathematics of computing
Probability and statistics
Recursion
Software and its engineering
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recursive calls over recursive data are useful for generating probability distributions, and probabilistic programming allows computations over these distributions to be expressed in a modular and intuitive way. Exact inference is also useful, but unfortunately, existing probabilistic programming languages do not perform exact inference on recursive calls over recursive data, forcing programmers to code many applications manually. We introduce a probabilistic language in which a wide variety of recursion can be expressed naturally, and inference carried out exactly. For instance, probabilistic pushdown automata and their generalizations are easy to express, and polynomial-time parsing algorithms for them are derived automatically. We eliminate recursive data types using program transformations related to defunctionalization and refunctionalization. These transformations are assured correct by a linear type system, and a successful choice of transformations, if there is one, is guaranteed to be found by a greedy algorithm.
ISSN:2475-1421
2475-1421
DOI:10.1145/3586050