A constraint language for algebraic term based on rewriting theory

François Prugniel 1 Pierre-Etienne Moreau 1 Horatiu Cirstea 1
1 PAREO - Formal islands: foundations and applications
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A key feature of Model Driven Engineering is the ability to define meta-models, but also constraints that have to be satisfied by their instances. Constraints are expressed in OCL (Object Constraint Language), which became a standard. OCL Constraints offer the possibility to capture properties which cannot be easily encoded in the meta-model. In the programming language community, instead of meta-models, we generally use grammars or algebraic signatures to define the syntax of the programs or abstract syntax trees (AST) we consider. But unfortunately, even when considering rich formalisms such as many-sorted signatures with subtyping or dependent types, they are not expressive enough to encode in a simple way some subsets of terms we want to consider. For instance arithmetic expressions which have at most two levels of plus operator, this includes a, a+b, (a+b)+(b+c), but not a+(b+(c+d)) for instance. There is a need for a constraint language dedicated to tree based data structures such as terms and AST. In this paper we present both a language to express constraints on trees, and a compilation scheme that shows how to translate constraints into an executable formalism based on term rewriting and strategies.
Type de document :
Rapport
[Research Report] 2011, pp.8
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00646343
Contributeur : François Prugniel <>
Soumis le : mardi 29 novembre 2011 - 16:55:25
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 17:55:46

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00646343, version 1

Collections

Citation

François Prugniel, Pierre-Etienne Moreau, Horatiu Cirstea. A constraint language for algebraic term based on rewriting theory. [Research Report] 2011, pp.8. 〈hal-00646343〉

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

105