Patent ID: 12229529

DESCRIPTION OF EMBODIMENTS

The following describes an embodiment of the present invention based on the drawings.FIG.1is a diagram showing an example of a hardware configuration of a program generation device10in the embodiment of the present invention. The program generation device10shown inFIG.1includes a drive device100, an auxiliary storage device102, a memory device103, a CPU104, an interface device105, a display device106, an input device107, and the like, which are connected to each other via a bus B.

A program that realizes processing performed in the program generation device10is provided using a recording medium101such as a CD-ROM. When the recording medium101on which the program is stored is set in the drive device100, the program is installed in the auxiliary storage device102from the recording medium101via the drive device100. However, the program does not necessarily have to be installed from the recording medium101, and may be downloaded from another computer via a network. The auxiliary storage device102stores therein the installed program and necessary files, data, and the like.

When a program start instruction is given, the memory device103reads the program from the auxiliary storage device102and stores the program in the memory device103. The CPU104realizes functions relating to the program generation device10in accordance with the program stored in the memory device103. The interface device105is used as an interface for connection to a network. The display device106displays GUI (Graphical User Interface) or the like of the program. The input device107is constituted by a keyboard and a mouse, for example, and is used to input various operation instructions.

FIG.2is a diagram showing an example of a functional configuration of the program generation device10in the embodiment of the present invention. The program generation device10shown inFIG.2includes a training unit11, a similar code search unit12, a program synthesis unit13, a synthesized program execution unit14, and an input-output result determination unit15. These units are realized through processing that one or more programs installed in the program generation device10cause the CPU104to execute.

The program generation device10also includes a search data set16. As described later, the search data set16is a set of search data pieces that are each expressed as a pair of a program (a source code of the program) and a specification of the program written in natural language. The search data set16is stored in the auxiliary storage device102, for example. It is preferable that source codes included in the search data are syntactically correct source codes (i.e., satisfy the syntax of a programming language), and therefore, in the following description, it is assumed that the source codes included in the search data are syntactically correct source codes.

The following describes a processing procedure that is executed by the program generation device10.FIG.3is a flowchart showing an example of the processing procedure executed by the program generation device10.

First, the training unit11executes training processing of a model (hereinafter referred to as a “machine learning model”) that is constituted by a neural network such as an RNN (Recurrent Neural Network) (step S10). In the training processing of the machine learning model, the model is caused to learn a relationship between natural language that describes a specification of a program and similarity of the structure of the program. Here, similarity of the structure of a program can be calculated using a method disclosed in Reference Document 1: Yusuke ODA, Shigeru WAKABAYASHI, “Method of Similarity Quantification between Program Codes”, research reports of Kobe City College of Technology, for example.

Subsequently, the similar code search unit12executes similar code search processing (step S20). In the similar code search processing, a specification that is written in natural language for the program to be generated (hereinafter referred to as the “target program”) and specifications written in natural language for programs included in respective search data pieces of the search data set16are input to the trained machine learning model, which has been trained in step S10, to find a source code (hereinafter referred to as a “similar code”) of a program that has a specification similar to the specification of the target program from the search data set16. The similar code is a source code that serves as a basis (source) when the target program is automatically generated.

Subsequently, the program synthesis unit13, the synthesized program execution unit14, and the input-output result determination unit15execute program synthesis processing (step S30). In the program synthesis processing, the target program that satisfies the specification (intention of the creator) is automatically generated by using the similar code found through the similar code search processing, as a basis, and repeating a partial change of the similar code (cumulatively changing the similar code portion by portion) until a program that satisfies input-output examples (at least one pair of an input value and an output value) generated in advance is generated.

That is, in the present embodiment, the possibility of a program conforming to the specification being generated is increased using two types of information, i.e., the specification of the target program written in natural language and input-output examples.

Next, details of step S10shown inFIG.3will be described.FIG.4is a flowchart showing an example of a processing procedure of the machine learning model training processing.

In step S101, the training unit11acquires two pieces of search data at random from the search data set16.

FIG.5is a diagram showing an example of the search data set16. InFIG.5, each table in the search data set16corresponds to a single piece of search data. The following is the data structure of the search data set16written in a form that is based on the BNF (Backus-Naur form) notation.<search data set>::=[specification source code]+

That is, the search data set16is a set of search data pieces that each include a specification (hereinafter referred to as a “search specification”) written in natural language and a source code of a program. It should be noted that the source code of the program satisfies the syntax of a programming language, as described above. Such a search data set16is prepared in advance.

In the following description, the two pieces of search data acquired at random in step S101will be referred to as “search data A” and “search data B”.

