or rewriting calculus aims to
"integrate first-order rewriting, the lambda calculus, and non-determinism."
is basically the lambda calculus extended with constructors, let bindings,
and from Stratego "first class pattern matching and generic traversals." (32)
The semantics are well-organized:
"We first present a set of rewrite rules on the language.
By taking different subsets of these rules, we obtain lazy or strict semantics.
...all sets of rules as a whole gives a non-confluent calculus
...the lazy and strict subsets themselves are confluent.
The fact that the semantics is given as a set of rewrite rules from the language
to the language, i.e., as source-to-source transformation, means that they can be
used directly in, e.g., an optimiser or an interpreter for the language. In fact, an
interpreter based directly on these rewrite rules is given in appendix B." (23)
Another Stratego paper by the same author
Building Interpreters with Rewriting Strategies
includes lambda calculus interpreters with strategies including
"normalization, eager evaluation, lazy evaluation, and lazy evaluation
with updates. An extension with pattern matching and choice shows that
such interpreters can easily be extended."
(Possible Analogy: These papers are to Rewrite interpreters as
EOPL is to Scheme interpreters?)
Posted to LC by jon fernquest on 7/30/02; 2:14:46 AM