paperbot · PL 论文追踪

全部论文 待读 收藏

P1 Compiling with Generating Functions

用生成函数编译
ICFP 9(ICFP)2025匹配度 5/10 · 该论文属于概率编程的精确推断与编译形式化,与贝叶斯/概率程序分析有相邻关系,且包含形式化证明与系统实现;但不涉及 LLM/Agent、静态分析或浮点程序分析,因此不属于当前核心方向。引用 3 inbox
Jianlin Li, Yizhou Zhang
crossref: 2026-09-10

AI 速览

一句话:提出以生成函数为编译目标的概率程序精确推断方法,形式化编译并证明其正确性,实现系统 Geni。

本文针对概率程序精确推断的可扩展性问题,提出一种新的编译思路:以生成函数(GF)作为编译目标。现有方法通常编译到二叉决策图(BDD)等表示并取得领先效果,作者表明面向 GF 的编译器在 BDD 方法表现良好的推断问题上同样具有竞争力,甚至在某些情况下可扩展性更强。文章给出了该编译器的形式化模型,首次为函数式概率语言定义了 GF 编译,并相对于指称语义证明了编译器的正确性。作者在名为 Geni 的概率编程系统中实现了该方法,并在多种推断问题上进行评估。结果确立了 GF 编译作为精确推断的一种有原则且强大的范式,兼具良好可扩展性、表达力与坚实的理论基础。

问题
概率程序的精确推断在大规模问题上难以扩展,现有以 BDD 等为编译目标的方法虽强,但仍有进一步提升与替代范式的空间。
方法
以生成函数(GF)作为编译目标,给出面向函数式概率语言的首个 GF 编译形式化定义,并相对于指称语义证明编译器正确性,最终实现为概率编程系统 Geni。
评估
在多种精确推断问题上评估 Geni,并与基于 BDD 的现有方法对比,显示其具有竞争力,并在部分场景下可扩展性更优。
原文摘要(Abstract)

We present a new approach to scaling exact inference for probabilistic programs, using generating functions (GFs) as a compilation target. Existing methods that target representations like binary decision diagrams (BDDs) achieve strong state-of-the-art results. We show that a compiler targeting GFs can be similarly competitive—and, in some cases, more scalable—on a range of inference problems where BDD-based methods perform well. We present a formal model of this compiler, providing the first definition of GF compilation for a functional probabilistic language. We prove that this compiler is correct with respect to a denotational semantics. Our approach is implemented in a probabilistic programming system called Geni and evaluated on a range of inference problems. Our results establish GF compilation as a principled and powerful paradigm for exact inference: it offers strong scalability, good expressiveness, and a solid theoretical foundation.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot3028,
  title = {Compiling with Generating Functions},
  author = {Jianlin Li and Yizhou Zhang},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {ICFP},
  year = {2025},
  doi = {10.1145/3747534}
}