Separation Of Rules And Strategies

You insist on the importance of separation of concerns, in particular in separation between rules and strategies, so that rules become basic strategies on top of which you build more complex transformation strategies. However, when you introduce match and build strategies and "break" the rules, these disappear completely and everything becomes just strategies. How do you explain or justify this?

-- Narcisco Marti Oliet

This seems indeed paradoxical, but it is not, in fact.

The 'separation of rules and strategies' is a programming idiom that is not the same as the 'linguistic distinction between rules and strategies'.

According to the principle of separation of rules and strategies, it should be possible to define transformation rules separately from the strategy in which they are applied. Thus, a rule

  PlusZero : Plus(x, Zero) -> x

defines a single transformation step regardless of the strategy. It can be used in an innermost normalization of terms

  innermost(PlusZero + ...)

or in single bottomup traversal

  bottomup(try(PlusZero + ...)

To support this separation you need a language in which rules can be defined as first-class citizens, i.e., it should be possible to combine rules in different strategies.

In the entire discussion above we regarded a 'rule' as a `basic transformation step'. Nothing in the separation principle requires that rules are defined in as specific way. In Stratego rules are implemented by the atomic transformation operatations match and build. Thus, the rule above is nothing but syntactic sugar for

  PlusZero  = ?Plus(x, Zero); !x

So, linguistically speaking, there is no distinction between rules and strategies.

The important point is that we can distinguish rule-like entities such as PlusZero from strategy-like entities such as innermost, and that rule-like things are first-class.

-- EelcoVisser - 23 May 2002