Overlapping Left-Hand Sides; Bug or Feature?

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

---

CategoryBugs^? | CategoryToDo^?