Stratego History
Stratego -- Strategies for Program Transformation
Since its always interesting to see how ideas develop, this page contains a reconstruction of the development of
StrategoLanguage and its implementation.
March 1997
At a visit to INRIA in Nancy the ideas of
RewritingStrategies in
ELAN are explained. This looks like an interesting mechanism for dealing with some of the problems encountered in
ASFandSDF specification.
Summer 1997
Development of strategy combinators with
BasLuttik. The combinators are a mixture of process algebra (sequential programming) and modal logic (for term traversal). In contrast to
ELAN no full backtracking operators are provided. New are combinators for
GenericTermTraversal. The combinators are implemented in
ASFandSDF.
Fall 1997
At the
OregonGraduateInstitute? AndrewTolmach is interested in a high-level language for specifying optimizations. An interpreter for the strategy combinators is implemented in
MetaML.
Winter 1998
Since the implementation of
MetaML is not up to speed the implementation of the interpreter is continued in Transform.SML.
The interpreter parses modules written in a dedicated language for specifying
RewriteRules and
RewritingStrategies.
While attending POPL'98 in San Diego it becomes clear that
ContextualRules (inspired by the paper
ShrinkingLambdaExpressionsInLinearTime? by
AndrewAppel and
TrevorJim?) can be implemented elegantly when match can share its variable scope with the context. A contextual rule can be implemented by means of a local traversal that performs a transformation that shares bindings from the context.
Spring 1998
Since interpretation is very slow implementation of compiler is begun with
ZinoBenaissa.
(See also this
CompilerWritingPicture)
The compiler is written in SML based on the front-end for the intepreter. The compiler implements full backtracking. Strategy definitions are interpreted as macros and are completely expanded at compile time. The compiler reduces a specification to one huge strategy expression which is compiled to a single C function.
- Visit to MaudeLanguage? group at SRI
- BuildingOptimizersWithRewritingStrategies?
At a talk at FMCS
EugenioMoggi? observes that the operational semantics does not require full backtracking. It turns out that an implementation without full backtracking is desirable, i.e., much more efficient.
- ACoreLanguageForRewriting: implement traditional rewriting with strategies, allows easy extension with features such conditional and default rules
Summer 1998
As a test case for the language, i.e., to get material to compile and to get a feeling for programming in the language, a compiler
for the strategies language is written in itself.
September 1998
The first bootstrap is completed just before attending
ICFP'98.
As
JanHeering had already suggested it suddenly becomes clear that the language should be called Stratego.
Fall 1998
Winter 1999
The first application other than the toy RML compiler and the
StrategoCompiler itself is the implementation of the
WarmFusion algorithm with
PatriciaJohann. This later turns into the
HSX package.
- OttoSkroveBagge from Bergen visits Utrecht to learn Stratego and to work on the implementation of CodeBoost, a transformation engine for C++ programs.
Summer 1999
- First public release (0.4.1) in August
Fall 1999
- Architecture of the XT bundle of transformation tools
- ImplodeAsFix?: using Tools.SDF parsers
- pretty-printing: connecting the GenericPrettyPrinting? package
Winter 2000
- KarinaOlmos? starts DSP transformation project at Philips Research Laboratories
- Program Optimization Seminar
Spring 2000
- LanguageIndependentTraverals?
- GenericTermDeConstruction?
- First course on SoftwareGeneration?
Summer 2000
Implementation of compiler for
TigerLanguage?
Fall 2000
- First HighPerformanceCompilersCourse?
- XTaBundleOfTransformationTools?
Winter 2001
- Visit to Nancy: interpreter for RhoCalculus?
- StrategoScript?: an interpreter for Stratego
- ASurveyOfStrategiesInProgramTransformation?
Spring 2001
Teaching
- Second course on SoftwareGeneration?
Language extension
Summer 2001
- New compilation scheme using setjmp/longjmp to implement failure and nested functions (a gcc extension) to implement higher-order strategy arguments.
Fall 2001
- Third course on SoftwareGeneration?
- Third course on High-Performance Compilers?
- Improved implementation of the TigerCompiler?
- Bottomup-rewriting for code generation using dynamic rules by MartinBravenboer
Fall 2002
- Stratego 0.8 introduces support for program transformation with concrete object syntax
Winter 2003
- XTC tool composition for creating complete transformation systems in Stratego.
Spring 2004