Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach
Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach
复制标题
函数式程序的归纳综合：一种基于解释的泛化方法
DOI：
10.1023/a:1008797606116
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Ute Schmid
中科院分区：
文献类型：
--
作者：
E. Kitzelmann;Ute Schmid
我们描述了一种从输入/输出示例中递归方程的归纳综合方法的方法，该方法基于经典的两步方法来诱导Summers功能LISP程序（1977）。第一步，I/O-例子被重写为基于数据型理论的相应输入的输出来解释输出。这些迹线可以集成到一个有条件的表达式中，该条件表达式代表一个非恢复程序。在第二步中，该初始程序术语通过搜索术语中的句法规律性将其推广到递归方程中。我们的方法在几个方面扩展了古典工作。最重要的扩展是我们能够在一个合成步骤中诱导一组递归方程，该方程可能包含一个以上的递归调用，并且还会自动引入所需的参数。
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.