TRANSLATING NATURAL LANGUAGE DESCRIPTIONS TO PROGRAMS IN A DOMAIN-SPECIFIC LANGUAGE FOR SPREADSHEETS

• US 20140214399A1
• Filed: 01/29/2013
• Published: 07/31/2014
• Est. Priority Date: 01/29/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gulwani, Sumit, Marron, Mark
• Granted Patent: US 9,330,090 B2
• Time in Patent Office: Days
• US Class Current: 704/8
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 8/10 Requirements analysis; Specification techniques

Abstract

A system and method to translate natural language descriptions to programs in a domain-specific language for spreadsheets. The method includes generating a model of a spreadsheet. The model includes a column description for each column, and one or more types associated with each column The method also includes normalizing the description by removing stop words, and replacing parts that match column names or data values by parameterized place-holders. The method involves applying rule-based translation along with keyword or type-based program synthesis in an inter-leaved, bottom-up manner and dynamic programming style, where phrases are mapped to sub-programs in increasing order of their length. The rules describe how to map a specific partial natural language phrase into a partial sub-program. Also, the method includes generating a number of potential programs and ranking the programs to sequence them according to their intended likelihood.

Claims

1. A method for translating natural language descriptions to programs in a domain-specific language for spreadsheets, the method comprising:

generating a model of a spreadsheet, comprising a column description for each column, and one or more types associated with each column;

identifying phrases in the natural language description that match with a column name or a data value in a column;

generating a normalized description for the original description;

generating a plurality of programs in the underlying domain-specific language from the normalized description by applying a combination of rule-driven translation and type-based program synthesis; and

ranking the generated programs in an order that reflects their likelihood.

8. The method recited in claim 1, wherein the underlying domain-specific language includes filtering operations, reduce operations, arbitrary composition of these operations, and support for operations in specific domains such as financial and social.

9. The method recited in claim 1, wherein the normalization requires removing stop words and replacing phrases that match with column names and data-values by appropriate parameter place-holders.

10. The method recited in claim 1, comprising:

determining that the natural language description does not specify a parameter a sub-program is associated with in one of the programs, wherein the parameter comprises a data type, and wherein the spreadsheet comprises no more than one column of the data type; and

associating the parameter with the one column

17. The method recited in claim 1, comprising code configured to direct the processing unit to:

determine that the natural language description does not specify a parameter a sub-program associated with one of the potential programs, wherein the parameter comprises a data type, and wherein the spreadsheet comprises no more than one column of the data type; and

associate the parameter with the one column.

2. The method recited in claim 2, comprising presenting the programs in association with the spreadsheet.

3. The method recited in claim 2, comprising presenting an explanation of each of the programs in association with the potential expression.

4. The method recited in claim 3, wherein the explanation comprises a paraphrasing of each of the programs.

5. The method recited in claim 3, wherein the explanation comprises a highlighting of a column whose values are operated on by the potential program.

6. The method recited in claim 3, wherein the explanation comprises showing a semantically equivalent program in some other domain-specific language.

7. The method recited in claim 3, comprising executing the potential program on the spreadsheet, wherein the explanation comprises a result of executing the potential program.

11. A system for translating natural language descriptions to programs in spreadsheets, the system comprising:

a processing unit; and

a system memory, wherein the system memory comprises code configured to direct the processing unit to;

generate a model of a spreadsheet, comprising a column description for each column, and one or more types associated with each column;

generating a plurality of potential programs in the domain-specific language after normalizing the natural language description and using a combination of rule-based translation and type-based program synthesis;

presenting a first of the potential programs based on a likelihood the one potential program is associated with the intended program; and

presenting a second of the potential interpretations in response to a request from the spreadsheet user.

12. The system recited in claim 11, comprising code configured to direct the processing unit to identify, in a client interface, stop words that are not included in the model.

13. The system recited in claim 11, comprising code configured to direct the processing unit to present an explanation of each of the potential programs in association with the potential program.

14. The system recited in claim 11, wherein the explanation comprises one of:

a natural language paraphrasing of the potential program;

a highlighting of a column whose values are operated on by the potential program; and

a semantically equivalent program in another domain-specific language that might be familiar to the user.

15. The system recited in claim 11, comprising code configured to direct the processing unit to execute the potential program on the spreadsheet, wherein the explanation comprises a result of execution of the potential program.

16. The system recited in claim 11, wherein the normalization process comprises one of:

removing a stop word;

replacing the phrase that refers to a column name of the spreadsheet or a data value in the spreadsheet by parameterized place-holders; and

18. One or more computer-readable storage media for translating natural language descriptions to expressions in spreadsheets, the computer-readable storage media comprising code configured to direct a processing unit to:

generate a model of a spreadsheet, comprising a column description for each column of the spreadsheet, and one or more types associated with each column;

generating a plurality of potential programs in the underlying domain-specific language from the natural language description by first normalizing the description and then using a translation system that uses a combination of rule-based translation and type-based program synthesis; and

presenting a first of the potential interpretations based on a likelihood the one potential interpretation is associated with the intended program; and

presenting a result of the program in association with a selection of one or more columns, wherein the columns are associated with the program, and wherein the result is based on the columns.

19. The computer-readable storage media recited in claim 18, wherein the normalization process comprises one of:

removing a stop word; and

replacing the phrase that refers to a column name of the spreadsheet or a data value in the spreadsheet by parameterized place-holders.

20. The computer-readable storage media recited in claim 18, comprising code configured to direct the processing unit to:

determine that the domain-specific language description does not specify a parameter for a sub-program associated with one of the potential programs, wherein the parameter comprises a data type, and wherein the spreadsheet comprises no more than one column of the data type; and

associate the parameter with the one column.