Translating natural language descriptions to programs in a domain-specific language for spreadsheets

Patent metadata

Field	Value
Publication number	US-9330090-B2
Application number	US-201313753507-A
Country	US
Kind code	B2
Filing date	Jan 29, 2013
Priority date	Jan 29, 2013
Publication date	May 3, 2016
Grant date	May 3, 2016

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.

First claim

What is claimed is:

1. A method for translating natural language descriptions to programs in a domain-specific language for spreadsheet documents, the method comprising:
generating a model of a spreadsheet document generated by a spreadsheet program, 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 based on the model;
generating a normalized description for the original description based on the identified phrases;
generating a plurality of programs in an 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.

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

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 , comprising executing the potential program on the spreadsheet document, wherein the explanation comprises a result of executing the potential program.

7. 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.

8. 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.

9. 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 document comprises no more than one column of the data type; and
associating the parameter with the one column.

10. The method of claim 1 , comprising providing feedback on the natural language description, wherein the feedback comprises information relevant to a correction to the natural language description.

11. A system for translating natural language descriptions to programs in spreadsheet documents, 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 document generated by a spreadsheet program, comprising a column description for each column, and one or more types associated with each column;
generate a plurality of potential programs in a domain-specific language after normalizing the natural language description based on the model, and using a combination of rule-based translation and type-based program synthesis;
present a first of the potential programs based on a likelihood the one potential program is associated with the intended program; and
present a second of the potential interpretations in response to a request from a 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; or
a highlighting of a column whose values are operated on by the potential program.

15. The system recited in claim 11 , comprising code configured to direct the processing unit to execute the potential program on the spreadsheet document, 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; or
replacing the phrase that refers to a column name of the spreadsheet document or a data value in the spreadsheet document by parameterized place-holders.

17. The system recited in claim 11 , 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 document comprises no more than one column of the data type; and
associate the parameter with the one column.

18. One or more computer-readable storage media for translating natural language descriptions to expressions in spreadsheet documents, the computer-readable storage media comprising code configured to direct a processing unit to:
generate a model of a spreadsheet document generated by a spreadsheet program, comprising a column description for each column of the spreadsheet document, and one or more types associated with each column;
generate a plurality of potential programs in an underlying domain-specific language from the natural language description by first normalizing the description based on the model, and then using a translation system that uses a combination of rule-based translation and type-based program synthesis; and
present a first of the potential interpretations based on a likelihood the one potential interpretation is associated with the intended program; and
present 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 one or more computer-readable storage media recited in claim 18 , wherein the normalization process comprises one of:
removing a stop word; or
replacing the phrase that refers to a column name of the spreadsheet document or a data value in the spreadsheet document by parameterized place-holders.

20. The one or more 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 document comprises no more than one column of the data type; and
associate the parameter with the one column.

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Gulwani Sumit
• Marron Mark

Classifications

• G06F40/40 Primary

  Processing or translation of natural language (natural language analysis G06F40/20; semantic analysis G06F40/30) · CPC title

• G06F8/10 Primary

  Requirements analysis; Specification techniques · CPC title

• G06F40/18

  of spreadsheets (form-filling G06F40/174) · CPC title

• G06F17/246

  Physics · mapped topic

• G06F17/28 Primary

  Physics · mapped topic