一句话：提出 cut 函数与 guarded DSL，把示例编程合成扩展到含非 EI/EE 算子的大型 DSL，并实现 FlashFill++。
示例编程（PBE）需从少量输入输出示例合成程序。传统方法依赖顶层有效可逆（EI）、底层有效可枚举（EE）算子的狭窄 DSL，结合自顶向下逆推与自底向上传播。但支持丰富变换和可读代码生成的大 DSL 常含非 EI/EE 算子，难以扩展。本文提出 cut 函数，利用另一侧子 DSL 知识剪枝传播值，并可用不完整 cut 控制搜索空间；又提出 guarded DSL，以算子优先级动态控制路径探索。两者减少传播值与路径，提升深层 DSL 及大扇出文法的效率与排序。作者实现工业级 PBE 引擎 FlashFill++，支持日期时间、数字等字符串变换，并可生成 Excel 公式、PowerFx、Python 代码。评估显示其表达力、性能和代码质量优于同类系统，并已部署于百万用户级产品。
Programming-by-Examples (PBE) involves synthesizing an "intended program" from a small set of user-provided input-output examples. A key PBE strategy has been to restrict the search to a carefully designed small domain-specific language (DSL) with "effectively-invertible" (EI) operators at the top and "effectively-enumerable" (EE) operators at the bottom. This facilitates an effective combination of top-down synthesis strategy (which backpropagates outputs over various paths in the DSL using inverse functions) with a bottom-up synthesis strategy (which propagates inputs over various paths in the DSL). We address the problem of scaling synthesis to large DSLs with several non-EI/EE operators. This is motivated by the need to support a richer class of transformations and the need for readable code generation. We propose a novel solution strategy that relies on propagating fewer values and over fewer paths. Our first key idea is that of "cut functions" that prune the set of values being propagated by using knowledge of the sub-DSL on the other side. Cuts can be designed to preserve completeness of synthesis; however, DSL designers may use incomplete cuts to have finer control over the kind of programs synthesized. In either case, cuts make search feasible for non-EI/EE operators and efficient for deep DSLs. Our second key idea is that of "guarded DSLs" that allow a precedence on DSL operators, which dynamically controls exploration of various paths in the DSL. This makes search efficient over grammars with large fanouts without losing recall. It also makes ranking simpler yet more effective in learning an intended program from very few examples. Both cuts and precedence provide a mechanism to the DSL designer to restrict search to a reasonable, and possibly incomplete, space of programs. Using cuts and gDSLs, we have built FlashFill++, an industrial-strength PBE engine for performing rich string transformations, including datetime and number manipulations. The FlashFill++ gDSL is designed to enable readable code generation in different target languages including Excel's formula language, PowerFx, and Python. We show FlashFill++ is more expressive, more performant, and generates better quality code than comparable existing PBE systems. FlashFill++ is being deployed in several mass-market products ranging from spreadsheet software to notebooks and business intelligence applications, each with millions of users.
@article{paperbot2113,
title = {FlashFill++: Scaling Programming by Example by Cutting to the Chase},
author = {José Cambronero and Sumit Gulwani and Vu Le and Daniel Perelman and Arjun Radhakrishna and Clint Simon and Ashish Tiwari},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {POPL},
year = {2023},
doi = {10.1145/3571226}
}