Quantitative Programming by Examples
This work addresses the need for more efficient program synthesis in programming-by-example systems, offering incremental improvements for users in automated programming tasks.
The paper tackles the problem of synthesizing programs that minimize quantitative cost functions, such as performance or size, from input-output examples, achieving 1.53x and 1.26x improvements over a baseline system on 701 benchmarks.
Programming-by-Example (PBE) systems synthesize an intended program in some (relatively constrained) domain-specific language from a small number of input-output examples provided by the user. In this paper, we motivate and define the problem of quantitative PBE (qPBE) that relates to synthesizing an intended program over an underlying (real world) programming language that also minimizes a given quantitative cost function. We present a modular approach for solving qPBE that consists of three phases: intent disambiguation, global search, and local search. On two concrete objectives, namely program performance and size, our qPBE procedure achieves $1.53 X$ and $1.26 X$ improvement respectively over the baseline FlashFill PBE system, averaged over $701$ benchmarks. Our detailed experiments validate the design of our procedure and show the value of combining global and local search for qPBE.