From Rogue to MicroRogue

The Rewriting Calculus has been proposed as a foundational system combining the central ideas of λ-calculus and term rewriting. The rewriting is explicit, in the sense that rules must be applied explicitly to terms to transform them. This paper begins with an imperative version of the Rewriting Calculus called Rogue. It then shows how Rogue can itself be conveniently implemented by an even more foundational system called MicroRogue. MicroRogue rewrites terms using a global set of first-order rules. Rules can be enabled, disabled, and dynamically added in scopes, which can be pushed and popped. MicroRogue also provides mechanisms for specifying evaluation order. Using these primitives, a Rogue interpreter can be implemented in less than 40 lines of MicroRogue code.