Stratego History

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.

• SpecificationOfRewritingStrategies

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

• StrategicPatternMatching: overlays, ContextualRules, RecursivePatterns

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.

• WarmFusionInStratego

• 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

• OttoSkroveBagge from Bergen visits for 3 months to work on the implementation of CodeBoost.

• KarinaOlmos^? starts DSP transformation project at Philips Research Laboratories

• FirstStrategoUsersDay

• Program Optimization Seminar
  • simple optimizations

Spring 2000

• LanguageIndependentTraverals^?
  • GenericTermDeConstruction^?

• First course on SoftwareGeneration^?
  • MondrianOptimizer^?

Summer 2000

Implementation of compiler for TigerLanguage^?

Fall 2000

• First HighPerformanceCompilersCourse^?
  • TigerInStratego^?

• XTaBundleOfTransformationTools^?

Winter 2001

• Visit PatriciaJohann
  • FusingLogicAndControlWithLocalTransformations^?

• Visit to Nancy: interpreter for RhoCalculus^?

• StrategoScript^?: an interpreter for Stratego

• SecondStrategoUsersDay

• ASurveyOfStrategiesInProgramTransformation^?

• Master's Projects
  • RhoStratego: generalizing the case construct
  • CobolX: PreserveLayout^?
  • PanOptimizer: InliningStrategies^?

Spring 2001

Teaching

• Second course on SoftwareGeneration^?
  • new slides on Stratego

Language extension

• ScopedDynamicRewriteRules: generation of context-sensive rules
  • TigerInterpreter^?
  • TigerTypeChecker^?
  • TigerInliner^?

Summer 2001

• StrategoRelease06

• 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^?
  • more slides on Stratego
  • assignments on: ProgramSimplification^?, SoftwareVisualization, ProgramInstrumentation^?

• Implementation of optimizations with DynamicRules by KarinaOlmos

• Third course on High-Performance Compilers^?
  • Improved implementation of the TigerCompiler^?
  • Bottomup-rewriting for code generation using dynamic rules by MartinBravenboer

• StrategoRelease063 introduces TermWrap and TermProject