The effect of distance metrics in a general purpose synthesizer: An empirical study on integer domain imperative programs. (22nd November 2021)

• Record Type: Journal Article
• Authors: Correia, Alexandre R. S.; Iyoda, Juliano M.; Mota, Alexandre C.
• Is Part Of: Software, practice & experience. Volume 52:Number 5(2022)
• Page Start: 1294
• Page End: 1304
• Publication Date: 2021-11-22
• Subjects: distance metric -- fitness function -- genetic algorithm -- program synthesis; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.3054
• Languages: English
• ISSNs: 0038-0644

Abstract

Abstract: 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 ( x s t ). Results: Regarding x, the synthesizer found a solution for all five subjects after calling the fitness function the same amount of times. For x s t, a one‐way ANOVA was performed with a significance level of 5% ( α = 0 . 05 ). No significant differences were observed in both x and x s t . 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.