Modelling Program Spaces in Program Synthesis with Constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909715234029568 |
|---|---|
| author | Hinnerichs, Tilman Swinkels, Bart de Jong, Jaap Reid, Reuben Gardos Magirescu, Tudor Yorke-Smith, Neil Dumancic, Sebastijan |
| author_facet | Hinnerichs, Tilman Swinkels, Bart de Jong, Jaap Reid, Reuben Gardos Magirescu, Tudor Yorke-Smith, Neil Dumancic, Sebastijan |
| contents | A core challenge in program synthesis is taming the large space of possible programs. Since program synthesis is essentially a combinatorial search, the community has sought to leverage powerful combinatorial constraint solvers. Here, constraints are used to express the program semantics, but not as a potentially potent tool to remove unwanted programs. Recent inductive logic programming approaches introduce constraints on the program's syntax to be synthesized. These syntactic constraints allow for checking and propagating a constraint without executing the program, and thus for arbitrary operators. In this work, we leverage syntactic constraints to model program spaces, defining not just solutions that are feasible, but also ones that are likely useful. To demonstrate this idea, we introduce BART, a solver that efficiently propagates and solves these constraints. We evaluate BART on program space enumeration tasks, finding that the constraints eliminate up to 99 percent of the program space, and that modeling program spaces significantly reduces enumeration time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00005 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Modelling Program Spaces in Program Synthesis with Constraints Hinnerichs, Tilman Swinkels, Bart de Jong, Jaap Reid, Reuben Gardos Magirescu, Tudor Yorke-Smith, Neil Dumancic, Sebastijan Programming Languages Artificial Intelligence A core challenge in program synthesis is taming the large space of possible programs. Since program synthesis is essentially a combinatorial search, the community has sought to leverage powerful combinatorial constraint solvers. Here, constraints are used to express the program semantics, but not as a potentially potent tool to remove unwanted programs. Recent inductive logic programming approaches introduce constraints on the program's syntax to be synthesized. These syntactic constraints allow for checking and propagating a constraint without executing the program, and thus for arbitrary operators. In this work, we leverage syntactic constraints to model program spaces, defining not just solutions that are feasible, but also ones that are likely useful. To demonstrate this idea, we introduce BART, a solver that efficiently propagates and solves these constraints. We evaluate BART on program space enumeration tasks, finding that the constraints eliminate up to 99 percent of the program space, and that modeling program spaces significantly reduces enumeration time. |
| title | Modelling Program Spaces in Program Synthesis with Constraints |
| topic | Programming Languages Artificial Intelligence |
| url | https://arxiv.org/abs/2508.00005 |