23 0

Accelerating search-based program synthesis using learned probabilistic models

Title
Accelerating search-based program synthesis using learned probabilistic models
Author
이우석
Keywords
Domain-specific languages; Statistical methods; Synthesis; Transfer learning
Issue Date
2018-06
Publisher
ACM
Citation
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Page. 436-449
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.
URI
https://dl.acm.org/citation.cfm?doid=3192366.3192410http://repository.hanyang.ac.kr/handle/20.500.11754/105568
ISBN
978-1-4503-5698-5
DOI
10.1145/3192366.3192410
Appears in Collections:
COLLEGE OF COMPUTING[E] > COMPUTER SCIENCE(소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE