Ivan Radiček doktorirao u Beču na temu dinamičke analize računalnih programa

Ovaj četvrtak, uspješnom obranom svoje doktorske disertacije pod nazivom “Automated Feedback Generation in Introductory Programming Education” Ivan Radiček stekao je titulu doktora znanosti u računarstvu na Tehničkom sveučilištu u Beču. Obrana pred četveročlanom međunarodnom komisijom trajala je više od dva sata tokom kojih je Ivan izložio svoj višegodišnji izvorni znanstveni rad, a kojeg je provodio pod mentorstvom prof. dr. Floriana Zulegera.

Ivan je osnovnoškolsko obrazovanje završio na Kalniku, a srednjoškolsko u Križevcima, u Gimnaziji Ivana Zakmardija Dijankovečkoga. Nakon toga, odabrao je studij računarstva na zagrebačkom Fakultetu elektrotehnike i računarstva (FER) na kojem je diplomirao 2012. godine. Paralelno sa studijem računarstva praktična iskustva stječe u jednoj zagrebačkoj IT firmi, ali već godinu i pol dana nakon diplome odlučuje se na nastavak svog obrazovanja te upisuje doktorski studij na Tehničkom sveučilištu u Beču. Za vrijeme diplomskog studija već je razvio interes za formalne metode u računarstvu, a tu tematiku odabire i kao temu doktorata gdje istražuje primjenu formalnih metoda u području edukacije na sustavima računalne asistencije pri učenju programiranja u sklopu grupe FORSYTE prof. dr. Zulegera. U sklopu tog istraživanja objavljuje dva znanstvena rada. U drugoj etapi svog doktorata Ivan analizira matematičkim metodama performanse funkcijskih programa i to istraživanje provodi na institutu Max Planck u njemačkom Saarbrückenu na kraju čega objavljuje još jedan znanstveni rad. Pred kraj doktorata, Ivan se zapošljava u Microsoftu gdje i danas radi u grupi PROSE, a gdje se bavi metodama za automatsku sintezu računalnih programa i umjetnom inteligencijom. Uz ova područja, stručno se zanima i za programske jezike te tipske sustave.

Kao student, Radiček je bio predavač srednjoškolcima u Informatičkom klubu “Križevci” organiziranog u sklopu Zajednice tehničke kulture Križevci, a vodio je i radionice programiranja na Culture Shock festivalu.

U nastavku slijedi sažetak doktorske disertacije na engleskom i njemačkom jeziku:

Anyone who ever manually corrected or graded any type of student assignment is aware of how tedious, error-prone and time-consuming this task is. In the context of programming assignments the situation is even worse: with a rising demand for programming education there are online courses with thousands of students, which makes manual grading downright impossible. However, students who are learning programming, especially at the introductory level, are in pressing need of guidance. This has motivated a lot of research on computer-aided feedback generation in introductory programming education. Many of these approaches are based on practices and methods employed in software engineering, testing, and verification, such as: code reviews, debugging, automated test generation, program synthesis, program repair, … This is very useful feedback as it mimics how software engineers reason about the code.

However, there are still numerous open issues. In this thesis, we will address the following two challenges:

• Most of the existing research focused on generating functional feedback, that is, to help the students write any correct program, while ignoring non-functional properties such as e.g., performance.
• Most of the existing approaches lack some of the following desirable properties automation (require as little manual effort as possible), correctness (generate correct feedback), performance (generate feedback in order of seconds), exhaustiveness (generate feedback for most student programs), and usefulness (reduce the teacher effort or help the student to make progress).

We first study inefficient (but correct) student programs in order to understand the performance problems faced by students in introductory programming. From the study we observe that in order to provide feedback we need to identify the high-level algorithmic strategy used by the student’s program, while ignoring its low-level implementation details. To that end we propose a lightweight specification language that enables the teacher to specify various algorithmic strategies, and a novel dynamic program analysis to determine whether a student’s attempt matches the teacher’s specification.

To provide feedback on (functional) correctness of student programs we propose a novel fully-automated program repair algorithm that uses the wisdom of the crowd: it leverages the existing correct student solutions to syntactically modify incorrect student attempts. The repair algorithm builds on and extends our earlier dynamic program analysis in order to determine whether a modified (repaired) program has the same behavior as a correct solution.

