Non-idempotent intersection types and strong normalisation

Alexis Bernadet 1, 2 Stéphane Graham-Lengrand 1, 3
2 TYPICAL - Types, Logic and computing
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
3 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We present a typing system with non-idempotent intersection types, typing a term syntax covering three different calculi: the pure λ-calculus, the calculus with explicit substitutions λS, and the calculus with explicit substitutions, contractions and weakenings λlxr. In each of the three calculi, a term is typable if and only if it is strongly normalising, as it is the case in (many) systems with idempotent intersections. Non-idempotency brings extra information into typing trees, such as simple bounds on the longest reduction sequence reducing a term to its normal form. Strong normalisation follows, without requiring reducibility techniques. Using this, we revisit models of the λ-calculus based on filters of intersection types, and extend them to λS and λlxr. Non-idempotency simplifies a methodology, based on such filter models, that produces modular proofs of strong normalisation for well-known typing systems (e.g. System F ). We also present a filter model by means of orthogonality techniques, i.e. as an instance of an abstract notion of orthogonality model formalised in this paper and inspired by classical realisability. Compared to other instances based on terms (one of which rephrases a now standard proof of strong normalisation for the λ-calculus), the instance based on filters is shown to be better at proving strong normalisation results for λS and λlxr. Finally, the bounds on the longest reduction sequence, read off our typing trees, are refined into an exact measure, read off a specific typing tree (called principal ); in each of the three calculi, a specific reduction sequence of such length is identified. In the case of the λ-calculus, this complexity result is, for longest reduction sequences, the counterpart of de Carvalho's result for linear head-reduction sequences.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2013, 9 (4), pp.17-42
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00906778
Contributeur : Stéphane Graham-Lengrand <>
Soumis le : mercredi 20 novembre 2013 - 12:43:14
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : vendredi 21 février 2014 - 04:27:49

Fichier

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

Identifiants

  • HAL Id : hal-00906778, version 1

Collections

Citation

Alexis Bernadet, Stéphane Graham-Lengrand. Non-idempotent intersection types and strong normalisation. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2013, 9 (4), pp.17-42. 〈hal-00906778〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

103