Abstract Interpretation of Program Transformations using Regular Tree Grammars
Master Project of Jente Hidskes


Abstract

Many program transformation languages simplify the implementation of program transformations. However, they give only weak static guarantees about the generated code such as well-sortedness. Well-sortedness guarantees that a program transformation does not generate syntactically ill-formed code, but it is too imprecise for many other scenarios. In this paper, we present a static analysis that allows developers of program transformations to reason about their transformations on a more fine-grained level, namely that of syntactic shape. Specifically, we present an abstract interpreter for the Stratego program transformation language that approximates the syntactic shape of transformed code using regular tree grammars. As a baseline, we also present an abstract interpreter that guarantees well-sortedness. We prove parts of both abstract interpreters sound.

Thesis


Abstract Interpretation of Program Transformations using Regular Tree Grammars

Student: Jente Hidskes
Supervisor(s): Eelco Visser, Sebastian Erdweg
Defended: November 02, 2018