More Like this

1. Inductive Program Synthesis Guided by Observational Program Similarity

   https://doi.org/10.1145/3622830  

   Feser, Jack; Dillig, Işıl; Solar-Lezama, Armando (October 2023, Proceedings of the ACM on Programming Languages)

   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. 

   more » « less
2. Cyclic program synthesis

   https://doi.org/10.1145/3453483.3454087  

   Itzhaky, Shachar; Peleg, Hila; Polikarpova, Nadia; Rowe, Reuben N.; Sergey, Ilya (June 2021, Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation)

   null (Ed.)
3. Automated program repair

   https://doi.org/10.1145/3318162  

   Goues, Claire Le; Pradel, Michael; Roychoudhury, Abhik (November 2019, Communications of the ACM)
4. Metric Program Synthesis

   John Feser; Isil Dillig; Armando Solar-Lezama (January 2022, POPL 2022)

   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. 

   more » « less
5. Programmable Program Synthesis

   https://doi.org/10.1007/978-3-030-81685-8_4  

   D'Antoni, Loris; Hu, Qinheping; Kim, Jinwoo; Reps, Thomas (January 2021, Computer Aided Verification)

   null (Ed.)

   Program synthesis is now a reality, and we are approaching the point where domain-specific synthesizers can now handle problems of practical sizes. Moreover, some of these tools are finding adoption in industry. However, for synthesis to become a mainstream technique adopted at large by programmers as well as by end-users, we need to design programmable synthesis frameworks that (i) are not tailored to specific domains or languages, (ii) enable one to specify synthesis problems with a variety of qualitative and quantitative objectives in mind, and (iii) come equipped with theoretical as well as practical guarantees. We report on our work on designing such frameworks and on building synthesis engines that can handle program-synthesis problems describable in such frameworks, and describe open challenges and opportunities. 

   more » « less