Patent ID: 12236247

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 program synthesis unit11, a synthesized program execution unit12, an input-output result determination unit13, and a constraint check unit14. These units are realized through processing that one or more programs installed in the program generation device10cause the CPU104to execute.

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.

In step S101, the program synthesis unit11generates source codes (hereinafter referred to as “synthesized codes”) of a plurality of (N) programs by, for example, randomly combining and compositing one or more program components included in a program component list that is stored in the auxiliary storage device102, for example.

FIG.4is a diagram showing an example of the program component list. The following is the data structure of the program component list shown inFIG.4, which is written in a form that is based on the BNF (Backus-Naur form) 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.4, 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.4corresponds to a unit of a single program component.

In step S101, processing for generating a single synthesized code by selecting a plurality of program components at random and compositing the plurality of program components is repeated N times. As a result, N synthesized codes are generated. It should be noted that compositing program components means combining calculations of the plurality of program components, and can be performed using a known technology such as the technology described in NPL 1, for example. For example, each program component can be 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, and a node in the tree structure of a program component can be replaced with the tree structure of another program component to composite these program components. It should be noted that similarly to the program components, a synthesized code includes a definition of taking a value as input, executing a calculation relating to the input value, and outputting a calculation result of the value.

Subsequently, loop processing L1 that includes steps S102and S103is executed for each synthesized code. In the following description, a synthesized code for which the loop processing L1 is performed will be referred to as a “target code”.

In step S102, the synthesized program execution unit12generates 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 unit12executes the synthesized program (hereinafter referred to as the “target synthesized program”) by inputting each input-output example included in an input-output example set that is prepared in advance, to the target synthesized program, and obtains output for each input-output example (step S103). The input-output example set is information that indicates conditions to be satisfied by the program to be generated (hereinafter referred to as the “target program”) with respect to input and output, and is set in advance and stored in the auxiliary storage device102, for example.

FIG.5is 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.5, 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 S103, the synthesized program execution unit12executes the target synthesized program for each of M input values by inputting the input values, and obtains M output values.

When the loop processing L1 has ended, the input-output result determination unit13determines 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 S104). That is, it is determined whether there is a synthesized program for which all output values obtained in step S103were as expected (correct), among synthesized programs for which the loop processing L1 has been performed.

If there is no synthesized program that satisfies the condition of step S104(No in step S104), the program synthesis unit11executes synthesized code change processing (step S105). 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 the program component list are used as candidates that replace a portion of the synthesized code of the previous generation in mutations.

FIG.6is a diagram showing an example of synthesized codes that are generated through the synthesized code change processing. As shown inFIG.6, 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 L1 and the following processing are executed for the N synthesized codes. Accordingly, in this case, steps S102and S103are executed N times.

On the other hand, if there is at least one synthesized program (hereinafter referred to as an “input-output pass program”) that satisfies the condition of step S104(Yes in step S104), the loop processing L1 ends and the procedure proceeds to step S106. That is, in the loop processing L1, an input-output pass program that satisfies the input-output example set is automatically generated as a result of a partial change of the synthesized code being repeated (the synthesized code being cumulatively changed portion by portion) until a program that satisfies the input-output examples generated in advance is generated. For example, in a case where the three input-output examples shown inFIG.5are all of the input-output examples constituting the input-output example set, the first and second synthesized codes from the left inFIG.6are input-output pass programs.

In step S106, the constraint check unit14generates one or more input values at random for the input-output pass program within the range of an input constraint that is one of constitutional elements of a constraint (constraint condition) that is input by the user with respect to input and output of the target program. That is, one or more input values that satisfy the input constraint are generated. It is preferable that many input values are generated to increase the accuracy of determining that the input-output pass program satisfies the constraint.

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

That is, the constraint is a pair of a single input constraint and a single output constraint. However, the single input constraint or the single output constraint may be constituted by a plurality of conditional expressions.

When the input constraint is as shown inFIG.7, in step S106, a plurality of input values greater than 0 are generated at random.

Subsequently, the constraint check unit14executes loop processing L2 that includes step S107for each of the input values generated in step S106. In the following description, an input value for which the processing is performed will be referred to as a “target input value”.

In step S107, the constraint check unit14executes the input-output pass program by inputting the target input value to the input-output pass program, and obtains an output value. In a case where there are a plurality of input-output pass programs, an output value for the same input value is acquired with respect to each of the input-output pass programs. The acquired output values are recorded in the memory device103in association with the respective input-output pass programs.

Ina case where K input values are generated in step S106, step S107is executed for the K input values.

When the loop processing L2 has ended, the constraint check unit14determines whether there is an input-output pass program for which all output values (all of K output values) satisfy the output constraint (whether or not all output values of any of the input-output pass programs satisfy the output constraint) (step S108). If there is no input-output pass program that satisfies the condition of step S108(No in step S108), the processing performed in step S105and the following processing are repeated. That is, synthesized programs that differ from the previous ones are generated, and the loop processing L1 and the following processing are executed for the synthesized programs.

If there is an input-output pass program that satisfies the condition of step S108(Yes in step S108), the constraint check unit14outputs the source code (synthesized code) of the input-output pass program (step S109). That is, the synthesized program is determined to be the target program. If there are a plurality of input-output pass programs that satisfy the condition of step S108, source codes of the respective input-output pass programs can be output.

For example, in a case where input values generated in step S107are the following three values {1,2,98}, output values of an input-output pass program that is based on the leftmost synthesized code shown inFIG.6are {1,0,0}, and some of the output values do not satisfy the output constraint. On the other hand, output values of an input-output pass program that is based on the second synthesized code from the left inFIG.6are {1,4,9604}, and all of the output values satisfy the output constraint. Accordingly, in this case, the input-output pass program based on the second synthesized code from the left inFIG.6is determined to be the target program.

As described above, according to the present embodiment, a program that satisfies not only input-output examples but also constraints regarding input and output is automatically generated. Accordingly, the possibility of the desired program being automatically generated can be increased. Specifically, not only validity of each synthesized program obtained by compositing program components is checked using input-output examples, but also input values are automatically generated at random within the range of a given input constraint and are input to each synthesized program to determine whether all synthesized programs satisfy the constraint regarding output, and therefore, inappropriate programs can be excluded.

For example, assume that the desired program is a program for finding the area of a square. Assume that the user has given an input value 2 and an output value 4 as an input-output example. In this case, a program. “x*x” has to be output, but the input-output example is also satisfied by a program “6−x”, and this program may be output as a program that satisfies the input-output example. In the case of this example, both input and output need to be always positive (there are neither negative lengths nor negative areas). Accordingly, the user inputs a constraint regarding input and output such as {input x>0, output y>0}, and the validity of each synthesized program is determined using not only the input-output example but also the constraint. Specifically, various values are generated at random within the range of x>0, each synthesized program is executed using the values, and it is determined whether or not the output value y always satisfies y>0. In the case of the program “6−x”, for example, y=−2 when x=8, which does not satisfy the constraint, and therefore, the program is determined to be inappropriate.

In the present embodiment, the program synthesis unit11is an example of a generation unit. The constraint check unit14is an example of a determination unit.

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 device11Program synthesis unit12Synthesized program execution unit13Input-output result determination unit14Constraint check unit100Drive device101Recording medium102Auxiliary storage device103Memory device104CPU105Interface device106Display device107Input deviceB Bus