WRS

Reduction Strategies in Rewriting and Programming
(JSC special issue)
B. Gramlich and
S. Lucas
(editors)
Journal of Symbolic Computation
volume 40, issue 1,
Elsevier, May 2005.
This special issue of the
Journal of Symbolic Computation
contains revised and extended versions of a selection of
papers appeared in the first two editions of the workshop:
WRS 2001 and
WRS 2002.
Four papers were selected for publication in this volume:

Tree Automata for Rewrite Strategies,
by Pierre Réty and Julie Vuotto.
Abstract.
For a constructorbased rewrite system R, a regular set of ground terms
E, and assuming some additional restrictions,
we build finite tree automata that recognize the descendants of
E, i.e., the terms issued from E by rewriting, according to
innermost, outermost, leftmost, and innermostleftmost strategies.
 Operational Semantics for Declarative MultiParadigm
Languages,
by Elvira Albert, Michael Hanus, Frank Huch, Francisco
J. Oliver, and Germán Vidal.
Abstract.
Declarative multiparadigm languages combine the most important
features of functional, logic and concurrent programming. The
computational model of such integrated languages is usually
based on a combination of two different operational
principles: narrowing and residuation. This work is motivated
by the fact that a precise definition of an
operational semantics including all aspects of modern multiparadigm
languages like laziness, sharing, nondeterminism,
equational constraints, external functions, concurrency, etc. does not exist.
Therefore, in this article, we present the first rigorous operational
description covering all the aforementioned
features in a precise and understandable manner.
We develop our operational semantics in several steps. First, we
define a natural (bigstep) semantics covering laziness, sharing
and nondeterminism. We also present an equivalent smallstep semantics
which additionally includes a number of practical features like equational
constraints and external functions. Then, we introduce a deterministic
version of the smallstep semantics which makes the search strategy
explicit; this is essential for profiling, tracing, debugging, etc.
Finally, the deterministic semantics is extended in order to cover
the concurrent facilities of modern declarative multiparadigm languages. The
developed semantics
provides an appropriate foundation to model actual declarative
multiparadigm languages like Curry.
The complete operational semantics has been implemented and used
for various programming tools.
 A Survey of Rewriting Strategies in Program
Transformation Systems,
by Eelco Visser.
Abstract.
Program transformation is the mechanical manipulation of a program in
order to improve it relative to some cost function and is understood
broadly as the domain of computation where programs are the data. The
natural basic building blocks of the domain of program transformation
are transformation rules expressing a 'onestep' transformation
on a fragment of a program. The ultimate perspective of research in
this area is a highlevel, language parametric, rulebased program
transformation system, which supports a wide range of transformations,
admitting efficient implementations that scale to large programs.
This situation has not yet been reached, as tradeoffs between
different goals need to be made. This survey gives an overview of
issues in rulebased program transformation systems, focussing on the
expressivity of rulebased program transformation systems and in
particular on transformation strategies available in various
approaches. The survey covers term rewriting, extensions of basic term
rewriting, tree parsing strategies, systems with programmable
strategies, traversal strategies, and contextsensitive rules.
 Evaluation Strategies for Functional Logic Programming,
by Sergio Antoy.
Abstract.
Recent advances in the foundations and the implementations of
functional logic programming languages originate from
farreaching 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 constructorbased, possibly conditional,
rewrite systems. Many interesting narrowing strategies,
particularly for the smallest subclasses of the constructorbased
rewrite systems, are generalizations of wellknown
rewrite strategies. However, some strategies for larger
nonconfluents 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.
Last update July 2005 # slucas@dsic.upv.es
