Effiziente Algorithmen zur induktiven Programmsynthese

点击翻译按钮获取中文摘要

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.