Previous Page Strategies Specification Non-Deterministic Computations Rules Specifications Modularity and parameterization Next Page

# ELAN - Strategies Specification

A labelled rule is the most elementary strategy and is called a primal strategy. The result of applying a rule labelled lab on a term t is a set of terms. Note that there may be several rules with the same label. If no rule labelled lab applies on the term t, the set of results is empty and we say that the rule lab fails. To understand why applying one rule at the top of a term can yield several results, one has to know that local assignments in a rewrite rule can call strategies on subterms. If the strategy in a local assignment has several results, so has the rewrite rule. A labelled rule lab can be considered as the simplest form of a strategy which returns all results of the rule application. As any strategy, lab can also be encapsulated by an operator dc one that returns a non-deterministically chosen result. In that case, dc one(lab) returns at most one result. In addition ELAN provides a few built-in strategy operators that take possibly several strategies as arguments and can be used to build new strategies:
• the concatenation operator denoted ; builds the sequential composition of two strategies S1 and S2. The strategy S1 ; S2 fails if S1 fails, otherwise it returns all results (maybe none) of S2 applied to the results of S1;
• the dk operator, with a variable arity, is an abbreviation of dont know choose. dk(S1,...,Sn) takes all strategies given as arguments, and returns, for each of them the set of all its results. dk(S1,...,Sn) fails if all strategies S1,...,Sn fail.
• the dc operator, with a variable arity, is an abbreviation of dont care choose. dc(S1,...,Sn) selects only one strategy that does not fail among its arguments, say Si, and returns all its results. dc(S1,...,Sn) fails if all strategies S1,...,Sn fail. How to choose Si is not specified.
• a specific way to choose an Si is provided by the first operator that selects the first strategy that does not fail among its arguments, and returns all its results. So if Si is selected, this means that all strategies Si-1 have failed. Again first(S1,...,Sn) fails if all strategies S1,...,Sn fail.
• if only one result is wanted, one can use the operators first oneor dc one that select a non-failing strategy among their arguments (either the first or anyone respectively), and return a non-deterministically chosen result of the selected strategy.
• id is the identity strategy that does nothing, and never fails.
• fail always fails and returns an empty set of results.
• repeat*(S) iterates the strategy S until it fails and then returns the last obtained result. repeat*(S) never fails and terminates only when S fails.
• iterate*(S) is similar to repeat*(S), except that it returns all intermediate results of successive applications of S.
In addition to these primitive strategy operators, the user can define new strategy operators and strategy rules for their evaluation [14].