- author = "Woosuk Lee and Kihong Heo and Rajeev Alur and Mayur Naik",
- title = "Accelerating search-based program synthesis using learned probabilistic models",
- booktitle = "Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018",
- year = "2018",
- editor = "Jeffrey S. Foster and Dan Grossman",
- pages = "436--449",
- address = "Philadelphia, PA, USA",
- month = jun # " 18-22",
- publisher = "ACM",
- keywords = "genetic algorithms, genetic programming, SBSE, Synthesis, Domain-specific languages, Statistical methods, Transfer learning",
- timestamp = "Wed, 23 Jun 2021 15:34:31 +0200",
-
biburl = "
https://dblp.org/rec/conf/pldi/LeeHAN18.bib",
- bibsource = "dblp computer science bibliography, https://dblp.org",
-
URL = "
http://psl.hanyang.ac.kr/assets/pdf/pldi18.pdf",
-
URL = "https://doi.org/10.1145/3192366.3192410",
-
DOI = "
doi:10.1145/3192366.3192410",
-
code_url = "https://github.com/wslee/euphony",
- size = "14 pages",
- abstract = "A key challenge in program synthesis concerns how to efficiently search for the desired program in the space of possible programs. We propose a general approach to accelerate search-based program synthesis by biasing the search towards likely programs. Our approach targets a standard formulation, syntax-guided synthesis (SyGuS), by extending the grammar of possible programs with a probabilistic model dictating the likelihood of each program. We develop a weighted search algorithm to efficiently enumerate programs in order of their likelihood. We also propose a method based on transfer learning that enables to effectively learn a powerful model, called probabilistic higher-order grammar, from known solutions in a domain. We have implemented our approach in a tool called Euphony and evaluate it on SyGuS benchmark problems from a variety of domains. We show that Euphony can learn good models using easily obtainable solutions, and achieves significant performance gains over existing general-purpose as well as domain-specific synthesizers.",
-
notes = "https://www.cis.upenn.edu/~alur/PLDI18.pdf Appendix:
'To find pbest, we adopt a genetic-programming like
procedure'
p447 'We compare Euphony with FlashFill'",
