Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach
E. Kitzelmann, and U. Schmid. Journal of Machine Learning Research, (2006)Revised version of~KiSc05.
Abstract
We describe an approach to the inductive synthesis of recursive equations from input/output-examples which is based on the classical two-step approach to induction of functional Lisp programs of Summers (1977). In a first step, I/O-examples are rewritten to traces which explain the outputs given the respective inputs based on a datatype theory. These traces can be integrated into one conditional expression which represents a non-recursive program. In a second step, this initial program term is generalized into recursive equations by searching for syntactical regularities in the term. Our approach extends the classical work in several aspects. The most important extensions are that we are able to induce a set of recursive equations in one synthesizing step, the equations may contain more than one recursive call, and additionally needed parameters are automatically introduced.
Description
Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach
%0 Journal Article
%1 KitzelmannSc06a
%A Kitzelmann, Emanuel
%A Schmid, Ute
%C Cambridge, MA, USA
%D 2006
%I MIT Press
%J Journal of Machine Learning Research
%K analytical_ip article ebg ifp igor1 induction inductive_programming program_synthesis recursive_program_schemes
%P 429--454
%T Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach
%U http://jmlr.csail.mit.edu/papers/v7/kitzelmann06a.html
%V 7
%X We describe an approach to the inductive synthesis of recursive equations from input/output-examples which is based on the classical two-step approach to induction of functional Lisp programs of Summers (1977). In a first step, I/O-examples are rewritten to traces which explain the outputs given the respective inputs based on a datatype theory. These traces can be integrated into one conditional expression which represents a non-recursive program. In a second step, this initial program term is generalized into recursive equations by searching for syntactical regularities in the term. Our approach extends the classical work in several aspects. The most important extensions are that we are able to induce a set of recursive equations in one synthesizing step, the equations may contain more than one recursive call, and additionally needed parameters are automatically introduced.
@article{KitzelmannSc06a,
abstract = {We describe an approach to the inductive synthesis of recursive equations from input/output-examples which is based on the classical two-step approach to induction of functional Lisp programs of Summers (1977). In a first step, I/O-examples are rewritten to traces which explain the outputs given the respective inputs based on a datatype theory. These traces can be integrated into one conditional expression which represents a non-recursive program. In a second step, this initial program term is generalized into recursive equations by searching for syntactical regularities in the term. Our approach extends the classical work in several aspects. The most important extensions are that we are able to induce a set of recursive equations in one synthesizing step, the equations may contain more than one recursive call, and additionally needed parameters are automatically introduced.},
added-at = {2010-04-21T22:13:16.000+0200},
address = {Cambridge, MA, USA},
author = {Kitzelmann, Emanuel and Schmid, Ute},
biburl = {https://www.bibsonomy.org/bibtex/241c72a03ba80767af6f77376acdbeb02/emanuel},
description = {Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach},
interhash = {952e3b17d93c05181e64bfc6a0a3960a},
intrahash = {41c72a03ba80767af6f77376acdbeb02},
journal = {Journal of Machine Learning Research},
keywords = {analytical_ip article ebg ifp igor1 induction inductive_programming program_synthesis recursive_program_schemes},
note = {Revised version of~\cite{KiSc05}},
pages = {429--454},
pdf = {http://www.cogsys.wiai.uni-bamberg.de/publications/jmlr06.pdf},
publisher = {MIT Press},
timestamp = {2010-04-21T22:13:17.000+0200},
title = {Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach},
url = {http://jmlr.csail.mit.edu/papers/v7/kitzelmann06a.html},
volume = 7,
year = 2006
}