Generating text manipulation programs using input-output examples

• US 8,972,930 B2
• Filed: 06/04/2010
• Issued: 03/03/2015
• Est. Priority Date: 06/04/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gulwani, Sumit
• Primary Examiner(s): Deng, Anna
• Assistant Examiner(s): Wu, Junchun
• Application Number:
  US12/793,700
• Publication Number:
  US 20110302553A1
• Time in Patent Office: 1,733 Days
• Field of Search: 717/107
• US Class Current: 717/107
• CPC Class Codes: G06F 40/16 Automatic learning of transformation rules, e.g. from examples
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs

Abstract

A program creation system is described which generates a data manipulation program based on input-output examples. The created program may include a collection of subprograms together with a collection of corresponding selection conditions. When a new input item is received, a program execution module uses the selection conditions to select one of the subprograms. The program execution module then applies the selected subprogram to generate a new output item. The program creation system generates the program using a three-part approach, involving: generating sets of subprograms for the respective input-output examples; grouping the sets of programs into partitions and choosing representative subprograms for the partitions; and determining the selection conditions. A user interaction module provides various mechanisms which allow a user to interact with the program creation system and thereby improve the performance of the created program.

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, the input-output examples providing input text-strings and corresponding output text-strings, each corresponding output text-string representing a transformation performed on a respective input text-string;

analyzing the input-output examples to generate sets of subprograms for the respective input-output examples, each subprogram configured to transform an input text-string associated with a particular input-output example to an output text-string associated with the particular input-output example, wherein said generating comprises generating a set of subprograms for the particular input-output example by identifying occurrences of string items in the input text-string that match respective string items in the output text-string to provide matching results, and providing the set of subprograms that map the input text-string to the output text-string using the matching results and constant strings;

grouping the sets of subprograms into partitions, and selecting representative subprograms from the respective partitions;

determining selection conditions for the respective partitions, each selection condition covering input text-strings associated with a particular partition while excluding input text-strings associated with other partitions; and

providing a created program based on the selection conditions together with the representative subprograms.

2. The method of claim 1, wherein said generating further comprises determining whether at least one additional subprogram can be generated using a loop constructor, and if so, adding said at least one additional subprogram to the set of subprograms.

3. The method of claim 1, wherein said generating comprises expressing each subprogram using an expression language that includes one or more of:

a concatenate constructor;

a substring extraction constructor;

a loop constructor; and

a constant string constructor.

4. The method of claim 1, wherein said generating comprises representing each set of subprograms as a directed acyclic graph, wherein an identical operation performed by two or more subprograms in the set corresponds to a single edge in the directed acyclic graph.

5. The method of claim 1, wherein said grouping comprises:

commencing an iterative grouping procedure by treating the input-output examples as singleton partitions;

determining appropriateness of combining respective candidate pairs of partitions together based on a compatibility consideration;

combining a candidate pair of partitions together into a single partition based on said determining of appropriateness; and

repeating said determining of appropriateness and combining until a termination condition is reached.

6. The method of claim 5, wherein the compatibility consideration specifies that a candidate pair of partitions is not a viable candidate for combination if an intersection of sets of subprograms corresponding to the candidate pair of partitions results in an empty set.

7. The method of claim 5, wherein the compatibility consideration favors combination of a candidate pair of partitions if a first partition and a second partition of the candidate pair of partitions have similar characteristics to each other with respect to other partitions.

8. The method of claim 1, wherein said determining of selection conditions comprises, for the particular partition:

determining attributes of input text-strings associated with the input-output examples; and

selecting a combination of formula elements, associated with the attributes, that has an effect of covering input text-strings associated with the particular partition while excluding input text-strings associated with other partitions.

9. The method of claim 1, further comprising:

receiving a new input text-string analyzing the new input text-string to determine a selection condition which applies, and selecting a corresponding subprogram; and

transforming the new input text-string into a new output text-string using the corresponding subprogram.

10. The method of claim 1, further comprising:

receiving identification from a user that an output text-string generated for a new input text-string is undesirable;

providing a new input-output example associated with the new input text-string, together with a corrected counterpart of the output text-string generated for the new input text-string; and

providing a modified created program based, in part, on the new input-output example.

11. The method of claim 1, further comprising:

identifying a new input text-string as ambiguous;

receiving input from the user which clarifies a proper form of an output text-string for the new input text-string; and

using the input from the user to improve the created program.

12. The method of claim 1, further comprising providing a natural language explanation that identifies logic that is being used by the created program to convert a new input text-string into a new output text-string.

13. A computing device comprising:

one or more processors;

one or more memories having instructions stored thereon that, responsive to execution by the one or more processors, perform operations comprising;

receiving input-output examples, the input-output examples providing input text-strings and corresponding output text-strings, each corresponding output text-string representing a transformation performed on a respective input text-string;

analyzing the input-output examples to generate sets of subprograms for the respective input-output examples, each subprogram configured to transform an input text-string associated with a particular input-output example to an output text-string associated with the particular input-output example, wherein said generating comprises generating a set of subprograms for the particular input example by identifying occurrences of string items in the input text-string that match respective string items in the output text-string to provide matching results, and providing the set of subprograms that map the input text-string to the output text-string using the matching results and constant strings;

grouping the sets of subprograms into partitions, and selecting representative subprograms from the respective partitions;

determining selection conditions for the respective partitions, each selection condition covering input text-strings associated with a particular partition while excluding input text-strings associated with other partitions; and

providing a created program based on the selection conditions together with the representative subprograms.

14. The computing device of claim 13, wherein each subprogram is constructed from constructors of an expression language, wherein the constructors of the expression language include a loop constructor for repeating a string item a plurality of times.

15. The computing device of claim 14, wherein the constructors of the expression language include a substring constructor for selecting a substring within an identified string item.

16. The computing device of claim 14, wherein the expression language interprets content in input string items and output string items as predefined types of tokens.

17. The computing device of claim 13, wherein each subprogram includes a plurality of selection conditions, wherein each selection condition is constructed based on at least one match constructor, a match constructor determining whether an identified regular expression is present in an identified string item a specified number of times.

18. A data manipulation system comprising:

data manipulation functionality for performing a data manipulation task;

at least a memory and a processor configured to implement a program creation system configured to;

receive input-output examples provided by the data manipulation functionality, the input-output examples providing input string items and corresponding output string items, each corresponding output string item representing a transformation performed on a respective input string item; and

analyze the input-output examples to generate sets of subprograms for the respective input-output examples, each subprogram configured to transform an input text-string associated with a particular input-output example to an output text-string associated with the particular input-output example, wherein said generating comprises generating a set of subprograms for the particular input-output example by identifying occurrences of string items in the input text-string that match respective string items in the output text-string to provide matching results, and providing the set of subprograms that map the input text-string to the output text-string using the matching results and constant strings;

group the sets of subprograms into partitions, and select representative subprograms from the respective partitions;

determine selection conditions for the respective partitions, each selection condition covering input text-strings associated with a particular partition while excluding input text-strings associated with other partitions;

provide a created program based on the sets of subprograms; and

a user interaction module configured to receive input from a user which provides feedback on assessed desirability of output results provided by the created program.

19. The data manipulation system of claim 18, wherein the data manipulation functionality comprises spreadsheet system.