Generating programs based on input-output examples using converter modules

摘要

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.

主权项

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; andselecting, 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.