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
- Title:
- The effect of distance metrics in a general purpose synthesizer: An empirical study on integer domain imperative programs. (22nd November 2021)
- Main Title:
- The effect of distance metrics in a general purpose synthesizer: An empirical study on integer domain imperative programs
- Authors:
- Correia, Alexandre R. S.
Iyoda, Juliano M.
Mota, Alexandre C. - 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 sameAbstract: 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. … (more)
- Is Part Of:
- Software, practice & experience. Volume 52:Number 5(2022)
- Journal:
- Software, practice & experience
- Issue:
- Volume 52:Number 5(2022)
- Issue Display:
- Volume 52, Issue 5 (2022)
- Year:
- 2022
- Volume:
- 52
- Issue:
- 5
- Issue Sort Value:
- 2022-0052-0005-0000
- 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 - Journal URLs:
- http://onlinelibrary.wiley.com/ ↗
- DOI:
- 10.1002/spe.3054 ↗
- Languages:
- English
- ISSNs:
- 0038-0644
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 8321.453000
British Library DSC - BLDSS-3PM
British Library STI - ELD Digital store - Ingest File:
- 21234.xml