A type system for embedded rewriting languages with associative pattern matching: from theory to practice - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

A type system for embedded rewriting languages with associative pattern matching: from theory to practice

Résumé

Programmers are often interested in a way to write error-free programs, i.e. to avoid undesired behaviors. In this context, a type system was conceived as the formal method for speci cation and proof of programs written in the Tom rewriting language. The Tom programming language is an extension of Java that adds pattern matching, more particularly associative pattern matching, and reduction strategies. Accordingly, we aim to make the static typing of the Tom constructs, in particular matching constructs, compatible with the features of Java. This paper presents a type system with nominal subtyping for Tom, that is compatible with the Java type system, and that performs both type inference. We adopted the idea that type inference is a form of type checking and included equality and subtyping constraints inside typing judgments. We propose a constraint-based type inference system to infer types of variables occurring in algebraic terms. Then, we de fine rules to solve equality constraints by uni cation. For the resolution of subtyping constraints, we introduce rules for a combination of constraint propagation, generation of solution and garbage collecting of remaining constraints.
Fichier principal
Vignette du fichier
Implementation.pdf (413.78 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00643808 , version 1 (23-11-2011)
hal-00643808 , version 2 (03-12-2011)

Identifiants

  • HAL Id : hal-00643808 , version 2

Citer

Cláudia Tavares. A type system for embedded rewriting languages with associative pattern matching: from theory to practice. [Research Report] 2011, pp.20. ⟨hal-00643808v2⟩
101 Consultations
56 Téléchargements

Partager

Gmail Facebook X LinkedIn More