Combining Inductive Program Synthesis with Problem Solving and Analogical Reasoning
[DPlan]
[TFold]
[AProg]
With our approach to combine inductive program synthesis techniques with AI-methods for problem solving/planning, analogical reasoning and learning we pursue two goals:
- An engineering goal: enlarging the scope of (automatically) inferable programs, and
- a cognitive science goal: modeling the human ability to learn from problem solving experience.
While during the last decade work in the field of inductive program synthesis is mostly done in the framework of inductive logic programming we investigate
program synthesis in a functional context (going back to the roots).
The general outline of our approach is as follows:
- Constructing initial programs by universal planning:
Mimicking a human programmer simulating the transformations of some example inputs into the desired output; mimicking a human problem solver gaining hands-on experience with a problem of fixed complexity
(sorting lists of zero, one, two and three elements; solving the Tower of Hanoi puzzle with three discs)
- Generalizing initial programs to recursive program schemes:
Mimicking a human programmer extracting the cyclic structure of the current programming problem; mimicking a human problem solver infering a more general strategy from example solutions
(inferring a sort-program for lists of arbitraty length; inferring a general rule to solve the Tower of Hanoi puzzle with n discs)
- Using already acquired knowledge to deal with new (programming) problems by analogical reasoning:
Mimicking program reuse by human programmers; mimicking analogical probelm solving
- Generalizing over the common structure of solved problems to acquire more general knowledge structures.
Currently we are working at the following aspects:
- Development and theoretical evaluation of synthesis algorithms
- Bridging the gap between planning and program synthesis
- Getting clearer insights into the mechanism of adaptation of non-isomorphical source problems (programs) by psychological experiments and by developing according algorithms.
Please refer to Publications for papers covering these topics.
Implementations:
- Planning: DPlan
- Program Synthesis/Folding: TFold
- Generalization of Program Schemes/Programming by Analogy: AProg
- A first prototype, implemented in student projects under survey of Ute Schmid and integrated by Mark Müller: IPAL (a system that integrates Inductive program synthesis, Problemsolving, and Analogical Learning) (1996).
(schmid, 23/07/01)