Content deleted Content added
Added {{merge from}} tag to article (TW) |
Disambiguated: programming → Computer programming, Haskell → Haskell (programming language) |
||
Line 1:
{{merge from|Inductive functional programming|discuss=Talk:Inductive programming#Proposed merge with Inductive functional programming|date=February 2014}}
'''Inductive Programming''' (IP) is a special area of [[automatic programming]], covering research from [[artificial intelligence]] and [[Computer programming|programming]], which addresses [[machine learning|learning]] of typically [[declarative programming|declarative]] ([[logic programming|logic]] or [[functional programming|functional]]) and often [[recursion|recursive]] programs from incomplete specifications, such as input/output examples or constraints.
Depending on the programming language used, there are several kinds of inductive programming. [[Inductive functional programming]], which uses functional programming languages such as [[Lisp (programming language)|Lisp]] or [[Haskell (programming language)|Haskell]], and most especially [[Inductive logic programming]], which uses logic programming languages such as [[Prolog]] and other logical representations such as [[Description logics]], have been more prominent, but other (programming) language paradigms have also been used, such as [[constraint programming]] or [[probabilistic programming language|probabilistic programming]].
== Definition ==
Inductive programming incorporates all approaches which are concerned with learning programs or algorithms from incomplete ([[formal specification|formal]]) specifications. Possible inputs in an IP system are a set of training inputs and corresponding outputs or an output evaluation function, describing the desired behavior of the intended program, [[Tracing (software)|traces]] or action sequences which describe the process of calculating specific outputs, [[Constraint (mathematics)|constraints]] for the program to be induced concerning its time efficiency or its complexity, various kinds of background knowledge such as standard [[data type]]s, predefined functions to be used, program schemes or templates describing the data flow of the intended program, heuristics for guiding the search for a solution or other biases.
Line 18:
== History ==
Research on the inductive synthesis of recursive functional programs started in the early 1970s and was brought onto firm theoretical foundations with the seminal THESIS system of Summers<ref>{{cite journal|first1=P.D.|last1=Summers|title=A methodology for LISP program construction from examples|journal=J ACM|volume=24(1)|pages=161–175|year=1977}}</ref> and work of Biermann.<ref>{{cite journal|first1=A.W.|last1=Biermann|title=The inference of regular LISP programs from examples|journal=IEEE Trans Syst Man Cybern|volume=8(8)|pages=585–600|year=1978}}</ref>
These approaches were split into two phases: first, input-output examples are transformed into non-recursive programs (traces) using a small set of basic operators; second, regularities in the traces are searched for and used to fold them into a recursive program. The main results until the mid 1980s are surveyed by Smith.<ref>{{cite journal|first1=D.R.|last1=Smith|title=The synthesis of LISP programs from examples: a survey|editor1-first=A.W.|editor1-last=Biermann|editor2-first=G.|editor2-last=Guiho|publisher=Macmillan|journal=Automatic program construction techniques|pages=307–324|year=1984}}</ref> Due to limited progress with respect to the range of programs that could be synthesized, research activities decreased significantly in the next decade.
| |||