一句话：提出 Roulette，首个兼具高性能精确推断与通用语言特性的离散概率编程语言。
高风险或验证场景要求概率程序支持精确推断，但高性能精确推断引擎难以实现，导致现有精确概率编程语言功能受限。Roulette 是首个兼顾高性能精确推断与通用语言特性的离散概率编程语言。其核心洞见是精确概率推断与 Rosette 符号求值策略紧密相关，故通过扩展 Rosette 求解器辅助系统处理概率量。Roulette 支持 Racket 的较大子集，包括数据结构、一等函数、必终止递归、可变状态、模块与宏，以及有限离散随机变量、条件化和顶层推断。作者将 Rosette 正确性证明推广到概率情形以证明 Roulette 可靠，并在示例上展示可扩展性与表达力。
Exact probabilistic inference is a requirement for many applications of probabilistic programming languages (PPLs) such as in high-consequence settings or verification. However, designing and implementing a PPL with scalable high-performance exact inference is difficult: exact inference engines, much like SAT solvers, are intricate low-level programs that are hard to implement. Due to this implementation challenge, PPLs that support scalable exact inference are restrictive and lack many features of general-purpose languages. This paper presents Roulette, the first discrete probabilistic programming language that combines high-performance exact inference with general-purpose language features. Roulette supports a significant subset of Racket, including data structures, first-class functions, surely-terminating recursion, mutable state, modules, and macros, along with probabilistic features such as finitely supported discrete random variables, conditioning, and top-level inference. The key insight is that there is a close connection between exact probabilistic inference and the symbolic evaluation strategy of Rosette. Building on this connection, Roulette generalizes and extends the Rosette solver-aided programming system to reason about probabilistic rather than symbolic quantities. We prove Roulette sound by generalizing a proof of correctness for Rosette to handle probabilities, and demonstrate its scalability and expressivity on a number of examples.
@article{paperbot3118,
title = {Roulette: A Language for Expressive, Exact, and Efficient Discrete Probabilistic Programming},
author = {Cameron Moy and Jack Czenszak and John M. Li and Brianna Marshall and Steven Holtzen},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729334}
}