一句话：将多阶段编程引入关系式编程，扩展 miniKanren 以分阶段解释含洞程序，并在综合任务中显著加速。
论文将多阶段编程从函数式编程迁移到关系式编程，提出控制分阶段与非确定性的新构造。方法是对关系解释器分阶段：被解释程序中未知表达式或值以洞表示，已知部分编译执行以消除解释开销，未知部分延迟到运行时解释。由此兼顾分阶段（把解释器变成编译器）与关系式解释（把函数变成关系、从草图综合）的优势。作者扩展 miniKanren，实现 Racket 与 miniKanren 子集的关系解释器及上下文无关文法识别器。在多个综合问题上，分阶段版本较未分阶段版本显著加速，并与手工调优的关系解释器做了指示性比较。
We transport multi-stage programming from functional to relational programming, with novel constructs to give programmers control over staging and non-determinism. We stage interpreters written as relations, in which the programs under interpretation can contain holes representing unknown expressions or values. By compiling the known parts without interpretive overhead and deferring interpretation to run time only for the unknown parts, we compound the benefits of staging (e.g., turning interpreters into compilers) and relational interpretation (e.g., turning functions into relations and synthesizing from sketches). We extend miniKanren with staging constructs and apply the resulting multi-stage language to relational interpreters for subsets of Racket and miniKanren as well as a relational recognizer for context-free grammars. We demonstrate significant performance gains across multiple synthesis problems, systematically comparing unstaged and staged computation, as well as indicatively comparing with an existing hand-tuned relational interpreter.
@article{paperbot3150,
title = {Multi-stage Relational Programming},
author = {Michael Ballantyne and Rafaello Sanna and Jason Hemann and William E. Byrd and Nada Amin},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729314}
}