Dynamic Rule Semantics

Dynamic rules allow the run-time addition of rewrite rules. This can be used to model context-sensitive rewriting and has a host of applications in program transformation.

This page discusses issues in the semantics of dynamic rules

---

---

Bug: Overlapping left-hand sides

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 any context variables in the left-hand side, the mapping generated for the rules is 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

Implementing User-Defined Rules with Dynamic Rules?

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^?("name") in the AST) -- I'll send you the code when I've tested it more.

-- 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

Fix: Taking entire left-hand side into account

The desugaring of dynamic rules has been changed to repair the problems arising when two dynamic rules with the same name have

different left-hand sides, but the same number of context variables in the left-hand side (see discussion below). The key that is used for a dynamic rule is now the entire left-hand side, modulo non-context variables. The new implementation will also make it easier to define (or even generate) operations for saving, restoring, and intersecting sets of dynamic rules, as used in data-flow optimizations.

The bugfix will be available in StrategoRelease09 (beta8).

-- EelcoVisser - 22 Dec 2002

Bug: Rewriting terms with annotations

After some hours of debugging my Tiger to C compiler, I've found a problem in the application of dynamic rules to terms with annotations in StrategoXT 0.9.x . A dynamic rule without annotations in the lhs cannot be applied to a term with annotations.

Of course this is not the behaviour of static rules. This problem breaks all components that use dynamic rules and annotations extensively (like my Tiger to C compiler). In the 0.8 releases of Stratego the behaviour was correct (like static rules).

This works:

-------------------
module dyn-test
imports option dynamic-rules

strategies

   main =
     rules(DynRule : None() -> Some("Blaat"))
     ; <DynRule> None()
-------------------

But this results in a rewriting failed:

-------------------
module dyn-test
imports option dynamic-rules

strategies

   main =
     rules(DynRule : None() -> Some("Blaat"))
     ; <DynRule> None(){"whatever"}
-------------------

-- MartinBravenboer - 29 Jul 2003

The change in behaviour from 0.8 to 0.9.x is due to the change in the semantics of dynamic rules. (See above) According to this semantics the entire term is relevant for the mapping from left-hand side to right-hand side. Repairing this requires stripping off the annotations from a term before doing the lookup in the rule table. (Unless the lhs contains annotations,of course.) Repair is in the release plan for StrategoRelease093.

Workaround: explicitly match on the list of annotations:

-------------------
   test2 =
     rules(DynRule2 : None(){t*} -> Some("Blaat"))
     ; <DynRule2> None(){"whatever"}
     ; <DynRule2> None()
-------------------

-- EelcoVisser - 29 Jul 2003

---

CategoryBugs^? | CategoryToDo^?