Abstract

Werkzeuge zur Lokalisierung der Ursachen von Typfehlern in Programmen

Die meisten getypten funktionalen Programmiersprachen, wie beispielsweise Haskell und ML, basieren auf dem Hindley-Milner Typsystem. Ohne aufwendige Typannotationen im Programm zu verlangen, bietet das Typsystem die Flexibilität von polymorphen Typen. Wenn ein Programm jedoch vom Compiler mit einer Typfehlermeldung abgelehnt wird, ist es häufig schwierig für den Programmierer, die Ursache dieses Typfehlers zu lokalisieren.

Kern des Problems ist die Schwierigkeit, zu erklären, warum ein bestimmter Programmausdruck einen bestimmten Typ hat. Weder die Definition des Typsystems, noch die üblichen Typinferenzalgorithmen sind kompositionell: Um nachvollziehbar zu sein, muß eine Erklärung aus kleinen Schritten bestehen, die jeweils nur einen kleinen Programmteil betreffen und unabhängig auf Übereinstimmen mit den Intentionen des Programmierers überprüft werden können. Ein Typerklärungswerkzeug muß auch interaktiv sein, damit der Programmierer seine Intentionen einbringen kann und nur die ihn interessierenden Teile einer Erklärung betrachten muß.

Mit Hilfe einer Variante des Hindley-Milner Typsystems kann ein kompositioneller Typerklärungsgraph definiert werden. Interaktive Navigation durch diesen Graphen ermöglicht dem Programmierer, Typen und Typfehler zu verstehen. Außerdem dient der Graph als Grundlage für algorithmisches Debuggen von Typfehler. Dieses ermöglicht, die Ursache eines Typfehlers semi-automatisch zu lokalisieren, ohne überhaupt einen Typinferenzschritt nachvollziehen zu müssen. Sowohl Navigieren als auch algorithmisches Debuggen werden anhand eines Prototyps praktisch demonstriert.