A Categorical Semantics for The Parallel Lambda-Calculus

Germain Faure 1, 2 Alexandre Miquel 3
2 TYPICAL - Types, Logic and computing
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : In this report, we define a sound and complete categorical semantics for the parallel lambda-calculus, based on a notion of aggregation monad which is modular w.r.t. associativity, commutativity and idempotence. To prove completeness, we introduce a category of partial equivalence relations adapted to parallelism, in which any extension of the basic equational theory of the calculus is induced by some model. We also present abstract methods to construct models of the parallel lambda-calculus in categories where particular equations have solutions, such as the category of Scott domains and its variants, and check that G. Boudol's original semantics is a particular case of ours.
Type de document :
Rapport
[Research Report] RR-7063, INRIA. 2009, pp.22
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00424248
Contributeur : Germain Faure <>
Soumis le : mercredi 14 octobre 2009 - 15:51:27
Dernière modification le : jeudi 10 mai 2018 - 02:06:47
Document(s) archivé(s) le : mardi 16 octobre 2012 - 12:15:30

Fichier

RR-7063.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00424248, version 1

Collections

Citation

Germain Faure, Alexandre Miquel. A Categorical Semantics for The Parallel Lambda-Calculus. [Research Report] RR-7063, INRIA. 2009, pp.22. 〈inria-00424248〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

147