Accelerating Search-Based Program Synthesis using Learned Probabilistic Models
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.
Thu 21 Jun Times are displayed in time zone: Eastern Time (US & Canada) change
14:00 - 15:40: Synthesis and LearningPLDI Research Papers at Grand Ballroom CD Chair(s): Xin ZhangMassachusetts Institute of Technology, USA | |||
14:00 - 14:25 Talk | A General Path-Based Representation for Predicting Program Properties PLDI Research Papers Uri AlonTechnion, Meital ZilbersteinTechnion, Omer LevyUniversity of Washington, USA, Eran YahavTechnion Media Attached | ||
14:25 - 14:50 Talk | Program Synthesis using Conflict-Driven Learning PLDI Research Papers Yu FengUniversity of Texas at Austin, USA, Ruben MartinsCarnegie Mellon University, Osbert BastaniStanford University, Isil DilligUT Austin Media Attached | ||
14:50 - 15:15 Talk | Accelerating Search-Based Program Synthesis using Learned Probabilistic Models PLDI Research Papers Woosuk LeeUniversity of Pennsylvania, USA, Kihong HeoUniversity of Pennsylvania, USA, Rajeev AlurUniversity of Pennsylvania, Mayur NaikUniversity of Pennsylvania Media Attached | ||
15:15 - 15:40 Talk | Inferring Crypto API Rules from Code Changes PLDI Research Papers Media Attached |