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 Kitzelmann06a
%A Kitzelmann, Emanuel
%A Schmid, Ute
%C Cambridge, MA, USA
%D 2006
%I MIT Press
%J Journal of Machine Learning Research
%K 2006 article automatic_programming explanation-based_generalization functional_programming igor1 induction inductive inductive_functional_programming inductive_inference inductive_learning inductive_program_synthesis inductive_programming myown programming published 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{Kitzelmann06a,
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 = {2007-10-17T15:28:39.000+0200},
address = {Cambridge, MA, USA},
author = {Kitzelmann, Emanuel and Schmid, Ute},
biburl = {https://www.bibsonomy.org/bibtex/241c72a03ba80767af6f77376acdbeb02/mh},
description = {Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach},
interhash = {952e3b17d93c05181e64bfc6a0a3960a},
intrahash = {41c72a03ba80767af6f77376acdbeb02},
issn = {1533-7928},
journal = {Journal of Machine Learning Research},
keywords = {2006 article automatic_programming explanation-based_generalization functional_programming igor1 induction inductive inductive_functional_programming inductive_inference inductive_learning inductive_program_synthesis inductive_programming myown programming published recursive_program_schemes},
pages = {429--454},
publisher = {MIT Press},
timestamp = {2007-10-17T15:28:40.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
}