SPoC: Suchbasierte Pseudocode-zu-Code-Umsetzung

Wir betrachten die Aufgabe, Pseudocode in lange, funktional korrekte Programme abzubilden. Angesichts von Testfällen als Mechanismus zur Validierung von Programmen durchsuchen wir den Raum der möglichen Übersetzungen des Pseudocodes, um ein Programm zu finden, das die Validierung besteht. Ohne eine angemessene Zuordnung der Verantwortung zur Lokalisierung der Ursachen von Programmfehlern ist es jedoch schwierig, die Suche in Richtung erfolgversprechenderer Programme zu lenken. Wir schlagen vor, die Verantwortungszuordnung auf Basis von Signalen aus Kompilierungsfehlern durchzuführen, die 88,7 % aller Programmfehler ausmachen. Konkret behandeln wir die Übersetzung jeder Pseudocode-Zeile als eine diskrete Portion des Programms und versuchen bei jedem Versagen eines synthetisierten Programms beim Kompilieren mit einer Fehlerlokalisationsmethode, den Teil des Programms zu identifizieren, der für das Versagen verantwortlich ist. Anschließend konzentrieren wir uns auf die Suche nach alternativen Übersetzungen des Pseudocodes für diese Teile. Für die Evaluation sammelten wir den SPoC-Datensatz (Search-based Pseudocode to Code), der 18.356 Programme enthält, die mit menschlicher Autorin oder Autor verfasstem Pseudocode und Testfällen versehen sind. Unter einem Budget von 100 Programm-Kompilierungen verbessert sich durch die Durchführung der Suche der Erfolgsquotient der Synthese im Vergleich zur Verwendung der besten einzelnen Übersetzung des Pseudocodes von 25,6 % auf 44,7 %.