Optimizing pattern matching compilation by program transformation

Emilie Balland 1 Pierre-Etienne Moreau 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Motivated by the promotion of rewriting techniques and their use in major industrial applications, we have designed Tom: a pattern matching layer on top of conventional programming languages. The main originality is to support pattern matching against native data-structures like objects or records. While crucial to the efficient implementation of functional languages as well as rewrite rule based languages, in our case, this combination of algebraic constructs with arbitrary native data-structures makes the pattern matching algorithm more difficult to compile. In particular, well-known many-to-one automaton-based techniques cannot be used. We present a two-stages approaches which first compiles pattern matching constructs in a naive way, and then optimize the resulting code by program transformation using rewriting. As a benefit, the compilation algorithm is simpler, easier to extend, and the resulting pattern matching code is almost as efficient as best known implementations.
Type de document :
Communication dans un congrès
Reiko Heckel and Jean-Marie Favre and Tom Mens. 3rd Workshop on Software Evolution through Transformations SeTra 2006, Sep 2006, Natal, Rio Grande do Norte, Brazil. EASST, 3, 2006, Electronic Communications of EASST; Software Evolution through Transformations 2006
Liste complète des métadonnées


https://hal.inria.fr/inria-00000763
Contributeur : Emilie Balland <>
Soumis le : jeudi 15 juin 2006 - 14:50:43
Dernière modification le : mardi 25 octobre 2016 - 17:02:37
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:04:17

Fichier

Identifiants

  • HAL Id : inria-00000763, version 3

Collections

Citation

Emilie Balland, Pierre-Etienne Moreau. Optimizing pattern matching compilation by program transformation. Reiko Heckel and Jean-Marie Favre and Tom Mens. 3rd Workshop on Software Evolution through Transformations SeTra 2006, Sep 2006, Natal, Rio Grande do Norte, Brazil. EASST, 3, 2006, Electronic Communications of EASST; Software Evolution through Transformations 2006. <inria-00000763v3>

Partager

Métriques

Consultations de
la notice

284

Téléchargements du document

141