Thu 21 Jun 2018 14:50 - 15:15 at Grand Ballroom CD - Synthesis and Learning Chair(s): Xin Zhang

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

Displayed time zone: Eastern Time (US & Canada) change

14:00 - 15:40
Synthesis and LearningPLDI Research Papers at Grand Ballroom CD
Chair(s): Xin Zhang Massachusetts Institute of Technology, USA
14:00
25m
Talk
A General Path-Based Representation for Predicting Program Properties
PLDI Research Papers
Uri Alon Technion, Meital Zilberstein Technion, Omer Levy University of Washington, USA, Eran Yahav Technion
Media Attached
14:25
25m
Talk
Program Synthesis using Conflict-Driven Learning
PLDI Research Papers
Yu Feng University of Texas at Austin, USA, Ruben Martins Carnegie Mellon University, Osbert Bastani Stanford University, Isil Dillig UT Austin
Media Attached
14:50
25m
Talk
Accelerating Search-Based Program Synthesis using Learned Probabilistic Models
PLDI Research Papers
Woosuk Lee University of Pennsylvania, USA, Kihong Heo University of Pennsylvania, USA, Rajeev Alur University of Pennsylvania, Mayur Naik University of Pennsylvania
Media Attached
15:15
25m
Talk
Inferring Crypto API Rules from Code Changes
PLDI Research Papers
Rumen Atanasov Paletov , Petar Tsankov ETH Zurich, Veselin Raychev ETH Zurich, Martin Vechev ETH Z├╝rich
Media Attached