We present [<span style="font-variant:small-caps;">Bustle</span>]{}, which integrates machine learning into bottom-up program synthesis.

-   We show how to efficiently add machine learning in the synthesis loop using property signatures and batched predictions. With these techniques, adding the model to the synthesizer provides an end-to-end improvement in synthesis time.

-   We present an evaluation on a synthesis task of string transformations. We show that [<span style="font-variant:small-caps;">Bustle</span>]{} leads to improvements in synthesis time compared to a baseline synthesizer without learning, a Deepcoder-style learning-based synthesizer [@DEEPCODER], and a hand-designed set of heuristics. Even though our model is trained on random programs, we show that the model’s performance transfers to a set of human-written synthesis benchmarks.

Background and Setup
====================

Programming by Example
----------------------

In a Programming-by-Example (PBE) task [@PBE; @MLPBE; @FLASHFILL], we are given a set of input/output pairs and the goal is to find a program such that for each pair, the synthesized program when executed on the input generates the corresponding output. To restrict the search space, the programs are typically restricted to a small domain-specific language (DSL). As an example PBE specification, consider the “io\_pairs” given in Listing \[listing:benchmarks\].

Our String Transformation DSL
-----------------------------

Following previous work [@FLASHFILL; @ROBUSTFILL], we deal 