Normal Forms for the Algebraic Lambda-Calculus

Michele Alberti 1, 2
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : We study the problem of defining normal forms of terms for the algebraic -calculus, an extension of the pure -calculus where linear combinations of terms are first-class entities: the set of terms is enriched with a structure of vector space, or module, over a fixed semiring. Towards a solution to the problem, we propose a variant of the original reduction notion of terms which avoids annoying behaviours affecting the original version, but we find it not even locally confluent. Finally, we consider reduction of linear combinations of terms over the semiring of polynomials with non-negative integer coefficients: terms coefficients are replaced by indeterminates and then, after reduction has taken placed, restored back to their original value by an evaluation function. Such a special setting permits us to talk about normal forms of terms and, via an evaluation function, to define such notion for any semiring.
Type de document :
Communication dans un congrès
Damien Pous and Christine Tasson. JFLA - Journées francophones des langages applicatifs, Feb 2013, Aussois, France. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00779911
Contributeur : Ist Inria Saclay <>
Soumis le : mardi 22 janvier 2013 - 17:02:29
Dernière modification le : jeudi 18 janvier 2018 - 02:09:33
Document(s) archivé(s) le : samedi 1 avril 2017 - 08:22:49

Fichier

jfla2013-14.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00779911, version 1

Collections

Citation

Michele Alberti. Normal Forms for the Algebraic Lambda-Calculus. Damien Pous and Christine Tasson. JFLA - Journées francophones des langages applicatifs, Feb 2013, Aussois, France. 2013. 〈hal-00779911〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

225