Expedited techniques for generating string manipulation programs

• US 9,552,335 B2
• Filed: 06/04/2012
• Issued: 01/24/2017
• Est. Priority Date: 06/04/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gulwani, Sumit, Singh, Rishabh, Rouhana, Dany, Zorn, Benjamin G., Zhong, Weide
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): ALFRED, MELISSA A
• Application Number:
  US13/487,266
• Publication Number:
  US 20130326475A1
• Time in Patent Office: 1,695 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 40/12 Use of codes for handling textual entities
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/427 Parsing

Abstract

A program creation system is described which generates sets of subprograms for respective input-output examples. The program creation system then groups the sets into partitions by performing an intersection operation. According to one aspect, the program creation system generates subprograms so as to exclude tokens that are not represented by the input strings of the input-output examples. According to another aspect, the program creation system first generates the subprograms without attempting to generate loop-type expressions. If this operation produces unsatisfactory results, the program creation system repeats its processing, this time including loop-type expressions. According to another aspect, the program creation system performs the grouping operation using an expedited graph-intersection operation. According to another aspect, the program creation system ranks programs (which are created based on the results of the grouping operation) based on the presence of preferred features found in the programs.

Claims

1. A method, performed using computing functionality, for generating subprograms that perform string manipulation tasks, comprising:

receiving and storing input-output examples, the input-output examples providing input strings and corresponding output strings;

identifying tokens that are used in input strings of the input-output examples, to provide identified tokens;

identifying a first program-generating constraint;

determining whether substrings align with natural token boundaries;

generating, based on the first program-generating constraint, sets of subprograms for the respective input-output examples, each subprogram configured to transform at least one input string associated with a particular input-output example when the substrings align with natural token boundaries, otherwise excluding generation of loop-type expressions and subprograms for the respective input-output examples;

grouping the sets of subprograms into partitions, yielding at least one representative subprogram for each partition;

determining whether said generating and grouping provide results that satisfy a predefined success test; and

repeating said generating and grouping, as governed by a second program-generating constraint, if it is determined that said generating and grouping do not satisfy the predefined success test, the second program generating constraint permitting at least one generation of loop-type expressions or subprograms based on the substrings not aligning with natural token boundaries thereby imposing greater processing complexity and allowing for a larger set of subprograms compared to the first program generating constraint.

2. The method of claim 1, further comprising repeating said generating and grouping at least one additional time, each instance of said generating and grouping being governed by a new program-generating constraint.

3. The method of claim 1, wherein said generating involves generating the subprograms so as to exclude tokens that are not represented by the identified tokens.

4. The method of claim 3, wherein said generating also entails:

identifying tokens that are used in additional input strings that do form part of the input-output examples, to provide additional identified tokens,

wherein said generating also involves generating the subprograms so as to exclude tokens that are not represented by the additional identified tokens.

5. The method of claim 1, wherein said generating involves representing each set of subprograms, associated with an input-output example, as a graph.

6. The method of claim 5, wherein said grouping comprises forming an intersection between a first graph and a second graph, the first graph being associated with a first input-output example that includes at least one first input string and a first output string, and the second graph being associated with a second input-output example that includes at least one second input string and a second output string, said forming comprising:

projecting the first graph onto the second input-output example, by running subprograms in the first graph for said at least one second input string, to provide a first projection-modified graph;

projecting the second graph onto the first input-output example, by running subprograms in the second graph for said at least one first input string, to provide a second projection-modified graph; and

taking the union of the first projection-modified graph and the second projection-modified graph.

7. The method of claim 6,

wherein said projecting of the first graph onto the second input-output example entails removing an incorrect first-graph expression, associated with a particular edge in the first graph, if the first-graph expression produces a result that is inconsistent with the second output item,

and wherein said projecting of the second graph onto the first input-output example entails removing an incorrect second-graph expression, associated with a particular edge in the second graph, if the second-graph expression produces a result that is inconsistent with the first output item.

8. The method of claim 1, the method further comprising:

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

providing created programs based on the selection conditions, together with representative subprograms provided by said grouping; and

ranking the created programs based on at least one ranking consideration.

9. The method of claim 8,

wherein at least some representative subprograms in the created programs identify a substring position using four regular expressions (r₁, r₂, r₃, r₄),

and wherein said at least one ranking consideration includes:

a first ranking consideration that preferentially biases a subprogram in which either r₂ and r₃ are empty, or r₁ and r₄ are empty;

a second ranking consideration that preferentially biases a subprogram in which r₄ is a counterpart character to r₁; and

a third ranking consideration that preferentially biases a subprogram in which r₁ and r₄ each corresponds to standard delimiter characters.

10. The method of claim 8, wherein said ranking comprises:

assigning a score to each created program based on presence of any preferred features in the created program; and

ranking the created programs based on respective scores assigned to the created programs.

11. A computer readable storage memory comprising computer readable instructions stored thereon that, responsive to execution by one or more processing devices, are configured to:

receive input-output examples, the input-output examples providing input strings and corresponding output strings;

identify tokens that are used in the input strings of the input-output examples, to provide identified tokens;

identify a first program-generating constraint;

determine whether substrings align with natural token boundaries;

generate, based on the first program generating constraint, first sets of subprograms for the respective input-output examples, each subprogram configured to transform at least one input string associated with a particular input-output example into an output string associated with the particular input-output example;

determine whether the generating provides results that satisfy a predefined success test;

if it is determined that the generating does not satisfy the predefined success test, generate, based on a second program generating constraint, second sets of programs for the respective input-output examples, the first program-generating constraint excluding generation of loop-type expressions and excluding generation of subprograms based on a consideration of substrings that do not align with natural token boundaries, and the second program-generating constraint permitting at least one of generation of loop-type expressions or generation of subprograms based on a consideration of substrings that do not align with natural token boundaries.

12. The computer readable storage memory of claim 11, wherein at least some of the subprograms use regular expressions to identify substrings, and wherein the regular expressions exclude tokens that are not represented by the identified tokens.

13. A system comprising:

one or more processors; and

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

receiving and storing input-output examples, the input-output examples providing input strings and corresponding output strings;

identifying tokens that are used in input strings of the input-output examples, to provide identified tokens;

identifying a first program-generating constraint;

determining whether substrings align with natural token boundaries;

generating, based on the first program generating constraint, sets of subprograms for the respective input-output examples, the first program-generating constraint excluding generation of loop-type expressions and excluding generation of subprograms based on a consideration of substrings that do not align with natural token boundaries;

determining whether said generating provide results that satisfy a predefined success test; and

repeating said generating, as governed by a second program-generating constraint, if it is determined that said generating does not satisfy the predefined success test, the second program-generating constraint permitting at least one of generation of loop-type expressions or generation of subprograms based on a consideration of substrings that do not align with natural token boundaries.