Declarative Graph Rewriting
Stc
Date: 2010-07-01
Time: 11:00
Room:
BBL 023
Speaker: Vali Georgescul
Title: Declarative Graph Rewriting (thesis defense)
Abstract
Transformation systems are commonly used in compiler technology for optimizers or code generators, but also for more general program transformations. Term rewriting is a common paradigm used to design such systems. This approach is particularly attractive when used with declarative rewrite rules, usually producing more maintainable systems as compared to other ad-hoc alternatives. Unfortunately, terms are not expressive enough to handle all cases encountered in compiler design. Thus, compiler designers have historically used a mixed representation for the underlying data structures, using tree-like terms for expressions and graphs for the whole program. While there has been a significant amount of research on graph rewriting, there are few production quality compilers that use graph rewriting to implement transformations and optimizations. Our goal is to explore the solution space and implement a declarative rule based graph rewriting system. Although we aim to integrate the system into a production quality compiler, the system can nevertheless be used for general graph transforamtions independent of the underlying domain.
