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 S_{1} and S_{2}. The strategy
S_{1}
; S_{2} fails if S_{1} fails, otherwise it
returns all results (maybe none) of S_{2} applied to the
results of S_{1};
the dk operator, with a variable arity, is an abbreviation of dont
know choose. dk(S_{1},...,S_{n}) takes all strategies
given as arguments, and returns, for each of them the set of all its results.
dk(S_{1},...,S_{n})
fails if all strategies S_{1},...,S_{n} fail.
the dc operator, with a variable arity, is an abbreviation of dont
care choose. dc(S_{1},...,S_{n}) selects only
one strategy that does not fail among its arguments, say S_{i},
and returns all its results.
dc(S_{1},...,S_{n})
fails if all strategies S_{1},...,S_{n} fail. How
to choose S_{i} is not specified.
a specific way to choose an S_{i} 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 S_{i} is selected, this
means that all strategies
S_{i-1} have failed. Again first(S_{1},...,S_{n})
fails if all strategies S_{1},...,S_{n} 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].