When writing programs, people have the ability to tackle a new complex task
by decomposing it into smaller and more familiar subtasks. While it is
difficult to measure whether neural program synthesis methods have similar
capabilities, we can measure whether they compositionally generalize, that is,
whether a model that has been trained on the simpler subtasks is subsequently
able to solve more complex tasks. In this paper, we characterize several
different forms of compositional generalization that are desirable in program
synthesis, forming a meta-benchmark which we use to create generalization tasks
for two popular datasets, RobustFill and DeepCoder. We then propose ExeDec, a
novel decomposition-based synthesis strategy that predicts execution subgoals
to solve problems step-by-step informed by program execution at each step.
ExeDec has better synthesis performance and greatly improved compositional
generalization ability compared to baselines.

通过将复杂任务分解为更小、更熟悉的子任务，人们在编写程序时能够解决新的复杂任务。本文中，我们表征了程序合成中几种不同形式的组合泛化，构建了一个元基准，用于为两个流行的数据集 RobustFill 和 DeepCoder 创建泛化任务。然后，我们提出了 ExeDec，一种新颖的基于分解的合成策略，它通过预测执行子目标，逐步解决问题并利用每一步的程序执行。与基线相比，ExeDec 具有更好的合成性能和大大改善的组合泛化能力。