Web Log

Stratego -- Strategies for Program Transformation


Nemerle is a new hybrid (functional, object-oriented and imperative) programming language for the .NET platform.

Key features of the language include:

  • simplicity,
  • C#-like syntax,
  • easy to use object system (derived directly from the .NET),
  • easy access to both functional and imperative features,
  • powerful code-generating macros,
  • variants,
  • pattern matching,
  • static and on-demand dynamic typing,
  • type inference.

We plan to make language full CLS consumer and producer soon.


Scala is a new programming language designed by Martin Odersky. According to the announcement:

Scala smoothly integrates object-oriented and functional programming. It is designed to express common programming patterns in a concise, elegant, and type-safe way. Scala introduces several innovative language constructs. For instance:

  • Abstract types and mixin composition unify ideas from object and module systems.

  • Pattern matching over class hierarchies unifies functional and object-oriented data access. It greatly simplifies the processing of XML trees.

  • A flxible syntax and type system enables the construction of advanced libraries and new domain specific languages.


David Wheeler's Program Library HOWTO is a HOWTO for programmers [that] discusses how to create and use program libraries on Linux using the GNU toolset. Particularly useful is Elf: From the Programmer's Perspective with explanation of constructors and such. (For finally getting separate compilation in the Stratego compiler.)


Classboxes: A Minimal Module System Supporting Local Rebinding

Classical modules systems support well the modular development of applications but lack the ability to add or replace a method in a class that is not defined in that module. But languages that support method addition and replacement do not provide a modular view of applications, and their changes have a global impact. The result is a gap between module systems for object-oriented languages on one hand, and the very desirable feature of method addition and replacement on the other hand.

To solve these problems we present classboxes, a module system for object-oriented languages that allows method addition and replacement. Moreover, the changes made by a classbox are only visible to that classbox (or classboxes that import it), a feature we call local rebinding.

This is a notion needed in Stratego to come to terms with the extension of strategies in different modules. Currently this is at the loss of separate compilation.

-- EelcoVisser - 08 Dec 2003


Quote: CodeCrawler is a language independent reverse engineering tool [developed by Michele Lanze] which combines metrics and software visualization. CodeCrawler is based on Moose, an implementation of the FAMIX metamodel. CodeCrawler is written in VisualWorks Smalltalk and runs on every major platform. You need however the VisualWorks non-commercial distribution which you can download from the website of Cincom.


Recently Pierre-Etienne Moreau gave a talk at the PEM at CWI about Formal Islands: introducing algebraic pattern matching facilities into a classical language.

