News

End of project

The project expired with end of September 2010. The development of the Haskell Igor2 version was ceased.

10.11.2010
Igor2 version 0.8.0 uploaded

The latest Igor2 version 0.8.0 for Haskell is online as Cabal package and Win32 binary.

10.11.2010
AAIP09 Post-Proceedings at Springer

The AAIP Workshop Post-Proceedings have been published as Springer Lecture Notes in Computer Science (LNCS) volume 5812 (LNCS)

03.03.2010
PEPM@POPL 2010

Two appers have been accepted for oral presentation at the PEPM workshop on the POPL conference 2010 in Madrid.

25.01.2010
Article in HCAR 08

An article about IgorII appeared in the fifteenth edition of the "Haskell Communities and Activities Report"

01.12.2009
Visiting Researcher O. Monakhov

Oleg Monakhov from the Russian Academy of Sciences, Siberian Branch is visiting our group from 19th of Sept. to 21st of Nov. 2009, funded by DAAD.

19.09.2009
Visiting Researcher S. Katayama

Susumu Katayama from Miyzaki University Japan is visiting from 7th to 10th September. He was the host of Martin Hofmann who spent a two month research visit at his department in summer 2009, funded by the Japan Society for the Promotion of Science.

07.09.2009
Igor2 in Haskell

A first Haskell version of IgorII is available as cabal package in the Download section

18.05.2009
JSPS Fellowship granted

A research fellowship of the Japan Society for the Promotion of Science has been granted to Martin Hofmann. He will spent two month as a visiting researcher in the department of Susumu Katayama at the University of Miyazaki in Japan in summer 2009.

09.04.2009
Ray Kurzweil Prize

The Best Paper Prize at AGI09 has been awarded to N. Crossley, E. Kitzelmann, M. Hofmann, and U. Schmid for their paper Combining Analytical and Evolutionary Inductive Programming.

12.03.2009
AAIP'09

Our group, together with Rinus Plasmeijer, is organising the next workshop on Approaches and Applications of Inductive Programming 2009 (AAIP'09).

08.01.2009
Article in HCAR 08

An article about IgorII appeared in the fifteenth edition of the "Haskell Communities and Activities Report"

01.12.2008
Major Overhaul

The page has been updated, especially the Download and the Members section. New section Activities added.

20.11.2008
New example data

New example data for various IP systems (as used in AGI-09 paper submission) is now available in the download section.

06.11.2008
Publications updated

The list of publications has been updated

03.11.2008
Homepage online

This site is now online as official project homepage.

09.10.2007

The Project

The project expired with end of September 2010 and the development of the Haskell Igor2 version was ceased. The final report (Sorry, but German only) can be downloaded here.

Efficient Algorithms for Inductive Program Synthesis

Inductive program synthesis addresses the problem of constructing recursive programs from incomplete specifications, typically input/output examples. Genereally, two different approaches can be identified: search-based methods exhaustively generate hypotheses as syntactic correct programs and test them against the provided specification. Analytic methods work example-driven, i.e. they construct program hypotheses as least general generalisations over regularities in the specification. Goal of this proposal is the advancement of classical (Summers like) approaches for example-driven, analytical synthesis of functional programs. In contrast to approaches of inductive logic programming and evolutionary computation, which are mainly search-based, analytical approaches have the advantage that synthesis effort is considerably lower.

However, current approaches typically are restricted to structural problems (such as reversing of a list) and rely on simple hypothesis languages (such as linear recursive program schemes). By reformulating the synthesis problem 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 (e. g. evolutionary) strategies and usage of background knowledge we hope to gain an approach whose efficiency is comparable to classical approaches but whose scope goes well beyond these approaches.

The proposed approach guarantees that the induced programs are a minimal generalization over examples and terminate. Besides applications to synthesis problems reported in literature, we plan to apply our approach in the domain of end-user programming support.

In the first project phase (10/2007–09/2009) we prototypically implemented Igor2 as an analytical approach in Maude and compared it with positive results against competing systems. In the second project phase (10/2009–09/2011) we plan to port Igor2 to Haskell to allow synthesising higher-order functions. Thus, we can improve the capabilities of Igor2 even further. Simultaneously, we plan to introduce heuristics to guide the generation of partial hypotheses to improve efficiency. Analytical inductive programming should, apart from support for enduser-programming, open programming assistance for the development of functional programs as a new application domain.

Effiziente Algorithmen zur Induktiven Programsynthese

Induktive Programmsynthese addressiert das Problem der Konstruktion von rekursiven Programmen aus unvollständigen Spezifikationen, meist aus Eingabe-/Ausgabe-Beispielen. Es können zwei prinzipielle Ansätze unterschieden werden: Suchbasierte Verfahren erzeugen Hypothesen in Form syntaktisch korrekter Programme und testen die Programme gegen die Spezifikation. Analytische Verfahren arbeiten beispielgetrieben, Programm-Hypothesen werden als kleinste Generalisierungen über Regularitäten der Spezifikation konstruiert. Ziel des Vorhabens ist die Weiterentwicklung von klassischen (Summers-artigen) Verfahren zur analytischen, beispielgetriebenen Synthese funktionaler Programme. Im Gegensatz zu Verfahren der induktiven logischen Programmierung und evolutionären Ansätzen, die vor allem suchbasiert arbeiten, haben analytische Verfahren den Vorteil, dass der Syntheseaufwand deutlich geringer ist.

Allerdings sind die bisher verfügbaren Ansätze häufig auf strukturelle Probleme (z. B. Umdrehen einer Liste) und einfache Hypothesensprachen (z. B. linear rekursive Programmschemata) eingeschränkt. Durch Reformulierung des Syntheseproblems auf der Basis von konstruktorbasierten Termersetzungssystemen, Berücksichtigung moderner Techniken der funktionalen Programmierung, sowie eingeschrünkten Einsatz von suchbasierten (z. B. evolutionären) Strategien und Berücksichtigung von Hintergrundwissen soll es gelingen, die Effizienz klassischer Ansätze weitgehend beizubehalten und gleichzeitig deren Mächtigkeit zu erhöhen.

Der vorgeschlagene Syntheseansatz garantiert, dass die konstruierten Programme eine minimale Generalisierung über die Beispiele darstellen und terminieren. Neben der Anwendung auf bekannte Syntheseprobleme aus der Literatur, soll das Verfahren zur Unterstützung der Endnutzer-Programmierung eingesetzt werden.

In der ersten Projekthase (10/2007–09/2009) haben wir Igor2 als analytischen Ansatz zur induktiven funktionalen Programmierung prototypisch in Maude implementiert und mit positiven Ergebnissen mit konkurrierenden Ansätzen verglichen. In der zweiten Projektphase (10/2009–09/2011) soll Igor2 nach Haskell portiert werden, um die Synthese von Programmen mit Funktionen höherer Ordnung zu ermöglichen. Dadurch kann die Mächtigkeit von Igor2 weiter erhöht werden. Gleichzeitig sollen Heuristiken zur Steuerung der Generierung von partiellen Hypothesen eingeführt werden, um die Effizienz aufrechtzuerhalten. Neben der Unterstützung von Endnutzerprogrammierung soll die Nutzung analytischer induktiver Programmierung als Programmier-Assistenz bei der Entwicklung funktionaler Programme als weiterer Anwendungsbereich erschlossen werden.