# US 2019/0171422 A1 · Synthesized programming-by-example programs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171422 A1
- Document ID: US20190171422A1
- Status: Published application
- Kind: A1
- Application number: 15/829,591
- Filed: 2017-12-01
- Published: 2019-06-06
- Earliest claimed: 2017-12-01
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Abhishek Udupa; Sumit Gulwani
- Web page: https://patentgrep.com/patent/US20190171422A1

## CPC

- G06F 8/30: Creation or generation of source code
- G06F 8/10: Requirements analysis; Specification techniques
- G06F 8/31: {Programming languages or programming paradigms}
- G06F 8/36: Software reuse
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems, methods, and computer-executable instructions for synthesizing a performant program include receiving a plurality of input examples. A plurality of input and output data pairs are generated using the input examples as input to the synthesized program. An expanded equivalence set is generated from the plurality of input and output data pairs. The expanded equivalence set is input to a synthesis engine to synthesize a first performant program. The first performant program is received. The first performant program does not satisfy at least one input and output data pair of the plurality of input and output data pairs. At least one input and output data pairs is added to the equivalence set. The equivalence set of input and output data pairs to the synthesis engine to synthesize a second performant program. The second performant program is determined to satisfy each of the plurality of input and output data pairs.

## Claims

### Claim 1

A method for generating a performant program, the method comprising:
executing a synthesized program to generate a plurality of input and output data pairs from a plurality of input examples as input to the synthesized program;
generating, using one or more electronic processors, an expanded equivalence set from the plurality of input and output data pairs;
inputting the expanded equivalence set to a synthesis engine to synthesize a first performant program;
determining the first performant program does not satisfy at least one input and output data pair of the plurality of input and output data pairs;
adding the at least one input and output data pair to the expanded equivalence set;
inputting the expanded equivalence set with the at least one input and output data pair to the synthesis engine to synthesize a second performant program; and
determining the second performant program satisfies each of the plurality of input and output data pairs; and
returning the second performant program.

### Claim 2 (depends on 1)

The method of claim 1, further comprising receiving the plurality of input examples.

### Claim 3 (depends on 2)

The method of claim 2, further comprising receiving initial output examples to form a plurality of initial input and output examples.

### Claim 4 (depends on 3)

The method of claim 3, further comprising synthesizing the synthesized program using the plurality of initial input and output examples.

### Claim 5 (depends on 1)

The method of claim 1, wherein the expanded equivalence set comprises the initial input and output examples.

### Claim 6 (depends on 1)

The method of claim 1, wherein the expanded equivalence set comprises an input and output pair for each of the plurality of input examples.

### Claim 7 (depends on 1)

The method of claim 1, wherein adding the at least one input and output pair to the expanded equivalence set comprises determining an error for each incorrect input and output pair, wherein the at least one input and output pair comprises the input and output pair with the largest error.

### Claim 8 (depends on 1)

The method of claim 1, wherein the synthesis engine uses a performance ranking function to select the first performant program and the second performant program.

### Claim 9 (depends on 8)

The method of claim 8, wherein the ranking function estimates performance of synthesized programs.

### Claim 10

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.

### Claim 11 (depends on 10)

The system of claim 10, wherein the expanded equivalence set comprises the plurality of initial input and output data pairs.

### Claim 12 (depends on 10)

The system of claim 10, wherein the expanded equivalence set comprises an input and output data pair for each of the plurality of input examples.

### Claim 13 (depends on 10)

The system of claim 10, wherein to add the at least one input and output data pair to the expanded equivalence set the one or more electronic processor determine an error for each incorrect input and output pair, wherein the at least one input and output data pair comprises the input and output data pair with the largest error.

### Claim 14 (depends on 10)

The system of claim 10, wherein the first ranking function is an intent-based function.

### Claim 15 (depends on 14)

The system of claim 14, wherein the second ranking function is a performance function.

### Claim 16 (depends on 15)

The system of claim 15, wherein the second ranking function estimates performance of synthesized programs.

### Claim 17 (depends on 10)

The system of claim 10, wherein the first synthesis engine is the second synthesis engine.

### Claim 18 (depends on 10)

The system of claim 10, wherein the first synthesis engine is different from the second synthesis engine.

### Claim 19

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.

### Claim 20 (depends on 19)

The non-transitory computer-readable storage media of claim 19, wherein the expanded equivalence set comprises the plurality of initial input and output data pairs.
