The Impact of Step Limits on Generalization and Stability in Software Synthesis

Software synthesisSoftware synthesis research has historically relied on tools such as step limits to handle undesired behavior like infinite loops. Here we explore the impact of different step limitsStep limits on several benchmark problems, and see that these limits do affect the evolved behaviors both in terms of generalization and stability. To assess stability Stability, we ran evolved programs with a range of step limits Step limits, and found several cases where programs failed to generalize with the step limit used during evolution, but generalized at other step limits Step limits. Two of our test problems evolved stable solutions in the sense that they correctly handled unseen test cases for all step limitsStep limits above a certain point, i.e., correctly computed the answer. Our other two test problems, however, sometimes evolved unstable solutions which only generalized (i.e., correctly handled unseen test cases) for specific step limits Step limits. These programs relied on the step limit to terminate, and would no longer generalize if the step limit was modified slightly. This indicates that step limitsStep limits can have a substantial impact on evolutionary performance, and suggests we need to revisit our notions of generalizationGeneralization in the context of evolutionary software synthesis Software synthesis.