Recent advances in the foundations and the implementations of
functional logic programming languages originate from
far-reaching results on narrowing evaluation strategies.
Narrowing is a computation similar to rewriting which yields
substitutions in addition to normal forms.
In functional logic programming, the classes of rewrite
systems to which narrowing is applied are, for the most part,
subclasses of the constructor-based, possibly conditional,
rewrite systems. Many interesting narrowing strategies,
particularly for the smallest subclasses of the constructor-based
rewrite systems, are generalizations of well-known
rewrite strategies. However, some strategies for larger
non-confluents subclasses have been developed just for
functional logic computations.
This paper discusses the elements that play a relevant
role in evaluation strategies for functional logic computations,
describes some important classes of rewrite systems that
model functional logic programs, shows examples of the
differences in expressiveness provided by these classes, and
reviews the characteristics of narrowing strategies proposed
for each class of rewrite systems.