Stratego

Stratego is a domain-specific language for program transformation—the systematic, rule-based rewriting of one program into another. Its defining idea is a clean separation between what to transform and where and when to do it: rewrite rules describe individual transformation steps as pattern-and-replace pairs, while strategies are small, composable programs that decide how those rules traverse and are applied across a program’s abstract syntax tree. This separation, unusual when Stratego appeared, lets a single library of rules be reused across many different transformations and lets generic control patterns—like “apply this everywhere, bottom-up” or “keep applying until nothing changes”—be written once, independently of the rules they orchestrate.

A note on dating

The encyclopedia metadata lists 1998 as Stratego’s first-appearance year, and independent verification supports it. Stratego is generally traced to the 1998 paper Building Program Optimizers with Rewriting Strategies by Eelco Visser, Zine-El-Abidine Benaissa, and Andrew Tolmach, presented at the ACM SIGPLAN International Conference on Functional Programming (ICFP'98). That work introduced the combination of named rewrite rules with a language of strategy combinators that became Stratego’s signature. The conceptual groundwork was laid slightly earlier, in the 1997 paper Specification of Rewriting Strategies by Bas Luttik and Eelco Visser. The frequently cited System Description of Stratego 0.5 dates to 2001 (RTA), which is the first tagged public release rather than the language’s first appearance. This page treats 1998 as the first-appearance year and flags the others in the timeline.

History & Origins

Stratego was created by the Dutch computer scientist Eelco Visser (1966–2022), initially during his time at Utrecht University and later carried forward at Delft University of Technology (TU Delft), where he became a professor and led the Spoofax language-workbench effort. Its intellectual roots lie in the world of algebraic specification and term rewriting, and in particular the ASF+SDF meta-environment developed in Amsterdam, which used equations (rewrite rules) to define and manipulate languages.

Pure term rewriting has a well-known limitation: a plain rewrite system applies its rules according to a fixed, built-in strategy (such as innermost or outermost evaluation), giving the programmer little control over where rules fire. For many program transformations—optimizers especially—that control is exactly what you need. Visser’s insight, developed with collaborators including Zine-El-Abidine Benaissa and building on the strategy-specification work with Bas Luttik, was to make the traversal and application strategy itself a first-class, programmable object. The result, presented at ICFP'98 and refined over the following years, was Stratego.

Design Philosophy

Stratego’s design turns on a single principle: separate transformation rules from transformation control.

• Rules say what changes. A rewrite rule matches a term against a pattern and produces a replacement. Rules are small, local, and reusable.
• Strategies say how change spreads. A strategy is a program built from a handful of combinators—sequence, choice, and generic traversal—that determines how rules are applied across the whole tree.

From this separation flow the language’s other commitments:

• Generic traversal. Rather than hand-writing recursion for every tree shape, Stratego provides one-level traversal combinators (all, one, some) from which language-independent traversals like “transform everything bottom-up” (bottomup) or “innermost normalization” (innermost) are defined once and reused for any language.
• Composability. Strategies combine with sequential composition (;), deterministic choice (<+), and recursion, so complex transformations are assembled from simple, well-understood parts.
• Terms as the universal data structure. Programs are represented as first-order terms (the ATerm format in Stratego/XT), which lets tools exchange abstract syntax trees and lets generic strategies operate on any language.

Key Features

• Rewrite rules of the form Name: lhs -> rhs, optionally with a where clause for side conditions and computed bindings.
• Strategy combinators for control flow: sequence s1 ; s2, guarded/left choice s1 <+ s2, negation-by-failure, and recursive strategy definitions.
• Generic one-level traversal (all(s), one(s), some(s)) that applies a strategy to a term’s direct subterms without knowing their shape—the foundation of reusable, language-independent traversals.
• Match and build primitives (?pattern and !pattern) that decompose the language into its most elementary operations, from which rules are derived.
• Dynamic rewrite rules, which can be generated at runtime to carry context-sensitive information (for example, remembering a variable’s value while transforming the code that uses it).
• Concrete object syntax, letting rule patterns be written in the syntax of the language being transformed rather than in raw abstract-syntax terms—a feature developed with SDF-based parsing.
• The Stratego/XT toolset, a collection of components—parsers, pretty-printers, and generic libraries—for assembling complete transformation systems around Stratego specifications.

A tiny flavor of the language, defining constant folding as a rule plus a strategy that applies it everywhere until no further change is possible:

// A rule: rewrite the addition of two integer literals
EvalPlus:
  Plus(Int(i), Int(j)) -> Int(<addS>(i, j))

// A strategy: apply EvalPlus everywhere, repeatedly, until fixpoint
simplify = innermost(EvalPlus)

Evolution

Stratego evolved across a sequence of releases and an accompanying toolset:

The most significant shift over time has been the move from the standalone Stratego/XT toolchain—which compiled specifications (historically via C) and exchanged trees using the ATerm format—into the broader Spoofax language workbench, where Stratego serves as the transformation and semantics language alongside SDF-based syntax definition. The more recent Stratego 2 line, associated with Jeff Smits and Eelco Visser’s work on gradually typing strategies (SLE 2020), adds an optional type system so that the shapes of terms and transformations can be declared and checked, addressing a long-standing weakness of the originally untyped language.

Current Relevance

Stratego remains actively developed and used, primarily through Spoofax. In that setting it is a practical tool for language engineering: researchers and students designing their own domain-specific languages use Stratego to implement desugaring, name and type analysis, optimization, and code generation. Its most visible downstream application is WebDSL, a web-programming language whose compiler is built with Stratego transformations. Following Eelco Visser’s death in 2022, the Programming Languages group at TU Delft and the wider Spoofax community have continued to maintain the language and its ecosystem.

Because it targets a specialized problem—transforming programs and building compilers and DSLs—Stratego has never been a general-purpose or mainstream language. But within its niche it is highly regarded, and its ideas have spread: the strategic-rewriting approach influenced later meta-programming systems such as Rascal, and the turtles-all-the-way-down notion that traversal control should itself be programmable has become a standard part of the program-transformation vocabulary.

Why It Matters

Stratego’s contribution is conceptual as much as practical. Before it, term rewriting forced a false choice between the elegance of declarative rules and the control you need to build real transformations; you either accepted a fixed evaluation strategy or abandoned rewriting for hand-written recursive code. Stratego showed that the strategy could be a program too—first-class, composable, and reusable—so that a library of small rules and a library of generic traversals could be combined in endless ways. That separation of rules from strategies, together with generic one-level traversal combinators, is the idea most cited from Stratego, and it reshaped how the software-language-engineering community thinks about building compilers, optimizers, refactoring tools, and domain-specific languages. For a language born to build program optimizers, its most lasting optimization may have been to the discipline of program transformation itself.