An introduction to inductive programming

The research field of inductive programming is concerned with the design of algorithms for learning computer programs with complex flow of control (typically recursive calls) from incomplete specifications such as examples. We introduce a basic algorithmic approach for inductive programming and illustrate it with three systems: dialogs learns logic programs by combining inductive and abductive reasoning; the classical thesys system and its extension igor1 learn functional programs based on a recurrence detection mechanism in traces; igor2 learns functional programs over algebraic data-types making use of constructor-term rewriting systems. Furthermore, we give a short history of inductive programming, discuss related approaches, and give hints about current applications and possible future directions of research. A short, non-technical version of this paper appears in C. Sammut, editor, Encyclopedia of Machine Learning, Springer–Verlag, forthcoming. The paper was written while the first author was on sabbatical in 2006/2007 at Sabancı University in İstanbul, Turkey.