Further Decimating the Inductive Programming Search Space with Instruction Digrams
This is an incremental improvement for researchers in inductive programming, specifically addressing search space constraints.
The paper tackled the problem of reducing the inductive programming search space by using instruction digrams as a heuristic, resulting in further reductions by several orders of magnitude and enabling the generation of larger programs.
Overlapping instruction subsets derived from human originated code have previously been shown to dramatically shrink the inductive programming search space, often by many orders of magnitude. Here we extend the instruction subset approach to consider direct instruction-instruction applications (or instruction digrams) as an additional search heuristic for inductive programming. In this study we analyse the frequency distribution of instruction digrams in a large sample of open source code. This indicates that the instruction digram distribution is highly skewed with over 93% of possible instruction digrams not represnted in the code sample. We demonstrate that instruction digrams can be used to constrain instruction selection during search, further reducing size of the the search space, in some cases by several orders of magnitude. This significantly increases the size of programs that can be generated using search based inductive programming techniques. We discuss the results and provide some suggestions for further work.