Title
Promoting rewriting to a programming language: a compiler for non-deterministic rewrite programs in associative-commutative theories
Abstract
First-order languages based on rewrite rules share many features with functional languages, but one difference is that matching and rewriting can be made much more expressive and powerful by incorporating some built-in equational theories. To provide reasonable programming environments, compilation techniques for such languages based on rewriting have to be designed. This is the topic addressed in this paper. The proposed techniques are independent from the rewriting language, and may be useful to build a compiler for any system using rewriting modulo Associative and Commutative (AC) theories. An algorithm for many-to-one AC matching is presented, that works efficiently for a restricted class of patterns. Other patterns are transformed to fit into this class. A refined data structure, namely compact bipartite graph, allows encoding of all matching problems relative to a set of rewrite rules. A few optimisations concerning the construction of the substitution and of the reduced term are described. We also address the problem of non-determinism related to AC rewriting, and show how to handle it through the concept of strategies. We explain how an analysis of the determinism can be performed at compile time, and we illustrate the benefits of this analysis for the performance of the compiled evaluation process. Then we briefly introduce the ELAN system and its compiler, in order to give some experimental results and comparisons with other languages or rewrite engines.
Year
DOI
Venue
2001
10.1017/S0956796800003907
J. Funct. Program.
Keywords
Field
DocType
compact bipartite graph,evaluation process,elan system,first-order language,rewrite systems,strategies.,compilation,ac many-to-one matching,compilation technique,programming language,ac theories,restricted class,associative-commutative theory,non-determinism,matching problem,many-to-one ac matching,built-in equational theory,first order,data structure,strategies,bipartite graph
Data structure,Programming language,Associative property,Functional programming,Commutative property,Computer science,Compile time,Theoretical computer science,Compiler,Confluence,Rewriting
Journal
Volume
Issue
ISSN
11
2
0956-7968
Citations 
PageRank 
References 
39
1.71
46
Authors
3
Name
Order
Citations
PageRank
Hélène Kirchner11655152.66
Pierre-etienne Moreau259840.40
MoreauPierre-Etienne3391.71