Programming by Navigation
Open Access
- 10 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 447-474
Abstract
When a program synthesis task starts from an ambiguous specification, the synthesis process often involves an iterative specification refinement process. We introduce the Programming by Navigation Synthesis Problem, a new synthesis problem adapted specifically for supporting iterative specification refinement in order to find a particular target solution. In contrast to prior work, we prove that synthesizers that solve the Programming by Navigation Synthesis Problem show all valid next steps ( Strong Completeness ) and only valid next steps ( Strong Soundness ). To meet the demands of the Programming by Navigation Synthesis Problem, we introduce an algorithm to turn a type inhabitation oracle (in the style of classical logic) into a fully constructive program synthesizer. We then define such an oracle via sound compilation to Datalog. Our empirical evaluation shows that this technique results in an efficient Programming by Navigation synthesizer that solves tasks that are either impossible or too large for baselines to solve. Our synthesizer is the first to guarantee that its specification refinement process satisfies both Strong Completeness and Strong Soundness .Keywords
Funding Information
- National Science Foundation (175281,2129008,2033558)
This publication has 100 references indexed in Scilit:
- Program Synthesis Using Example Propagation2023
- Counterexample-Guided Partial Bounding for Recursive Function Synthesis2021
- The Lean 4 Theorem Prover and Programming Language2021
- Stochastic synthesis of recursive functions made easy with bananas, lenses, envelopes and barbed wireGenetic Programming and Evolvable Machines, 2019
- Abstraction-Based Interaction Model for Synthesis2017
- Constraint-Based Synthesis of Datalog Programs2017
- Bottom-Up Context-Sensitive Pointer Analysis for JavaLecture Notes in Computer Science, 2015
- Recursive Program Synthesis2013
- Using Datalog with Binary Decision Diagrams for Program Analysis2005
- A Syntactic Approach to Type SoundnessInformation and Computation, 1994