Reduction Strategies in Rewriting and Programming
(JSC special issue)
B. Gramlich and
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
Four papers were selected for publication in this volume:
Tree Automata for Rewrite Strategies,
by Pierre Réty and Julie Vuotto.
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
by Elvira Albert, Michael Hanus, Frank Huch, Francisco
J. Oliver, and Germán Vidal.
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
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
by Eelco Visser.
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.
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.
Last update July 2005 # firstname.lastname@example.org