We present a new domain-agnostic synthesis technique for generating programs from input-output examples. Our method, called metric program synthesis, relaxes the well-known observational equivalence idea (used widely in bottom-up enumerative synthesis) into a weaker notion of observational similarity, with the goal of reducing the search space that the synthesizer needs to explore. Our method clusters programs into equivalence classes based on a distance metric and constructs a version space that compactly represents "approximately correct" programs. Then, given a "close enough" program sampled from this version space, our approach uses a distance-guided repair algorithm to find a program that exactly matches the given input-output examples. We have implemented our proposed metric program synthesis technique in a tool called SyMetric and evaluate it in three different domains considered in prior work. Our evaluation shows that SyMetric outperforms other domain-agnostic synthesizers that use observational equivalence and that it achieves results competitive with domain-specific synthesizers that are either designed for or trained on those domains.
翻译:我们提出了一个新的域- 不可知合成技术, 用于从输入- 输出实例生成程序。 我们的方法, 称为 度量程序合成, 将众所周知的观测等同概念( 在自下而上的数字合成中广泛使用) 放松为较弱的观测相似性概念, 目的是减少合成人需要探索的搜索空间。 我们的方法将程序分组成基于远程测量的等同类, 并构建一个“ 近似正确” 程序的版本空间。 然后, 鉴于从这个版本空间抽样的“ 足够接近” 程序, 我们的方法使用远程指导的修复算法, 来找到一个与给定的输入- 输出示例完全匹配的程序。 我们用一个名为 SyMetetric 的工具应用了我们提议的矩阵综合方案技术, 并在先前工作中考虑的三个不同领域进行评估。 我们的评估表明, SyMetricric 将其他使用观测等同的域- 合成器, 并实现与为这些领域设计或培训的域化合成器的竞争性结果。