Abstract
Inductive programming (IP)—the use of inductive reasoning methods for programming, algorithm design, and software development—is a currently emerging research field. A major subfield is inductive program synthesis, the (semi-)automatic construction of programs from exemplary behavior. Inductive program synthesis is not a unified research field until today but scattered over several different established research fields such as machine learning, inductive logic programming, genetic programming, and functional programming. This impedes an exchange of theory and techniques and, as a consequence, a progress of inductive programming. In this paper we survey theoretical results and methods of inductive program synthesis that have been developed in different research fields until today.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Partridge, D.: The case for inductive programming. Computer 30(1), 36–41 (1997)
Flener, P., Partridge, D.: Inductive programming. Automated Software Engineering 8(2), 131–137 (2001)
Schmid, U.: Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning. LNCS (LNAI), vol. 2654. Springer, Heidelberg (2003)
Summers, P.D.: A methodology for LISP program construction from examples. Journal of the ACM 24(1), 161–175 (1977)
Mitchell, T.M.: Machine Learning. McGraw-Hill, New York (1997)
McCarthy, J.: Recursive functions of symbolic expressions and their computation by machine, part i. Communications of the ACM 3(4), 184–195 (1960)
Smith, D.R.: The synthesis of LISP programs from examples: A survey. In: Biermann, A., Guiho, G., Kodratoff, Y. (eds.) Automatic Program Construction Techniques, pp. 307–324. Macmillan, Basingstoke (1984)
Jouannaud, J.P., Kodratoff, Y.: Program synthesis from examples of behavior. In: Biermann, A.W., Guiho, G. (eds.) Computer Program Synthesis Methodologies, pp. 213–250. D. Reidel Publ. Co. (1983)
Plotkin, G.D.: A note on inductive generalization. Machine Intelligence 5, 153–163 (1970)
Biermann, A.W.: The inference of regular LISP programs from examples. IEEE Transactions on Systems, Man and Cybernetics 8(8), 585–600 (1978)
Kitzelmann, E., Schmid, U.: Inductive synthesis of functional programs: An explanation based generalization approach. Journal of Machine Learning Research 7, 429–454 (2006)
Kitzelmann, E.: Analytical inductive functional programming. In: Hanus, M. (ed.) Logic-Based Program Synthesis and Transformation. LNCS, vol. 5438, pp. 87–102. Springer, Heidelberg (2009)
Muggleton, S.H., De Raedt, L.: Inductive logic programming: Theory and methods. Journal of Logic Programming 19, 20, 629–679 (1994)
Nienhuys-Cheng, S.-H., de Wolf, R.: Foundations of Inductive Logic Programming. LNCS (LNAI), vol. 1228. Springer, Heidelberg (1997)
Shapiro, E.Y.: Algorithmic Program Debugging. MIT Press, Cambridge (1983)
Quinlan, J.R., Cameron-Jones, R.M.: FOIL: A midterm report. In: Brazdil, P.B. (ed.) ECML 1993. LNCS, vol. 667, pp. 3–20. Springer, Heidelberg (1993)
Muggleton, S.H., Feng, C.: Efficient induction of logic programs. In: Proceedings of the First Conference on Algorithmic Learning Theory, Ohmsha, pp. 368–381 (1990)
Muggleton, S.H.: Inverse entailment and progol. New Generation Computing 13, 245–286 (1995)
Flener, P., Yilmaz, S.: Inductive synthesis of recursive logic programs: Achievements and prospects. The Journal of Logic Programming 41(2-3), 141–195 (1999)
Aha, D.W., Lapointe, S., Ling, C.X., Matwin, S.: Inverting implication with small training sets. In: Bergadano, F., De Raedt, L. (eds.) ECML 1994. LNCS, vol. 784, pp. 29–48. Springer, Heidelberg (1994)
Rios, R., Matwin, S.: Efficient induction of recursive prolog definitions. In: McCalla, G.I. (ed.) Canadian AI 1996. LNCS, vol. 1081, pp. 240–248. Springer, Heidelberg (1996)
Idestam-Almquist, P.: Efficient induction of recursive definitions by structural analysis of saturations. In: Advances in Inductive Logic Programming. IOS Press, Amsterdam (1996)
Furusawa, M., Inuzuka, N., Seki, H., Itoh, H.: Induction of logic programs with more than one recursive clause by analyzing saturations. In: Džeroski, S., Lavrač, N. (eds.) ILP 1997. LNCS, vol. 1297, pp. 165–172. Springer, Heidelberg (1997)
Mofizur, C.R., Numao, M.: Top-down induction of recursive programs from small number of sparse examples. In: Advances in Inductive Logic Programming. IOS Press, Amsterdam (1996)
Bergadano, F., Gunetti, D.: Inductive Logic Programming: From Machine Learning to Software Engineering. MIT Press, Cambridge (1995)
Flener, P.: Inductive logic program synthesis with DIALOGS. In: ILP 1996. LNCS, vol. 1314, pp. 175–198. Springer, Heidelberg (1997)
Jorge, A.M.G.: Iterative Induction of Logic Programs. PhD thesis, Departamento de Ciência de Computadores, Universidade do Porto (1998)
Ferri-Ramírez, C., Hernández-Orallo, J., Ramírez-Quintana, M.: Incremental learning of functional logic programs. In: Kuchen, H., Ueda, K. (eds.) FLOPS 2001. LNCS, vol. 2024, pp. 233–247. Springer, Heidelberg (2001)
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)
Koza, J.R., Andre, D., Bennett, F.H., Keane, M.A.: Genetic Programming III: Darwinian Invention & Problem Solving. Morgan Kaufmann, San Francisco (1999)
Wong, M., Mun, T.: Evolving recursive programs by using adaptive grammar based genetic programming. Genetic Programming and Evolvable Machines 6(4), 421–455 (2005)
Yu, T.: Hierarchical processing for evolving recursive and modular programs using higher-order functions and lambda abstraction. Genetic Programming and Evolvable Machines 2(4), 345–380 (2001)
Kahrs, S.: Genetic programming with primitive recursion. In: Proceedings of the 8th annual Conference on Genetic and Evolutionary Computation (GECCO 2006), pp. 941–942. ACM, New York (2006)
Binard, F., Felty, A.: Genetic programming with polymorphic types and higher-order functions. In: Proceedings of the 10th annual Conference on Genetic and Evolutionary Computation (GECCO 2008), pp. 1187–1194. ACM Press, New York (2008)
Hamel, L., Shen, C.: An inductive programming approach to algebraic specification. In: Proceedings of the 2nd Workshop on Approaches and Applications of Inductive Programming (AAIP 2007), pp. 3–14 (2007)
Olsson, J.R.: Inductive functional programming using incremental program transformation. Artificial Intelligence 74(1), 55–83 (1995)
Katayama, S.: Systematic search for lambda expressions. In: van Eekelen, M.C.J.D. (ed.) Revised Selected Papers from the Sixth Symposium on Trends in Functional Programming, TFP 2005, vol. 6, pp. 111–126. Intellect (2007)
Koopman, P., Alimarine, A., Tretmans, J., Plasmeijer, R.: GAST: Generic automated software testing. In: Peña, R., Arts, T. (eds.) IFL 2002. LNCS, vol. 2670. Springer, Heidelberg (2003)
Hofmann, M., Kitzelmann, E., Schmid, U.: A unifying framework for analysis and evaluation of inductive programming systems. In: Proceedings of the Second Conference on Artificial General Intelligence, Atlantis, pp. 55–60 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kitzelmann, E. (2010). Inductive Programming: A Survey of Program Synthesis Techniques. In: Schmid, U., Kitzelmann, E., Plasmeijer, R. (eds) Approaches and Applications of Inductive Programming. AAIP 2009. Lecture Notes in Computer Science, vol 5812. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11931-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-11931-6_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11930-9
Online ISBN: 978-3-642-11931-6
eBook Packages: Computer ScienceComputer Science (R0)