inductive-programming.org

Content

• Main
• Introduction
• People
• Resources
  • Systems
  • Repository
  • Publications
• Events
• Links
• News

Introduction

Background

Inductive programming incorporates all approaches which are concerned with learning programs or algorithms from incomplete specifications. Possible inputs in an IP system are

1. a set of training inputs and corresponding outputs or an output evaluation function, describing the desired behavior of the intended program,
2. traces or action sequences which describe the process of calculating specific outputs,
3. constraints for the program to be induced concerning its time efficiency or its complexity,
4. various kinds of background knowledge such as standard data types, predefined functions to be used, program schemes or templates describing the data flow of the intended program,
5. heuristics for guiding the search for a solution or other biases.

Output of an IP system is a program in some arbitrary programming language containing conditionals and loop- or recursive control structures.

Approaches

Automatic induction of programs from input/output examples is an active area of research since the sixties and of interest for machine learning research as well as for automated software engineering. In the early days of inductive programming research there several approaches to the synthesis of Lisp programs from examples or traces were proposed.

Due to only limited progress, interest decreased in the mid-eighties and research focused on inductive logic programming (ILP) instead. Although ILP proved to be a powerful approach to learning relational concepts, applications of learning recursive clauses had only moderate success.

Learning recursive programs from examples is also investigated in genetic programming and other forms of evolutionary computation. Here again, functional programs are learned from sets of positive examples together with an output evaluation function which specify the desired input/output behavior of the program to be learned.

In the recent years, the classical (Summers like) approaches have been resumed and advanced with great success. Therefore the synthesis problem has been reformulated on the background of constructor-based term rewriting systems taking into account modern techniques of functional programming, as well as moderate use of search-based strategies and usage of background knowledge as well as automatic invention of subprograms. A fourth approach is learning recursive programs in the context of grammar inference.

Current Research

Currently, there is no single prominent approach to inductive program synthesis. Instead, research is scattered over the different approaches. Nevertheless, inductive programming is a research topic of crucial interest for machine learning and artificial intelligence in general. The ability to generalize a program – containing control structures as resursion or loops – from examples is a challenging problem which calls for approaches going beyond the requirements of algorithms for concept learning. Pushing research forward in this area can give important insights in the nature and complexity of learning as well as enlarging the field of possible applications.

Application Areas

Typical areas of application where learning of programs or recursive rules are called for, are first in the domain of software engineering where structural learning, software assistants and software agents can help to relieve programmers from routine tasks, give programming support for endusers, or support of novice programmers and programming tutor systems. Further areas of application are language learning, learning recursive control rules for AI-planning, learning recursive concepts in web-mining or for data-format transformations.