Reflection in conditional rewriting logic

AbstractWe recall general metalogical axioms for a reflective logic based on the notion of a universal theory, that is, a theory that can simulate the deductions of all other theories in a class of theories of interest, including itself. We then show that conditional rewriting logic is reflective, generalizing in two stages: first to the unsorted conditional case, and then to the many-sorted conditional case, the already known result for unconditional and unsorted rewriting logic (Reflection in Rewriting Logic: Metalogical Foundations and Metaprogramming Applications. CSLI Publications, 2000). This work should be seen as providing foundations for many useful applications of rewriting logic reflection. The results presented here have greatly influenced the design of the Maude language, which implements rewriting logic and supports its reflective capabilities, and have been used as a theoretical foundation for applications such as internal rewrite strategies, reflective design of theorem proving tools, module algebra and metaprogramming, and metareasoning in metalogical frameworks