The notion of formal islands (think of island grammars) is a way of integrating algebraic notions into existing programs written in C or Java for example. As shown by ASF+SDF and ELAN, many processes can be seen as transformations of tree-like data structures. In compiler construction, for example, we continuously manipulate trees and perform tree transformations. In order to simplify the implementation of these transformations (in C or Java), and reduce the risk of error, we have introduced a pattern matching compiler: TOM. In this talk, I will introduce the language and its (informal) semantics and give several examples of applications, ranging from small XML transformations to the TOM compiler itself. TOM is developed by INRIA (http://tom.loria.fr) and is available as an eclipse plugin. This bundle contains the ATerm library and integrates an ApiGen plugin.


http://open64.sourceforge.net : An open and open source compiler for C, C++ and other languages that can be extended with new optimizations.


The programming language Scheme does not natively include pattern matching, but rather through libraries, which can be become quite sophisticated, e.g., including regular expressions. May provide inspiration for Stratego with list matching and other extensions of pattern matching.


Ganesh Sittampalam, Oege de Moor, Ken Friis Larsen.Incremental Execution of Transformation Specifications.Accepted for POPL '04.



Dave Thomas: “The Impedance Imperative – Tuples+Objects+Infosets=Too Much Stuff!”, in Journal of Object Technology, vol. 2, no. 5, September-October 2003, pp. 7-12.

This article discusses the complexity of writing software that manipulates structured information. The move from tuples to objects to the xml info set has made writing these rather basic applications unnecessary complex, mostly because there hasn't been a real move. Dave Thomas challenges us to step back and think about where we should go now.


The Lightweight Languages workshop series focuses on programming languages, tools, and processes that are usable and useful. In particular some interesting ideas for 'Disruptive Programming Language Technologies' in Todd Proebsting's talk at LL2. Here is the abstract of the talk:

For the past few decades, programming language design and implementation research has concentrated heavily in a few notable areas: type theory, functional programming, object-oriented programming, and, of course, optimization techniques. Yet most of the recent commercially successful languages (e.g., Perl, Python, Visual Basic, Java) are not particularly interesting when judged in these domains. What happened? The newly successful languages represented a "disruptive technology" that allowed it to capture programmer mindshare while everybody else was looking. In this talk, I will present what I think makes a programming language technology disruptive, and I will propose possible future disruptive programming language technologies.


Generalized-LR parsing is taking over the world, well at least Microsoft Research. In a recent paper Dave Hanson and Todd Proebsting describe A Research C# Compiler (MSR-TR-2003-32, Apr. 2003) in which they use their own GLR parser. Another technique that they adopt is generic traversals.


Special Issue of FUNDAMENTA INFORMATICAE on PROGRAM TRANSFORMATION: Theoretical Foundations and Basic Techniques

Guest Editors: Alberto Pettorossi, University of Roma Tor Vergata, Italy and Maurizio Proietti, IASI CNR, Roma, Italy


This special issue is devoted to the various aspects of program transformation as they developed during the last decades in different programming paradigms such as imperative, functional, and logic languages. It gives special emphasis to the theoretical foundations and basic techniques of program transformation such as: the various approaches and formalisms, the correctness of the transformations, the relationship with program analysis, program synthesis, program specialization, partial evaluation, and theorem proving.


In a set of slides Bill Pugh gives a reaction to Proebsting's law (compiler optimizations double the speed of programs every 18 years) under the title Is Code Optimization Research Relevant? One of his conclusions is that rather than squeezing another percent speedup out of artificial benchmarks, optimization research should be directed at optimization of high-level constructs, thus encouraging higher-level programming.


The CDuce and Xtatic projects build languages for programming with XML data types and have support for regular pattern matching?. This may provide inspiration for the compilation of strategic pattern matching.

Phil Wadler's page on XML: Some hyperlinks minus the hype provides many links to XML concepts, tools, and applications.


Dick Kieburtz is using Stratego to implement a theorem prover for proving correctness of Haskell programs in the Programmatica project. See his comments on the P Logic Prover.


Types and Programming Languages: The Next Generation.

This presentation by Benjamin Pierce gives a birds-eye view on PL research in the last 20 years. In the context of Stratego the section on XML type systems and XDuce might be interesting: how do the achievements of XDuce compare to the achievements of Stratego? (Lambda the Ultimate)


Ronald Bourret's paper on XML Data Binding Resources says that

XML data binding is the binding of XML documents to objects designed especially for the data in those documents. This allows applications (usually data-centric) to manipulate data that has been serialized as XML in a way that is more natural than using the DOM.

Time to show how this is done in Stratego with XmlTools.


This paper by Philip Wadler on Call-by-need and call-by-value might be nice material for a Stratego programming pearl.


It might be interesting to consider implementation of some of the following methods in Stratego. -- EelcoVisser - 26 May 2003

John Harrison johnh@ichips.intel.com wrote:

I've made available some simple implementations of common automated theorem proving methods. This code, intended to accompany a textbook on theorem proving, is written in Objective CAML and covers quite a range of techniques, e.g.

  • The Davis-Putnam procedure
  • Stalmarck's method
  • Binary decision diagrams
  • Tableaux
  • Resolution
  • Model elimination
  • Congruence closure
  • Rewriting
  • Knuth-Bendix completion
  • Brand's transformation
  • Paramodulation
  • Quantifier elimination over Z, C and R
  • Groebner bases
  • Geometry theorem proving
  • The Nelson-Oppen combination method
  • CTL and LTL model checking
  • Symbolic trajectory evaluation
  • Interactive LCF proof
  • Mizar-like proofs

For more details, and to browse or download the code, see:



The Journal for Higher-Order and Symbolic Computation published a special issue dedicated to Bob Paige the designer of the APTS transformation system.