Effiziente Algorithmen zur induktiven Programmsynthese

• Applicant: Professorin Dr. Ute Schmid
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2007 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 42267097

Induktive Programmierung 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. In der ersten Projektphase 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 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.

• DFG Programme: Research Grants