We have implemented both of the proposed approaches in practical tools and performed an experimental evaluation on a large number of student attempts from various programming courses. We have evaluated both of our approaches on the above mentioned desirable properties: automation, correctness, performance, exhaustiveness, and usefulness.

 

Wer jemals Übungsaufgaben korrigiert oder bewertet hat, ist sich darüber bewusst wie mühsam, fehleranfällig und zeitaufwändig diese Aufgabe ist. In Bezug auf Programmieraufgaben ist die Situation noch gravierender: aufgrund des steigenden Bedarfs an ProgrammiererInnen gibt es Online-Kurse mit Tausenden von Studenten, was manuelles Bewerten schlicht unmöglich macht. Demgegenüber haben gerade Studenten, welche noch nie zuvor programmiert haben, einen hohen Bedarf an Betreuung. Diese Ausgangslage hat zu einer Vielzahl an Forschungsansätzen geführt wie man computergestützt Feedback für Programmieranfänger generieren kann. Viele Ansätze basieren auf der Praxis und den Methoden des Software Engineering, des Software Testens und der Programmverifikation: Code Reviews, Debugging, automatische Testfallgenerierung, Programmsynthese, Programmreparatur, … Dieses Feedback ist sehr nützlich da es nachahmt wie ProgrammiererInnen mit ihrem Code arbeiten und darüber nachdenken.

Dennoch verbleiben eine Vielzahl von Herausforderungen. In dieser Arbeit addressieren wir die beiden folgenden Fragestellungen:

• Die bisherige Forschung hat vor allem die Generierung von funktionalem Feedback behandelt, das heißt Studenten dabei zu helfen ein korrektes Programm zu schreiben, wobei nicht-funktionale Eigenschaften wie zum Beispiel Performance ignoriert werden.
• Existierenden Ansätzen fehlt mindestens eine der folgenden Eigenschaften: Automatisierung (so wenig manueller Aufwand wie möglich), Korrektheit (die Generierung von korrektem Feedback), Performance (die Generierung von Feedback innerhalb weniger Sekunden), Vollständigkeit (die Generierung von Feedback für die meisten studentische Lösungen), und Nutzen (Reduktion des Aufwands für den Betreuer oder Erzielen von Fortschritt durch die Studenten).

Wir studieren zunächst ineffiziente (aber korrekte) studentische Lösungen um zu verstehen welche Performanceprobleme bei Programmieranfängern auftreten. In dieser Studie stellen wir fest, dass es zur Feedbackgenerierung erforderlich ist, die algorithmische Strategie einer Lösung zu erkennen, aber Implementierungsdetails zu ignorieren. Zu diesem Zweck entwickeln wir eine leichtgewichtige Spezifizierungssprache, welche es dem Lehrer erlaubt algorithmische Strategien zu spezifizieren, und eine neue dynamische Programmanalyse, welche es ermöglicht zu überprüfen ob ein studentischer Lösungsansatz eine Spezifikation des Lehrers erfüllt.

Um Feedback für die funktionalen Korrektheit von studentischen Lösungen zu generieren, entwickeln wir einen neuartigen voll-automatiserten Reparaturalgorithmus, welcher einem Wisdom of the Crowd Ansatz folgt: unser Algorithmus nutzt bereits existierende korrekte studentische Lösungen um syntaktische Änderungen an inkorrekten studentischen Lösungen zu generieren. Der Reparaturalgorithmus basiert auf und erweitert unsere dynamische Programmanlyse um zu überprüfen ob ein studentischer Lösungsansatz das selbe Verhalten hat wie eine bereits existierende korrekte Lösung.

Wir haben beide Ansätze in praktischen Tools implementiert und an einer großen Anzahl von studentischen Lösungen aus verschiedenen Programmierkursen ausgwertet. Wir evaluieren beide Tools im Hinblick auf die zuvor beschriebenen wünschenswerten Eigenschaften: Automatisierung, Korrektheit, Performance, Vollständigkeit und Nutzen.