Synthesized programming-by-example programs

A system for synthesizing a performant program, the system comprising:

• one or more electronic processors to:
• receive a plurality of input examples;
• receive a plurality of output examples, a number of the output examples is less than a number of the input examples, a plurality of initial input and output examples comprising the output examples and corresponding input examples;
• input the plurality of initial input and output examples to a synthesis engine that uses a first ranking function to synthesize a synthesized program;
• perform the synthesized program to generate a plurality of input and output data pairs using the input examples as input to the synthesized program;
• generate an expanded equivalence set from the plurality of input and output data pairs;
• input the expanded equivalence set of input and output data pairs to a second synthesis engine that uses a second ranking function to synthesize a first performant program;
• determine the first performant program does not satisfy at least one input and output data pair of the plurality of input and output data pairs;
• add the at least one input and output data pair to the expanded equivalence set;
• input the expanded equivalence set to the second synthesis engine to synthesize a second performant program;
• and
• determine the second performant program satisfies each of the plurality of input and of output pairs.

A non-transitory computer-readable storage media storing computer-executable instructions for synthesizing a performant program, the stored instructions comprising:

• instructions to receive a plurality of output examples, a number of output examples is less than a number of input examples, a plurality of initial input and output examples comprising the output examples and corresponding input examples;
• instructions to input the plurality of initial input and output examples to a synthesis engine that uses a first ranking function to synthesize a synthesized program;
• instructions to generate a plurality of input and output data pairs using the input examples as input to the synthesized program;
• instructions to generate an expanded equivalence set from the plurality of input and output data pairs;
• instructions to input the expanded equivalence set of input and output data pairs to a second synthesis engine that uses a second ranking function to synthesize a first performant program;
• instructions to receive the first performant program;
• instructions to determine the first performant program does not satisfy at least one input and output data pair of the plurality of input and output data pairs;
• instructions to add the at least one input and output data pair to the expanded equivalence set;
• instructions to input the expanded equivalence set to the second synthesis engine to synthesize a second performant program;
• and
• instructions to determine the second performant program satisfies each of the plurality of input and of output pairs.