Inducing Constructor Systems from Example-Terms by Detecting Syntactical Regularities |
| |
Authors: | Emanuel Kitzelmann Ute Schmid |
| |
Affiliation: | aDepartment of Information Systems and Applied Computer Science, University of Bamberg, 96045 Bamberg, Germany |
| |
Abstract: | We present a technique for inducing functional programs from few, well chosen input/output-examples (I/O-examples). Potential applications for automatic program or algorithm induction are to enable end users to create their own simple programs, to assist professional programmers, or to automatically invent completely new and efficient algorithms. In our approach, functional programs are represented as constructor term rewriting systems (CSs) containing recursive rules. I/O-examples for a target function to be implemented are a set of pairs of terms (F(ii),oi) meaning that F(ii)—denoting application of function F to input ii—is rewritten to oi by a CS implementing the function F. Induction is based on detecting syntactic regularities between example terms. In this paper we present theoretical results and describe an algorithm for inducing CSs over arbitrary signatures/data types which consist of one function defined by an arbitrary number of rules with an arbitrary number of non-nested recursive calls in each rule. Moreover, we present empirical results based on a prototypical implementation. |
| |
Keywords: | inductive program synthesis rule-based programming functional programming constructor systems |
本文献已被 ScienceDirect 等数据库收录! |
|