Strategic Pattern Matching
Stratego -- Strategies for Program Transformation
Strategic Pattern Matching is a paper about extending standard first-order term pattern matching using strategies to define complex patterns. Specifically it describes the Stratego idioms recursive pattern, contextual rule and overlay definition.
Bibliographic Information
Eelco Visser. Strategic Pattern Matching. In Rewriting Techniques and Applications (RTA'99), volume 1631 of Lecture Notes in Computer Science, pages 30-44, Trento, Italy. July 1999.
Abstract
Stratego is a language for the specification of transformation
rules and strategies for applying them. The basic actions of
transformations are matching and building instantiations of
first-order term patterns. The language supports concise
formulation of generic and data type-specific term traversals.
One of the unusual features of Stratego is the separation of
scope from matching, allowing sharing of variables through
traversals. The combination of first-order patterns with
strategies forms an expressive formalism for pattern matching.
In this paper we discuss three examples of strategic pattern matching: (1) Contextual rules allow matching
and replacement of a pattern at an arbitrary depth of a
subterm of the root pattern. (2) Recursive patterns
can be used to characterize concisely the structure of
languages that form a restriction of a larger language. (3)
Overlays serve to hide the representation of a language
in another (more generic) language. These techniques are
illustrated by means of specifications in Stratego.
Download
CategoryPaper