Generating programs based on input-output examples using converter modules

• US 9,613,115 B2
• Filed: 07/12/2010
• Issued: 04/04/2017
• Est. Priority Date: 07/12/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gulwani, Sumit, Walker, David P.
• Primary Examiner(s): Hutton, Nan
• Application Number:
  US12/834,031
• Publication Number:
  US 20120011152A1
• Time in Patent Office: 2,458 Days
• Field of Search: 707602
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 8/51 Source to source

Abstract

A program generation system is described that generates a program based on a plurality of input-output examples. The input-output examples include input items and corresponding output items. The program generation system can include three component modules. A parsing module processes the input items and output items to provide a plurality of input parts and output parts, respectively. A transformation module determines, for each output part, whether the output part can be produced from a corresponding input part using one or more converter modules selected from a collection of candidate converter modules. A formatting module generates formatting instructions that transform selected output parts into a form specified by the output items. These three modules provide a generated program that embodies logic learned from the input-output examples; the generated program can be subsequently used to transform new input items into new respective output items.

Claims

1. A method, performed using at least one computing device, for generating a program that performs a data manipulation task, comprising:

receiving input-output examples that include input items and corresponding output items, the corresponding output items representing transformed versions of respective input items;

parsing the input items and the output items to provide a plurality of input parts and output parts, respectively, the parsing including;

identifying multiple alternative approaches for parsing the input items and the output items into the plurality of input parts and output parts; and

selecting, based on analysis of the multiple alternative approaches, one of the multiple alternative approaches to use to parse the input items and the output items;

identifying portions of the output items that match portions of the respective input items by comparing the input parts with the output parts;

determining, for each output part, whether the output part can be produced from a corresponding input part using one or more converter modules;

generating formatting instructions which transform selected output parts into a form specified by the output items; and

automatically creating a program based on said parsing, said determining, and said generating, the program being configured to be used to transform subsequently received new input items into new respective output items.

2. The method of claim 1, wherein said parsing comprises determining the input parts and the output parts based on a data store of parsing rules.

3. The method of claim 1, wherein said determining comprises selecting said one or more converter modules from a collection of candidate converter modules.

4. The method of claim 3, wherein said determining comprises investigating each candidate converter module in the collection of candidate converter modules.

5. The method of claim 4, wherein said determining also comprises investigating each combination of two or more converter modules in the collection of candidate converter modules.

6. The method of claim 3, wherein said determining comprises using a search acceleration tool to select said one or more converter modules from the collection of candidate converter modules.

7. The method of claim 6, wherein the search acceleration tool is a satisfiability determination module.

8. The method of claim 3, wherein at least one of the candidate converter modules converts date information from a first date format to a second date format.

9. The method of claim 3, wherein at least one of the candidate converter modules converts measurement information from a first standard to a second standard.

10. The method of claim 3, wherein at least one of the candidate converter modules processes numeric information using a mathematical operation.

11. The method of claim 1, wherein said generating comprises generating formatting instructions which arrange output parts in an order which matches a format specified by the output items.

12. The method of claim 1, wherein said generating comprises generating formatting instructions which print constant information to match invariant information presented in the output items.

13. A program generation system comprising:

a data store that provides a collection of candidate converter modules, each candidate converter module configured to transform input information into output information based on at least one predetermined conversion rule;

at least a memory and a processor to implement;

a parsing module configured to receive a plurality of input-output examples, the input-output examples including input items and corresponding output items that represent transformed versions of respective input items, and to process the input items and the output items based on at least;

identification of two or more alternative approaches for dividing the input items and the output items into plural parts;

selection of one said approach based on an analysis of the two or more alternative approaches;

provision of a plurality of input parts and output parts, respectively, based on the selected approach; and

identification of portions of the output items that match portions of the input items based on a comparison of the input parts with the output parts;

a transformation module configured to determine, for each output part, whether the output part can be produced from a corresponding input part using one or more converter modules selected from the collection of candidate converter modules; and

a formatting module configured to generate formatting instructions that transform selected output parts into a form specified by the output items,

the program generation system configured to automatically create a program using the parsing module, the transformation module, and the formatting module to be used to transform subsequently received new input items into new respective output items.

14. The program generation system of claim 13, wherein the parsing module is configured to determine the input parts and the output parts based on a data store of parsing rules.

15. The program generation system of claim 13, wherein the transformation module is configured to use a search acceleration tool to select said one or more converter modules from the collection of candidate converter modules.

16. The program generation system of claim 13, wherein the formatting module is configured to generate formatting instructions which arrange output parts in an order which matches a format specified by the output items.

17. The program generation system of claim 13, wherein the formatting module is configured to generate formatting instructions which print constant information to match invariant information presented in the output items.

18. A computer readable storage device for storing computer readable instructions, the computer readable instructions providing a program generation system when executed by one or more processing devices, the computer readable instructions comprising:

parsing logic configured to receive input-output examples, the input-output examples providing input items and corresponding output items that represent transformed versions of the input items, the parsing logic configured to;

process the input items to provide a plurality of input parts based on identification of multiple alternative approaches for dividing the input items into the plurality of input parts, and selection of one said approach based on an analysis of the multiple alternative approaches;

process the output items to provide a plurality of output parts based on selection of an additional approach from among multiple additional alternative approaches for dividing the output items into the plurality of output parts; and

identify portions of the output items that match portions of respective input items by comparing the output parts with the input parts;

transformation logic configured to determine, for each output part, whether the output part can be produced from a corresponding input part using one or more converter modules selected from a collection of candidate converter modules, each candidate converter module configured to transform input information into output information based on at least one predetermined conversion rule;

formatting logic configured to generate formatting instructions which transform selected output parts into a form specified by the output items, at least one formatting instruction governing an order of presentation of the output parts; and

program generation logic configured to use at least the selected one or more converter modules and the generated formatting instructions to produce a program that is to be used to transform subsequently received additional input items into additional respective output items.

19. The computer readable storage device of claim 18, wherein the transformation logic is configured to use a search acceleration tool to select said one or more converter modules from the collection of candidate converter modules.

20. The computer readable storage device of claim 18, wherein the formatting logic is configured to generate formatting instructions which print constant information to match invariant information presented in the output items.