Effiziente Algorithmen zur induktiven Programmsynthese
Final Report Abstract
Im Projekt Effiziente Algorithmen zur induktiven Programmsynthese befassen wir uns mit der Entwicklung eines analytischen, beispielgetriebenen Ansatzes zur induktiven funktionalen Programmierung. Zunächst wurde das System IgorII entwickelt, in Maude implementiert, empirisch – im Vergleich zu anderen Systemen – evaluiert und in den Bereichen Endnutzer-Programmierung sowie Kognitive Modellierung angewendet. Darauf aufbauend wurde IgorII in Haskell portiert und um die Berücksichtigung von Funktionen höherer Ordnung erweitert. IgorII erhält als Eingabe eine kleine Menge von Ein-/Ausgabe-Beispielen. Daraus können sehr effizient und vollautomatisch linear-, baum- sowie wechselseitig rekursive Funktionen induziert werden. IgorII ist in der Lage, Hilfsfunktionen zu induzieren (necessary function invention) und kann Hintergrundwissen in Form von beispielhaft spezifizierten Prädikaten und Funktionen in den Syntheseprozess einbeziehen. Die Synthesezeiten liegen meist deutlich unter einer Sekunde. Die induzierten Programme sind garantiert korrekt bezüglich der gegebenen Beispielmenge und stellen die minimale Generalisierung über diese Menge dar. Igor2 ist über die Webseite des Projekts verfügbar. IgorII ist als conditional higher-order term rewriting System formalisiert und die Eigenschaften des Algorithmus wurden in diesem Rahmen charakterisiert. In umfangreichen empirischen Evaluationen konnte gezeigt werden, dass IgorII eine mit alternativen Systemen vergleichbare, häufig überlegene, Leistung erbringt. Im Vergleich zu suchbasierten Verfahren ist die Mächtigkeit von IgorII kaum eingeschränkt. Ein Repository von Problemen ist online verfügbar. Die Anwendbarkeit von IgorII wurde im Eclipse Plug-in AutoXSL erprobt. Hier werden aus Edit-Traces in XML-Dokumenten XSL Transformationen induziert, die dann auf das gesamte Dokument angewendet werden können. Die Portierung nach Haskell erlaubt die Nutzung von IgorII als Programmierassistent für die beispielgetriebene Induktion von Funktionen. Zudem konnte gezeigt werden, dass analytische induktive Programmierung auch in den Bereichen Problemlösen, Schließen und Sprachverarbeitung angewendet werden kann um über Regularitäten zu generalisieren.
Publications
- (2008). Analysis and evaluation of inductive programming systems in a higher-order framework. In A. Dengel, K. Berns, T. M. Breuel, F. Bomarius, & T. R. Roth-Berghofer (Eds.), KI 2008: Advances in Artificial Intelligence (p. 78-86). Berlin: Springer, LNAI 5243
Hofmann, M., Kitzelmann, E., & Schmid, U.
- (2009). An introduction to inductive programming. Artificial Intelligence Review, 29 (1), 45-62
Flener, P., & Schmid, U.
(See online at https://doi.org/10.1007/s10462-009-9108-7) - (2009). Analytical inductive functional programming. In M. Hanus (Ed.), Proceedings of the 18th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2008, Valencia, Spain) (Vol. LNCS 5438, p. 87-102). Springer
Kitzelmann, E.
- (2010). I/O Guided Detection of List Catamorphisms - Towards Problem Specific Use of Program Templaa tes in IP. In J. Gallagher & J. Voigtländer (Eds.), Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Madrid, 18.01.2010 - 22.01.2010) (p. 93-100). New York: ACM SIGPLAN
Hofmann, M., & Kitzelmann, E.
- (2010). IgorII - an analytical inductive functional programa ming system (tool demo). In J. Gallagher & J. Voigtländer (Eds.), Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Madrid, 18.01.2010 - 22.01.2010) (p. 29-32). ACM SIGPLAN
Hofmann, M.
