Introduction
Programming-by-Example (PBE) has revolutionized end-user data manipulation, enabling tasks like string reformatting through simple demonstrations. However, as data complexity grows, traditional PBE systems—which typically synthesize programs from scratch for every new example—suffer from exponential time complexity. This paper presents Iterative Programming-by-Example (IPBE), a novel framework that treats program synthesis as an incremental refinement process rather than a repetitive search.
The IPBE Framework
The core innovation of IPBE lies in its ability to reuse "mostly correct" subprograms from previous iterations. When a user provides a new example that the current program fails to handle, the system does not discard its previous work. Instead, it performs a surgical "patching" operation.
Trace-Based Bug Localization
The system utilizes computational "traces" to map the execution of an existing program against the desired output for a new input. By comparing these traces, IPBE can deterministically identify which specific subprograms (e.g., a particular regex or index operation) are responsible for the failure.
Once the "buggy" subprograms are localized, the system searches for replacement patches within the Domain-Specific Language (DSL) while keeping the successful components intact. This decomposition significantly reduces the search space, making the synthesis time proportional to the complexity of the change rather than the total program size.
Evaluation and Results
The authors evaluated IPBE against standard non-iterative baselines across real-world and synthetic datasets. In real-world scenarios involving complex data cleaning, IPBE demonstrated a dramatic performance advantage. For instance, on a dataset of 30 large-scale scenarios, IPBE reduced average generation time from 4.02 seconds to just 0.20 seconds.
Scalability
The most significant gains were observed in synthetic tests designed to push the limits of program complexity. As the number of data columns to be transformed simultaneously increased, the traditional approach's synthesis time grew steeply. IPBE, however, maintained a much flatter growth curve, demonstrating its fitness for heavy-duty data cleaning tasks.
Conclusion
IPBE demonstrates that iterative refinement is a superior strategy for scaling PBE systems. By leveraging the "mostly correct" nature of evolving programs and using traces for precise bug localization, the system achieves order-of-magnitude speedups. Future work aims to extend this logic to broader domains and explore how the system might proactively guide users toward more informative examples.
Summary updated