Subsequently, the training unit11decomposes (divides) each of a search specification (hereinafter referred to as a “search specification A”) included in the search data A and a search specification (hereinafter referred to as a “search specification B”) included in the search data B into words. As a result, the search specification A and the search specification B are converted to strings of words (hereinafter referred to as “word strings”).

In step S103, the training unit11inputs the word string of the search specification A to the machine learning model to obtain an output vector (hereinafter referred to as an “output vector A”). Similarly, the training unit11inputs the word string of the search specification B to the machine learning model to obtain an output vector (hereinafter referred to as an “output vector B”).

Then, the training unit11trains the machine learning model so that similarity between the output vector A and the output vector B becomes close to similarity between the structure of the source code included in the search data A and the structure of the source code included in the search data B (step S104). Thus, it is possible to cause the machine learning model to learn a relationship between natural language that describes a specification of a program and similarity of the structure of the program.

Here, any type of similarity can be used as the similarity between output vectors. For example, cosine similarity between the output vectors can be used. The similarity between the structures of source codes can be calculated using the method disclosed in Reference Document 1 described above.

Steps S101to S104are repeatedly executed until the learning converges, for example. Whether or not the learning has converged can be determined based on, for example, a condition that a change amount in the value of an objective function for evaluating closeness between similarity of output vectors and similarity of structures of source codes is smaller than a predetermined value between before and after the repetition, or a condition that the repetition has been performed at least a predetermined number of times.

Next, details of step S20shown inFIG.3will be described.FIG.6is a flowchart showing an example of a processing procedure of the similar code search processing. In the similar code search processing, a search data set that is different from the search data set16used in the machine learning model training processing may be used.

In step S201, the similar code search unit12decomposes the specification (hereinafter referred to as the “target specification”) written in natural language for the target program and search specifications included in respective search data pieces constituting the search data set16into words. As a result, a plurality of word strings (i.e., a word string of the target specification and word strings of the respective search specifications) are obtained.

Subsequently, the similar code search unit12inputs each of the plurality of word strings obtained in step S201to the trained machine learning model to obtain a plurality of output vectors (step S202). Thus, an output vector corresponding to the target specification (i.e., an output vector obtained by inputting the word string of the target specification to the trained machine learning model) and output vectors corresponding to the respective search specifications (i.e., output vectors obtained by inputting word strings of the respective search specifications to the trained machine learning model) are obtained.

Subsequently, the similar code search unit12calculates similarity between the output vector corresponding to the target specification and an output vector corresponding to each search specification (step S203). For example, when the output vector corresponding to the target specification is referred to as an “output vector a” and output vectors corresponding to the respective search specifications are referred to as an “output vector A1”, an “output vector A2”, . . . , and an “output vector An”, the similar code search unit12calculates similarity between the output vector a and the output vector A1, similarity between the output vector a and the output vector A2, . . . , and similarity between the output vector a and the output vector An. It should be noted that, as described above, cosine similarity can be used as the similarity between output vectors, for example.

Then, the similar code search unit12identifies search data that includes a search specification that corresponds to an output vector having the highest similarity among similarities calculated in step S203, and acquires a source code included in the identified search data as a similar code from the search data set16(step S204). Thus, out of source codes included in the search data set16, the source code of a program having a structure that is close to the structure required for the specification of the target program is obtained as the similar code.

Next, details of step S30shown inFIG.3will be described.FIG.7is a flowchart showing an example of a processing procedure of the program synthesis processing.

In step S301, the program synthesis unit13takes the similar code to be a synthesized code. The processing performed in step S301is merely a change of the name.

Subsequently, loop processing L1that includes steps S302and S303is executed for each synthesized code. In the following description, a synthesized code for which the loop processing L1is performed will be referred to as a “target code”. When the loop processing L1is executed for the first time, the synthesized code is the single similar code.

In step S302, the synthesized program execution unit14generates a program (hereinafter referred to as a “synthesized program”) in an executable form by performing compiling, linking, and the like on the target code.

Subsequently, the synthesized program execution unit14executes the synthesized program (hereinafter referred to as the “target synthesized program”) by inputting an input value of each input-output example included in an input-output example set that is prepared in advance, to the target synthesized program, and obtains an output value for each input-output example (step S303) The input-output example set is information that indicates conditions to be satisfied by the target program with respect to input and output, and is set in advance and stored in the auxiliary storage device102, for example.

FIG.8is a diagram showing an example of the input-output example set. The following is the data structure of the input-output example set shown inFIG.8, which is written in a form that is based on the BNF notation.<input-output example set>::=<input-output example>+<input-output example>::=<input example><output example><input example>::=input value+<output example>::=output value+

That is, the input-output example set includes one or more input-out examples. Each input-output example is a pair of an input example and an output example. The input example is one or more input values, and the output example is one or more output values.

