Inductive Program Synthesis Guided by Observational Program Similarity

Citations Over Time

Abstract

We present a new general-purpose synthesis technique for generating programs from input-output examples. Our method, called metric program synthesis, relaxes the 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 an expert-provided 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.

Related Papers

• → News shocks or parametric indeterminacy? An observational equivalence result in linear rational expectations models(2011)8 cited
• → Using arbitrary precision arithmetic to sharpen identification analysis for DSGE models(2023)3 cited
• → On observational equivalence and algebraic specification(1985)43 cited
• → Decidability in Syntactic Control of Interference(2005)2 cited
• The observational equivalence of the Ricardian and Heckscher-Ohlin explanations of trade patterns(1984)