- 64 views
- 62 downloads
Two Irons in the Fire: Synthesizing Libraries of Programs by Optimizing an Auxiliary Function while Solving Problems
-
- Author / Creator
- Rahman, Habibur
-
Program synthesis faces a significant challenge in exploring a vast program space to find a program that satisfies the user's intent. Prior studies have proposed using different methods to guide the synthesis process to address this challenge. We propose a method that offers search guidance which can be orthogonal to guidance provided by the previous functions. It only requires one to define an auxiliary objective function aligned with the synthesis task. Given a synthesis task, a domain-specific language (DSL), a programming language, and a simple domain-dependent auxiliary function, we search for a solution to the task in the language-defined program space using a baseline search algorithm. If the search fails to find a solution, we augment the language by incorporating a library of programs encountered during the search process that optimize the auxiliary function. Then we repeat the search with this library-augmented language. We continue augmenting the language and searching until it finds a solution to the given synthesis task or the system times out. We evaluate our approach in two domains: string manipulation and reverse drawing. In reverse drawing, our language augmentation method substantially increases the number of problems solved using the base algorithm, bottom-up search, outperforming Dreamcoder. In string manipulation, our proposed method increases the number of problems solved for all base algorithms evaluated: Bottom-up Search (BUS), Bee Search, Crossbeam, and Bustle.
-
- Graduation date
- Fall 2023
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.