Utilizing Frequently Occurring Subprograms in Program Synthesis
Letting clingo find subprograms and inserting them into the grammar
J.P.L. Römer (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J.G.H. Cockx – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
S. Dumančić – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Program synthesis automatically generates pro-grams satisfying given specifications through sys-tematic search over candidate programs. This pa-per explores an enhancement to Herb.jl, a pro-gram synthesis framework, by implementing a two-phase approach that alternates between a ”wak-ing” phase that generates candidate programs, anda ”sleeping” phase that identifies frequently occur-ring subprograms and refactors the grammar ac-cordingly. The sleeping phase uses Clingo to dis-cover common patterns, which are incorporatedinto the grammar to enable more efficient synthesis.I investigate whether this iterative refactoring ac-celerates synthesis, and identify types of problemswhere it provides improvements. This work con-tributes to understanding how grammar compres-sion and abstraction discovery can enhance pro-gram synthesis efficiency.
https://github.com/jelleromer/herb-bep