The Rewriting Calculus
Résumé
The Rho-calculus is a new calculus that integrates in a uniform and simple setting first-order rewriting, lambda-calculus and non-deterministic computations. This paper describes the calculus from its syntax to its basic properties in the untyped case. We show how it embeds first-order conditional rewriting and lambda-calculus. Finally we use the Rho-calculus to give an operational semantics to the rewrite based language Elan.