一句话：提出一种概率编程语言，可自然表达递归数据上的递归，并通过类型保证的程序变换实现精确推断。
概率编程便于模块化地描述概率分布，但现有语言无法对递归数据上的递归调用进行精确推断，迫使程序员手工实现许多应用。本文提出一种概率编程语言，可自然表达多种递归，并执行精确推断。其核心是用与去函数化和再函数化相关的程序变换消除递归数据类型；线性类型系统保证变换正确，且若存在可行变换序列，贪心算法保证找到。实例上，概率下推自动机及其泛化易于表达，其多项式时间解析算法可自动导出。
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.
@article{paperbot2016,
title = {Exact Recursive Probabilistic Programming},
author = {David Chiang and Colin McDonald and Chung-chieh Shan},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA1},
year = {2023},
doi = {10.1145/3586050}
}