Disjunctive Program Synthesis: A Robust Approach to Programming by Example

Programming by example systems allow end users to easily create programs by providing a few input-output examples to specify their intended task, from which the system aims to generate a satisfying program. However, a key challenge faced by existing PBE techniques is the robustness of the programs synthesized from a small number of examples, as these programs often fail when applied to new inputs. This is because there can be many possible programs that satisfy a small number of examples, and the PBE system has to somehow rank between these candidates and choose the correct one without any further information from the user. In this work we present a different approach to PBE in which we avoid making a ranking decision at the synthesis stage, by instead synthesizing a kind of disjunctive program that includes the many possible top ranked programs and selects between these different choices upon execution on a new input. This delayed choice brings the important benefit of comparing the possible outputs on the given input at execution time. We present a generic framework for implementing such disjunctive programs for arbitrary DSLs, and describe two concrete implementations of disjunctive synthesis in the practical domains of data extraction from plain text and HTML documents. We present results showing the significant improvement in robustness achieved with our disjunctive approach as illustrated by an increase from 59% to 93% of correct programs that can be learnt from a single example.