The effect of distance metrics in a general purpose synthesizer: An empirical study on integer domain imperative programs

摘要

Context Program synthesis is the task of automatically finding a program that satisfies the user intention. In previous work, we have developed a program synthesizer that integrates genetic algorithm with model finder. A genetic algorithm uses a fitness function to calculate how "distant to a solution" a given candidate program is. Researchers argue that different distance metrics for a fitness function may reveal behavioral differences in the genetic algorithm. Objective We have chosen five distance metrics as fitness functions to check whether they affect the synthesis task of five different integer domain imperative toy-programs which read/write integer values using fundamental syntactic constructs, such as while, if-then-else, and so forth. We have used input/output examples and sketches to constrain the search space of the candidate programs. Method A hypothesis test was proposed and experiments were conducted to observe the number of calls to the fitness function (x) and to measure the synthesis time (xst). Results Regarding x, the synthesizer found a solution for all five subjects after calling the fitness function the same amount of times. For xst, a one-way ANOVA was performed with a significance level of 5 (alpha=0.05). No significant differences were observed in both x and xst. Conclusion With these preliminary results, this study suggests that the discrete distance metric is the best choice, because it guides the search with the same effectiveness as the others and is not time consuming, and so forth. However, future experimentation with a larger search space will confirm or not this initial impression.