more precise typing of rewrite strategies
The programming concept of rewrite strategies supports versatile composition of rewrite rules and control of their application. Such programmability of rewrites can possibly lead to incorrect compositions of rewrites or incorrect applications of rewrites to terms within a strategic rewriting program. In this paper, we explore the analysis of strategic rewriting programs to detect certain programming errors statically. In particular, we introduce fine-grain types to closely approximate the dynamic behavior of rewriting. We develop an expressive type system for a core rewriting language. The resulting system detects programming errors of universally unreachable and failing rewrites. Static detection of such errors can substantially reduce testing and debugging efforts and lead to a more effective use of strategic rewriting in large and complex rewriting problems.
types strategies type-checking term rewriting transformation