For example, in a case where the input-output example set includes M input-output examples, in step S303, the synthesized program execution unit14executes the target synthesized program for each of M input values by inputting the input values, and obtains M output values.

When the loop processing L1has ended, the input-output result determination unit15determines whether there is a synthesized program for which all output values match output examples of input-output examples to which input values corresponding to the output values belong (step S304). That is, it is determined whether there is a synthesized program for which all output values obtained in step S303were as expected (correct), among synthesized programs for which the loop processing L1has been performed. It should be noted that when step S304is executed for the first time, the loop processing L1is performed on only one synthesized program generated based on the similar code. Accordingly, in this case, the determination is performed on input-output results of this synthesized program in step S304.

If there is no synthesized program that satisfies the condition of step S304(No in step S304), the program synthesis unit13executes synthesized code change processing (step S305). In the synthesized code change processing, a plurality of (N) synthesized codes are generated by partially changing the original synthesized code. For example, a genetic algorithm may be used to partially change the synthesized code. That is, a genetic operation may be performed N times on the synthesized code of the previous generation to generate N synthesized codes of the next generation. Here, N represents the number of individuals (source codes) of a single generation of the genetic algorithm. At this time, each synthesized code to which the genetic algorithm is applied is expressed using a tree structure in which an operator serves as a parent node and a variable, a constant, or an operator for which an operation is performed using the operator serves as a child node, for example, and the genetic operation is performed on a subtree of the tree structure. A pass rate of output values (a rate at which the output values were correct) may be used in evaluation for selecting individuals on which the genetic operation is performed N times.

For example, program components included in a program component list that is stored in the auxiliary storage device102in advance are used as candidates that replace a portion of the synthesized code of the previous generation in mutations.

FIG.9is a diagram showing an example of the program component list. The following is the data structure of the program component list shown inFIG.9, which is written in a form that is based on the BNF notation.<program component list>::=program component+

That is, the program component list includes one or more program components (source codes of the program components). InFIG.9, the program components are categorized into constants and methods. Here, a single constant corresponds to a single program component, and a single method corresponds to a single program component. That is, each unit surrounded by a dashed line inFIG.9corresponds to a unit of a single program component.

It should be noted that when step S305is executed for the first time, the individual (synthesized code) of the previous generation is the single similar code. Accordingly, in this case, N identical synthesized codes can be generated by copying the similar code, and the genetic operation can be performed N times on the N synthesized codes. As a result, N new synthesized programs are generated.

FIG.10is a diagram showing an example of synthesized codes generated through the synthesized code change processing. As shown inFIG.10, N synthesized codes are generated as a result of synthesis processing being performed once.

It should be noted that an existing library such as DEAP (https://deap.readthedocs.io/en/master/) may be used for program synthesis processing in which the genetic algorithm is used.

Subsequently, the loop processing L1and the following processing are executed for the N synthesized codes. Accordingly, in this case, steps S302and S303are executed N times.

On the other hand, if there is a synthesized program that satisfies the condition of step S304(Yes in step S304), the input-output result determination unit15outputs the source code (synthesized code) of the synthesized program (step S306). That is, the synthesized program is determined to be the target program. If there are a plurality of synthesized programs that satisfy the condition of step S304, source codes of the respective synthesized programs can be output.

For example, in a case where the three input-output examples shown inFIG.8are all of the input-output examples constituting the input-output example set, the second synthesized code from the left inFIG.10is output as the target program (source code of the target program).

As described above, according to the present embodiment, a program that is expected to satisfy a specification of a program is automatically generated using two types of information, i.e., the specification (character string) of the program written in natural language and input-output examples. That is, according to the present embodiment, a source code of a program that has a structure close to the structure required for the specification of the target program (intention of the creator) is found from the search data set16that includes source codes and specifications of programs by using the machine learning model that has been caused to learn a relationship between natural language describing a specification of a program and similarity of the structure of the program, and then a program is repeatedly modified (changed) based on the found source code until a program that satisfies all input-output examples is generated. As a result, according to the present embodiment, it is possible to increase the possibility of the desired program (i.e., program that satisfies desired input-output examples) being automatically generated, when compared to conventional technologies.

It should be noted that in the present embodiment, the similar code is an example of a first program. The similar code search unit12is an example of a search unit. The program synthesis unit13is an example of a change unit. The target program is an example of a second program.

Although an embodiment of the present invention has been described in detail, the present invention is not limited to the specific embodiment, and various alterations and changes can be made within the scope of the gist of the present invention described in the claims.

REFERENCE SIGNS LIST

10Program generation device11Training unit12Similar code search unit13Program synthesis unit14Synthesized program execution unit15Input-output result determination unit16Search data set100Drive device101Recording medium102Auxiliary storage device103Memory device104CPU105Interface device106Display device107Input deviceB Bus