WG211/M2Visser

Title: Towards Extensible Program Transformation Systems
Eelco Visser

Abstract: The work on the Stratego program transformation language can be divided into two tracks. The first is concerned with high-level constructs for the support of concise and generic specification of program transformations [3,5]. This has produced features such as generic traversal strategies, first-class pattern matching, and scoped and dependent dynamic rewrite rules. Together these features provide a rich language for concisely implementing a wide variety of program transformations including data-flow transformations, code generation, compilation, and partial evaluation.

The second track is concerned with the support for language embeddings [1,2,4]. Language embeddings are useful for adding domain-specific syntax to a general-purpose programming language. Applications include heterogeneous staged meta-programming (e.g., generating Java in Stratego) and syntactic abstractions for domains (e.g., Swul [Swing User-Interface Language] in Java). The syntax definition formalism SDF2 and transformation strategies of Stratego provide a powerful combination for implementing such embeddings and the corresponding assimilation [1].

This second track can be considered an application of the techniques from the first. However, language embeddings introduce a particular set of challenges. Properly implementing a language embedding requires supporting it in all stages of the programming environment (at least until artifacts of the embedding are eliminated), i.e., type checking, optimization, and code generation. While one can build support for a particular embedding (e.g., generating AspectJ programs with Java), the challenge here is to create an open programming environment that can cater for many different embeddings, possibly used in the same module. We have realized this to some extent in the `meta-programming with concrete object syntax' approach [4] for Stratego itself, in the sense that we can embed arbitrary syntax for terms. However, the assimilation is fixed here.

The perspective here is related to Moggi's call for a general methodology for implementing staged programming languages.

In the talk I want to outline the motivation for extensible program transformation systems (explain the above), and discuss possible roads to solutions.

References

[1] M. Bravenboer and E. Visser. Concrete Syntax for Objects. Domain-Specific Language Embedding and Assimilation without Restrictions. In D. C. Schmidt, editor, Proceedings of the 19th ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications (OOPSLA'04), pages 365--383, Vancouver, Canada, October 2004. ACM Press.

[2] B. Fischer and E. Visser. Retrofitting the AutoBayes Program Synthesis System with Concrete Object Syntax. In C. Lengauer et al., editors, Domain-Specific Program Generation, volume 3016 of Lecture Notes in Computer Science, pages 239--253. Spinger-Verlag, 2004.

[3] K. Olmos and E. Visser. Composing Source-to-Source Data-Flow Transformations with Rewriting Strategies and Dependent Dynamic Rewrite Rules. In R. Bodik, editor, 14th International Conference on Compiler Construction (CC'05). Springer-Verlag, April 2005.

[4] E. Visser. Meta-Programming with Concrete Object Syntax. In D. Batory, C. Consel, and W. Taha, editors, Generative Programming and Component Engineering (GPCE'02), volume 2487 of Lecture Notes in Computer Science, pages 299--315, Pittsburgh, PA, USA, October 2002. Springer-Verlag.

[5] E. Visser. Program Transformation with Stratego/XT: Rules, Strategies, Tools, and Systems in StrategoXT-0.9. In C. Lengauer et al., editors, Domain-Specific Program Generation, volume 3016 of Lecture Notes in Computer Science, pages 216--238. Spinger-Verlag, June 2004.