Little is known about program search spaces. It is often assumed they are vast and ill structured. However programs may not be as fragile as is commonly assumed. We can make a start by studying how the search spaces scale with respect to program size and parse tree depth.
Experiments suggest the distribution of fitness of programs, once some minimum size threshold has been exceeded, is approximately independent of program size. This can be proved for linear programs and for simple side effect free parse trees.
Analysis suggests size limits tend to match asymmetric problems while depth limits give a better bias for problems where all inputs are equally important. Our results suggest it may be possible to devise genetic operators with a better match to problems.