Term Annotation

Stratego -- Strategies for Program Transformation


Stratego uses terms to represent the abstract syntax of programs or documents. A term consists of a constructor and a list of argument terms. Sometimes it is useful to record additional information about a term without adapting its structure, i.e., creating a constructor with additional arguments. For this purpose terms can be annotated. Support for TermAnnotations has been available from StrategoRelease07.

In Stratego a term always has a list of annotations. This is the empty list if a term doesn't have any annotations. term annotation uses the syntax

  t1 { a1 }

where term a1 is an annotation of term t1. If you want to add more annotations to a term you can use the same syntax you would use for the content of a list:

  t1 { a1, a2, a3 }

Annotations in match and build

The annotations of a term can be retrieved in a pattern match and set in a build. For example the following build will create a term Plus(1, 2) with the term Int as the only annotation.

  !Plus(1, 2){Int}

Naturally the annotation syntax can also be used in a match:

  ?Plus(1, 2){Int}

Note however that this match only accepts Plus(1, 2) terms with just one annotation, which should be the empty contstructor application Int. This match will thus not allow other annotations.

Annotations in RewriteRules

Because a RewriteRule is just sugar for a StrategyDefinition, the usage of annotations in rules is just as you would expect. The following rule checks that the two subterms of the Plus have annotation Int and then attaches the annotation Int to the whole term:

  TypeCheck :
    Plus(e1{Int}, e2{Int}) -> Plus(e1, e2){Int}

Annotations in CongruenceOperators

Also congruences over annotations are supported. Thus, if s1 and s2 are strategies, then s1{s2} is also a strategy, which applies s1 to the term and s2 to its annotations. Notice that s2 is applied to the annotations. Therefor you have to use a list congruence [s3] if you want to apply s3 to the only annotation of s3. If you want to apply a strategy to all annotations, you can use a map.

Some examples:

   <id{[inc]}>      Plus(1, 2){3}       => Plus(1, 2){4}
   <id{[inc, inc]}> Plus(1, 2){3, 4}    => Plus(1, 2){4, 5}
   <id{map(inc)}>   Plus(1, 2){3, 4, 5} => Plus(1, 2){4, 5, 6}

Frequent problems

Annotation is list

Remember that if you apply a !Plus(1, 2){x}, the term x will be the only annotation. This is also the case if x is a list. Example:

   SomeRule: xs -> Plus(5, 6){xs}

   <SomeRule> ["a", "b", "c"] => Plus(5, 6){["a", "b", "c"]}

Notice that in this example the result is not Plus(5, 6){"a", "b", "c"}. The Plus term will have just one annotation, which is the list ["a", "b", "c"]. You can use ListMatching to solve this problem:

   SomeRule: [xs*] -> Plus(5, 6){xs*}

   <SomeRule> ["a", "b", "c"] => Plus(5, 6){"a", "b", "c"}

You can also use ListMatching inside the annotation part of a match:

   Incr: Int(x){as*} -> Int(<inc> x){as*}

   <Incr> Int(5){Int} => Int(6){Int}

Preserving annotations

Because annotations are not part of the structure there is a huge risk of losing them. For example the following RewriteRule will already drop the annotations of the Int term.

   Incr: Int(x) -> Int(<inc> x)

You can create a strategy into an annotation preserving strategy with preserve-annos in the annotations module of the StrategoStandardLibrary?.

The GenericTermTraversal operators all, some and one and CongruenceOperators preserve annotations. If the Incr rule is implemented as congruence, the annotations will be preserved:

   Incr = Int(inc)

   <Incr> Int(5){Int} => Int(6){Int}

-- MartinBravenboer - 25 Jan 2003


Stratego.TermAnnotation moved from Stratego.TermAnnotations on 06 Jan 2002 - 16:34 by EelcoVisser - put it back