Enabling program analysis through provenance-preserving translation into A-Normal form

Abstract

This thesis explores the transformation of imperative high-level languages into an intermediate representation, the A-normal form, and back. It involves developing an entire pipeline that transforms the data, which thereby facilitates the optimization and analysis of the code in A-normal form. The optimized code is then transformed back into the imperative language.Usually, semantic information is lost between each transformation. In contrast, this thesis presents a novel methodology that enables the trustworthy backwards transformation into the original source code by retaining crucial provenance information, that would normally be lost. Based on an extensive literature research, it is evident that this particular form of transformation has not been documented or published yet.In the course of this thesis, the research questions addressed and resolved, include how provenance information can be retained during the transformation process and whether a bijective relation between imperative source code and A-normal form with provenance can be established. To achieve these objectives, we defined and developed a transformation pipeline with intermediate representations, starting from the imperative source code in Python, via abstract syntax trees, control flow graphs and static single assignments into A-normal form, essential for the transformation process. The syntax definitions and transformation rules for each representation are rigorously established to ensure the accuracy and consistency of the transformation process.The implementation of the proposed methodology is realized through the development of a Python library that facilitates the transformations and a web-project for its visualization. Leveraging existing libraries such as "AST-comments" and "Scalpel", which are extended and made publicly available, assist the seamless integration of the transformation process into existing workflows. The implementation is subjected to critical evaluation with external code files tested for deviations between the original- and the back-propagated-code. The detailed documentation of the evaluation result underscores the efficiency and reliability of the proposed methodology.While the developed library demonstrates great performance in preserving provenance information and accurately transforming code into A-normal form and back, certain limitations are acknowledged. This includes the transformation of complex structures such as classes, exceptions and asynchronous behavior, which remain challenging and warrant further exploration for enhancement.In summary, this thesis contributes a comprehensive documentation of the transformation process, elucidates transformation rules and syntax definitions for the various intermediate representations, and pioneers the preservation of provenance information for enabling the novel backwards transformation into the original source code. Through careful implementation and evaluation, the work provides evidence of the effectiveness and practicality of the proposed methodology and establishes a solid foundation for future advances in program analysis and optimization.

Diese Arbeit untersucht die Transformation von imperativen Hochsprachen in eine intermediäre Repräsentation, die A-Normalform, und zurück. Dies umfasst die Entwicklung einer kompletten Pipeline, die die Daten transformiert, wodurch die Optimierung und Analyse des Codes in A-Normalform erleichtert werden. Die Erkenntnisse aus dieser Analyse werden dann wieder in die imperative Sprache zurücktransformiert.Normalerweise gehen bei jeder Transformation semantische Informationen verloren. Im Gegensatz dazu präsentiert diese Arbeit eine neuartige Methodik, die eine vertrauenswürdige Rücktransformation in den Originalquellcode ermöglicht, indem wichtige Herkunftsinformationen, die normalerweise verloren gehen würden, beibehalten werden. Basierend auf einer umfangreichen Literaturrecherche wird deutlich, dass diese spezielle Form der Transformation bisher nicht dokumentiert oder veröffentlicht wurde.Im Verlauf dieser Arbeit werden die untersuchten Forschungsfragen behandelt und gelöst, darunter wie Herkunftsinformationen während des Transformationsprozesses erhalten bleiben können und ob eine bijektive Beziehung zwischen dem imperativen Quellcode und der A-Normalform mit Herkunftsinformationen hergestellt werden kann. Um diese Ziele zu erreichen, haben wir eine Transformationspipeline mit Zwischenrepräsentationen definiert und entwickelt, die vom imperativen Quellcode in Python über abstrakte Syntaxbäume, Kontrollflussgraphen und statische Einzelzuweisungen in A-Normalform führt, die für den Transformationsprozess wesentlich sind.Die Syntaxdefinitionen und Transformationsregeln für jede Repräsentation werden streng festgelegt, um die Genauigkeit und Konsistenz des Transformationsprozesses zu gewährleisten. Die Implementierung der vorgeschlagenen Methodik erfolgt durch die Entwicklung einer Python-Bibliothek, die die Transformationen erleichtert, und eines Webprojekts zur Visualisierung.Die Nutzung bestehender Bibliotheken wie "AST-comments" und "Scalpel", die erweitert und öffentlich zugänglich gemacht werden, unterstützen die nahtlose Integration des Transformationsprozesses in bestehende Workflows. Die Implementierung wird einer kritischen Evaluation unterzogen, wobei externe Code-Dateien auf Abweichungen zwischen dem Original- und dem rücktransformierten-Code überprüft werden. Die ausführliche Dokumentation des Evaluierungsergebnisses unterstreicht die Effizienz und Zuverlässigkeit der vorgeschlagenen Methodik.Während die entwickelte Bibliothek eine hervorragende Leistung bei der Erhaltung von Herkunftsinformationen und der präzisen Transformation des Codes in A-Normalform und zurück zeigt, werden bestimmte Einschränkungen anerkannt. Dazu gehört die Transformation von komplexen Strukturen wie Klassen, Exceptions und asynchronem Verhalten, die weiterhin herausfordernd sind und eine weitere Erkundung zur Verbesserung erfordern.Zusammenfassend trägt diese Arbeit zu einer umfassenden Dokumentation des Transformationsprozesses bei, erläutert Transformationsregeln und Syntaxdefinitionen für die verschiedenen Zwischenrepräsentationen und ist Wegbereiter für die Erhaltung von Herkunftsinformationen zur Ermöglichung der neuartigen Rücktransformation in den Originalquellcode. Durch sorgfältige Implementierung und Evaluation liefert die Arbeit Belege für die Wirksamkeit und Praktikabilität der vorgeschlagenen Methodik und legt eine solide Grundlage für zukünftige Fortschritte in der Programmanalyse und -optimierung dar.