Homepage of

Karl Trygve Kalleberg

Abstractions for Language-Independent Program Transformations


Maintenance of software programs is normally the most expensive part of the software life cycle. Most tools that support maintenance and improvements to programs and program structure, be they compilers, program verifiers, transformation systems, modeling or reverse-engineering tools all represent the program internally either in the form of abstract syntax trees (ASTs), or in forms derived from it. In each of these software tools, the respective AST is almost always specific to a given programming language. While the task of a given tool, e.g., a documentation generator, may be generic across many languages, the chosen program representation binds a given tool to a particular subject language. The goal of this thesis was find more generic solutions to the AST problem. My dissertation investigates how one may construct ASTs more generically, and how one may express reusable, language-independent program analyses and transformations on top of these generic ASTs. It has been an explicit goal that transformations and analyses should be reusable for language families, across language infrastructures and, when possible, across language paradigms.


In pursuit of the above goals, the following results were achieved:

  1. A Survey of the State of the Art -- The dissertation starts with a survey of existing software transformation systems. The focus of the survey is on transformation languages and architectures. Attention is given to the program models, i.e. the facilities a transformation system has for representing and manipulating programs. The survey indicates that the program model is the central component that needs good abstraction facilities and a good abstract representation if one is to attain transformation reuse and language-independence. It also indicates that facilities for language abstraction are not sufficiently well developed in current transformation systems.
  2. A Domain Analysis -- Next, the dissertation presents an analysis of program models. It describes the domain objects which must be abstracted over. This analysis suggests that the abstractions necessary for language-independence behave in rather complicated ways: capturing them in traditional transformation libraries is not the best solution. It might be better to express the abstractions as new language features in the transformation language.
  3. Design of New Abstractions -- The above-noted abstractions are captured and described as abstract data types, using basic algebraic specifications. This formalises the abstractions and the rules governing them. Algebraic specifications are used as requirements for implementing the abstractions in transformation libraries and as language extensions to the transformation language.
  4. Implementation -- an extensible variant of the Stratego transformation language, called MetaStratego, is presented. The prototypes of all the new abstractions, both transformation libraries and language extensions, have been implemented on top of MetaStratego.
  5. Case studies -- Four research prototypes were constructed as proofs-of-concept that the suggested approach to language genericity is feasible:
    1. Spoofax, a modern, interactive development environment for (Meta)Stratego.
    2. A framework for interactive and automatic transformation and analysis of Java code.
    3. JAxT, a code generator for axiom-based unit testing.
    4. A domain-specific aspect language for alerts.

Summary of Results

The primary goal of the research, to provide facilities for language-independent program analysis and transformation, is achieved and substantiated through:

  • core API for language independent ASTs;
  • generic and mostly automated technique for adapting existing ASTs into the core API;
  • an adaptation of the Stratego transformation system that executes on top of the core API; and
  • validation of the approach through several substantial case studies.


The complete contents of the dissertation is available.