More precise typing of rewrite strategies

Azamat Mametjanov, Victor Winter, Ralf Lämmel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th Workshop on Language Descriptions, Tools and Applications, LDTA'11
DOIs
StatePublished - 2011
Event11th Workshop on Language Descriptions, Tools and Applications, LDTA 2011 - Saarbrucken, Germany
Duration: Mar 26 2011Mar 27 2011

Publication series

NameProceedings of the 11th Workshop on Language Descriptions, Tools and Applications, LDTA'11

Conference

Conference11th Workshop on Language Descriptions, Tools and Applications, LDTA 2011
CountryGermany
CitySaarbrucken
Period3/26/113/27/11

Keywords

  • strategies
  • term rewriting
  • transformation
  • type-checking
  • types

ASJC Scopus subject areas

  • Language and Linguistics
  • Computer Science Applications

Fingerprint Dive into the research topics of 'More precise typing of rewrite strategies'. Together they form a unique fingerprint.

Cite this