Print Email Facebook Twitter Speeding up program synthesis using specification discovery Title Speeding up program synthesis using specification discovery Author de Jong, Jaap (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics; TU Delft Programming Languages) Contributor Dumančić, S. (mentor) Cockx, J.G.H. (mentor) Hinnerichs, T.R. (mentor) Spaan, M.T.J. (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science Date 2023-07-04 Abstract How convenient would it be to have an AI that relieves us programmers from the burden of coding? Program synthesis is a technique that achieves exactly that: it automatically generates simple programs that meet a given set of examples or adhere to a provided specification. This is often done by enumerating all programs in the search space and returning the first program that satisfies the requirements. However, these algorithms frequently enumerate redundant programs because of symmetries in the search space. We propose a new constraint discovery system that is able to detect these symmetries in a language and systematically generate symmetry-breaking constraints for them. To test these constraints, we implemented a novel, re-usable framework for program synthesis called Herb.jl. The generated constraints are shown to cut down search spaces to less than 25% of the original size and reduce the enumeration time by a factor of 3. Furthermore, this approach is extended to automatically discover semantic specifications without needing an expert. The effectiveness of these specifications is evaluated with an existing specification-based synthesizer, which shows that adding these specifications is an effective way to cut the synthesis time in half for domains where expert-defined specifications are not available. Together, these approaches demonstrate the effectiveness of extracting additional information from a language and applying it during enumeration. Subject program synthesisconstraintsspecification extractionenumeration To reference this document use: http://resolver.tudelft.nl/uuid:26b28efe-98fd-4c44-9ff3-d2a7d2636912 Part of collection Student theses Document type master thesis Rights © 2023 Jaap de Jong Files PDF MScThesisJaapdeJong.pdf 815.05 KB Close viewer /islandora/object/uuid:26b28efe-98fd-4c44-9ff3-d2a7d2636912/datastream/OBJ/view