GENERALIZE: A framework for evolving searching constraints for domain-specific languages in program synthesis

Bachelor thesis (2022)

Authors

L.G. Kroes Electrical Engineering, Mathematics and Computer Science

Contributors

S. Dumančić Algorithmics - EEMCS (mentor)
G. Smaragdakis Cyber Security - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Lucas Kroes
More Info
expand_more

Published Date

18-06-2022

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

In this paper, we propose a method for eliciting constraints for arbitrary Domain-Specific Languages (DSL) in Program Synthesis search. We argue that we can successfully predict constraints using a form of attribute-based induction. We also provide a novel approach to constraint verification using genetic algorithms to optimize desired results. We implement our approach into GENERALIZE, a novel algorithm for reducing DSL size. GENERALIZE is tested and compared against the default Brute algorithm using 2 different program synthesis domains, robot planning and pixel art. These experiments show that GENERALIZE does not improve performance if good objective functions are available, because of a tendency to get stuck in local heuristic minima. It can increase performance if no such function is available.