Non Deterministic Choice

Stratego -- Strategies for Program Transformation
The non-deterministic local choice operator s1 + s2 chooses one of the strategies s1 or s2 to apply. If the one chose fails, the other one is tried.

The + operator is local because once one of the strategies has succeeded the choice is committed, even if the continuation of the choice fails on the result. If backtracking to the other strategy is desired one should used the GlobalChoice? operator ++.

The + operator is non-determinstic sine the EvaluationOrder in which the strategies are tried is not defined. The StrategoCompiler is free to choose an order. If complete control over the evaluation order is needed one should use the DeterministicChoice operator <-.

In Stratego it is permitted to define several RewriteRules with the same label. This interpreted as the composition with + of the rules.

It would be useful to DetectOverlappingRules in a non-deterministic choice.

-- EelcoVisser - 17 Mar 2002

CategoryGlossary | StrategoGlossary