Stratego -- Strategies for Program Transformation

Dynamic rules with the same label share the same mapping from context-variables in the left-hand side to context-variables in the right-hand side. That is, the dynamic data in a dynamic rule is determined by the context-variables in the rule.

For example, consider the following generation of a dynamic rule

generate = ?Context(x,y,z); rules( Lab : Pat1(x, es) -> Pat2(y, <op>(z, es)) )When applying

`generate`

a mapping from `Keys(x)`

to `Defined(y, z)`

is generated.
When applying `generate`

twice in a context with the same value for `x`

, the second rule overrides
the first, i.e., the first will be invisible.
Two dynamic rules with the same label share the same mapping from values to keys. If the number
of context-variables in the left-hand side of the rule is the same, subsequent rule generations
will shadow earlier ones, *even when the static part of the dynamic rule is different*.

MarkusLauer^{?} reports an example where this causes different behaviour than expected.
The strategy `gendyn`

generates two rules with label `Dyn`

. The idea of the rules is that
each time a section is encountered the section counter is incremented, and that titles
are transformed using the current section counter:

gendyn = ?n; where( <add>(n,1) => n1 ); where( rules( Dyn : tag("section", _, l) -> l where<gendyn> n1 Dyn : tag("title", _, l) -> para(sect(n),l) ))These rules are then used in the following strategy to number titles:

transform = {| Dyn : where(<gendyn>0); rec x({| Dyn : try(Dyn <+ A); all(try(x)) |}) |}However, this approach does not work because the mappings of the two

`Dyn`

rules overlap; since
the rules do not use `Keys()`

to `Defined(n1)`

(first rule) or `Defined(n)`

(second rule). The last rule to be generated will thus determine the values that both rules get.
A **workaround** in these situations is to use *two* different rule labels. In the example above the problem is solved by naming the rules `Dyn1`

and `Dyn2`

.

gendyn = ?n; where( <add>(n,1) => n1 ); where( rules( Dyn1 : tag("section", _, l) -> l where <gendyn> n1 Dyn2 : tag("title", _, l) -> para(sect(n),l) )) transform = {| Dyn1, Dyn2 : where(<gendyn>0); rec x({| Dyn1, Dyn2 : try(Dyn1 + Dyn2 <+ A); all(try(x)) |}) |}

Now the question is whether this is **a bug or a feature**. A solution would be to use the entire
static part of the left-hand side to determine which dynamic rule should be applied.
However, that would also make it more difficult to *use* the shadowing effect of overlapping
context variables. Any opinions on the matter?

-- EelcoVisser - 22 Nov 2001

I believe this is a bug and not a feature. I would intuitively expect several dynamic rules with the same name to behave just like normal rules with the same name. If anyone needs special shadowing effects, couldn't the syntax be extended so that the programmer can specify that?

Another thing; why do we only have dynamic rules, and not dynamic strategies?

-- OttoSkroveBagge - 18 Jan 2002

I've made an implementation of user-defined rules for CodeBoost, e.g. the programmer can say,

void rules() { X<int> x; simplify: f(g(x)) = fg(x); } int main(int argc, char**argv) { X<int> x; x = f(g(x)); }and this is transformed into

int main(int argc, char**argv) { X<int> x; x = fg(x); }(More or less similar to the "Transform.Playing by the rules..." paper where this is done for Haskell)

This was surprisingly easy to do, but I've run into the "Overlapping Left-Hand Sides"-bug in dynamic rules. I'm still using Stratego 0.6.2 -- is this fixed in newer versions? If not, is there a smart way of avoiding the problem?

Basically, what I'm doing is: 1. extract the user-defined rule specifications and store them as a list in the AST; 2. when the time comes to use the user-defined rules for something, the list is traversed, and dynamic rules are created:

make-rule' = ?Rule("simplify", lhs, rhs, whr); rules(simplify: x -> y where <apply-user-rule> (lhs, x, rhs) => y)Of course, this only works for a predefined set of rule names (and, with the dynamic rule bug, only for the last rule), and I haven't come up with a meaningful way of specifying "where"-clauses yet. apply-user-rule uses special match/build strategies with support for user-defined variables (represented as RuleVar

-- OttoSkroveBagge - 18 Jan 2002

No, this is not an instance of the overlapping left-hand sides problem.

Dynamic rules trigger on the left-hand side. This means that such a rule is only meaningful if has at least one variable in the left-hand side that is bound in the context of the rule. This is not the case in your make-rule'.

The problem is that you cannot directly employ dynamic rules for this application. The paper Scoped Dynamic Rewrite Rules has the following to say about this issue:

Wadler's deforestation algorithm [18] can be expressed using rewrite rules and
a simple strategy. Dynamic rules can be used to implement the folding of
recursive occurrences of the function composition being deforested. However,
this requires abstracting over object variables, which is not supported by the
dynamic rules discussed in this papers. Currently, dynamic rules can only
inherit ground terms from their de nition context. Another application that
would need abstraction over object variables are the rule pragmas of the Glas-
gow Haskell Compiler [14] that allow the user to state rewrite rules that
should be applied during compilation in addition to normal optimizations.

What you would like to do is to generate a rule

rules( simplify : ~lhs -> ~rhs )where ~t expresses the replacement of object variables with meta-variables in the term. I don't currently know how to do this, but is on my mind.

Workaround: Store the (lhs, rhs) pairs in a list and trie to match each in turn.

-- EelcoVisser - 18 Jan 2002

CategoryBugs