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 constructor-based 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 innermost-leftmost strategies.

• Operational Semantics for Declarative Multi-Paradigm Languages,
  by Elvira Albert, Michael Hanus, Frank Huch, Francisco J. Oliver, and Germán Vidal.

  Abstract. Declarative multi-paradigm 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 multi-paradigm languages like laziness, sharing, non-determinism, 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 (big-step) semantics covering laziness, sharing and non-determinism. We also present an equivalent small-step semantics which additionally includes a number of practical features like equational constraints and external functions. Then, we introduce a deterministic version of the small-step 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 multi-paradigm languages. The developed semantics provides an appropriate foundation to model actual declarative multi-paradigm 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 'one-step' transformation on a fragment of a program. The ultimate perspective of research in this area is a high-level, language parametric, rule-based 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 trade-offs between different goals need to be made. This survey gives an overview of issues in rule-based program transformation systems, focussing on the expressivity of rule-based 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 context-sensitive 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 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.