Inductive Program Synthesis

Theoretic and Algorithmic Foundations of the Induction of Functional Programs


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. We focus on analytical strategies to learning of recursive functional programs from few well-choosen I/O-examples. In our approach, programs are represented as constructor term rewriting systems (CSs) containing recursive rules. I/O-examples are a set of pairs of terms. The induction is based on detecting syntactic regularities between the example-terms. Our current approach is based on an algorithm for inducing programs 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.
Description
current: past:
  • Martin Mühlpfordt
  • Heike Pisch
Collaborators

Forschungsförderung 2007: DFG-Projekt "Effiziente Algorithmen zur induktiven Programmsynthese".

Grant
  • Kitzelmann, E.; Schmid, U.: Induction of Functional Programs based on Relations between I/O Examples. (Poster Abstract). 29th Annual German Conference on Artificial Intelligence, Bremen, June 14-19, 2006.
  • Kitzelmann, E.; Schmid, U.: Inductive Synthesis of Functional Programs -- an Explanation Based Generalization Approach. Journal of Machine Learning Research, 7(Feb), 429-454. [draft, pdf]
  • Kitzelmann, E.; Schmid, U.: An EBG Approach to the Inductive Synthesis of Functional Programs. ICML 2005 Workshop "Approaches and Applications of Inductive Programming", Bonn, Germany, 7-11 August, 2005, pp. 15--27. [pdf, 12 pages]
  • Schmid, U. (2003). Inductive Synthesis of Functional Programs -- Learning Domain-Specific Control Rules and Abstract Schemes. Springer, LNAI 2654. (Based on my habilitation thesis, Mai 2001). [GZipped Postscript, 447 pages] [pdf, 447 pages] [Title page, ps]
  • Kitzelmann, E., Schmid, U., Mühlpfordt, M., and Wysotzki, F. (2002). Folding of finite program terms to recursive program schemes. IEEE International Symposium 'Intelligent Systems', Bulgaria, September 10-12, 2002 (Proceedings Volume 1, pp. 144-149), IEEE Press. [Postscript, 6 pages]
  • Kitzelmann, E., Schmid, U., Mühlpfordt, M., and Wysotzki, F. (2002). Inductive synthesis of functional programs. In J. Calmet, B. Benhamou, O. Caprotti, L. Henocque, V. Sorge (Eds.), Artificial Intelligence, Automated Reasoning, and Symbolic Computation, Joint International Conference, AISC 2002 and Calculemus 2002 Marseille, France, July 1-5, 2002, pp. 26-37, Springer, LNAI 2385. [Postscript, 12 pages]
Publications

Inductive Program Synthesis as an Approach to Cognitive Modeling of Learning From Problem Solving Experience

IPAL Homepage Project Site
DFG-research scholarship (12 month), working on "Combining Inductive Program Synthesis with Planning and Analogical Reasoning" at Carnegie Mellon University, Pittsburgh, PA, invited by Jaime Carbonell (10/98-3/99; 3/00-8/00) Past Grant
The new web-based gui Hippal is under construction (work by Martin Beckmann, Christopher Lörken) Current Work

Application of Inductive Synthesis Techniques to Enduser Programming Support

Automated synthesis of programs is a central goal of research in automated programming. Inductive program synthesis means that a recursive program is constructed from a small set of examples describing the desired input/output behavior which are generalized into the searched for program. Existing, fully automated approaches are mostly restricted to very simple problems. In our own approach we split the synthesis problem into two subproblems – generating a non-recursive trace and generalizing over this trace (folding). For solving the first part we work with knowledge based methods (e.g., AI planning), the second part can be solved with purely syntactical pattern matching. In a diploma thesis, this approach was applied to the synthesis of XSL transformations with recursive template applications. Based on the first, positivew results of this work, the approach will be further developped to be applied to a larger set of synthesis tasks with practical relevance. Description
current: past: Collaborators
  • Schmid, U. and Waltermann, J. (2004). Automatic Synthesis of XSL-Transformations from Example Documents. IASTED International Conference on Artificial Intelligence and Applications (AIA 2004), Innsbruck, Austria, February 16-18, 2004. [pdf, 6 pages]
  • Jens Waltermann (diploma student, mathematics, Osnabrück): Automatische Generierung von rekursiven Programmen aus Beispielen als Anwendung der induktiven Programmsynthese auf XSL [Web-Page] (February 2003)
Publications