Seminars & Events

Mathematics and Computer Science Division
"Type Analysis of Rewrite Strategies"

DATE: February 15, 2011
TIME: 10:30 AM - 11:30 AM
SPEAKER: Az Mametjanov, Type Analysis of Rewrite Strategies
LOCATION: Building 240 Seminar Room 4301, Argonne National Laboratory
HOST: Boyana Norris

Description:
Rule-based program transformation employs term rewriting strategies to algorithmically control rewrite sequences. The primary abstractions of rewriting strategies -- rewrite rules, combinators and term traversals -- provide basic yet powerful constructs enabling complex program transformation. Due to the programmability of rewrites, errors are often made because of incorrect compositions or incorrect applications of rewrites to a term within a strategic rewriting program. In practice, ill-formed strategies are the Achilles heel of strategic rewriting and present a major obstacle to the effective application of strategies to large complex problems. We propose a type analysis geared towards term rewriting strategies to detect and remove errors statically. Novel aspects of this analysis are (1) more precise type-checking enabled by the data type constructor-based typing of terms and patterns, and (2) integration of compositional behavior of strategies to model arguments and results of rewrite rule compositions. The primary benefit of such analysis is automated detection of ill-formed strategies, which in turn can significantly reduce the development and testing of program transformations. The analysis is demonstrated on TL -- a representative transformation language supporting all of the strategic abstractions. We also discuss several applications of program transformation such as automated adaptation of Java libraries toward non-standard JVM profiles and annotation-based transformation for performance optimization.

Save the event to your calendar [schedule.ics]