Language Independent Traversals For Program Transformation
Stratego -- Strategies for Program Transformation
Language Independent Traversals for Program Transformation.
EelcoVisser. Workshop on
GenericProgramming (
WGP'00), July 2000. Ponte de Lima, Portugal.
ps.gz
Abstract
Many language processing operations have a generic underlying
algorithm. However, these generic algorithms either have to be
implemented specifically for the language under consideration
or the language needs to be encoded in a generic format that
the generic algorithm works on. Stratego is a language for
program transformation that supports both specific and generic
views of data types.
A Stratego program defines a transformation on first-order
ground terms. Transformation rules define single
transformation steps. Transformation rules are combined into
transformation
strategies by means of combinators that
determine where and in what order rules are applied. These
combinators include: primitives for traversal to the direct
subterms of a node, allowing the definition of many kinds of
full term traversals; full control over recursion in
traversals; patterns as first-class citizens; generic term
construction and deconstruction.
These features create a setting in which it is possible to
combine generic traversal with data type specific pattern
matching, and separating logic (transformation, pattern
matching) from control (traversal). This makes it possible to
give language independent descriptions of language processing
operations that can be instantiated to a specific language by
providing the patterns of the relevant constructs. These
generic algorithms only touch relevant constructors and do not
need to know the entire datatype, making the algorithms
insensitive to changes in the abstract syntax that do not
affect the constructors relevant to the operation.
Stratego is currently implemented by compilation to C code.
All constructs of the language are implemented directly, i.e.,
the compiled program is as large as the specification, in
contrast to approaches that rely on preprocessing or program
generation which may have a scaling problem when dealing with
large languages.
The approach to generic programming in Stratego is illustrated
by means of several examples including free variable
extraction, bound variable renaming, substitution and
syntactic unification.
CategoryPaper | --
EelcoVisser - 14 May 2001