A Categorical Semantics for The Parallel Lambda-Calculus - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2009

A Categorical Semantics for The Parallel Lambda-Calculus

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.
Fichier principal
Vignette du fichier
RR-7063.pdf (253.5 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00424248 , version 1 (14-10-2009)

Identifiers

  • HAL Id : inria-00424248 , version 1

Cite

Germain Faure, Alexandre Miquel. A Categorical Semantics for The Parallel Lambda-Calculus. [Research Report] RR-7063, INRIA. 2009, pp.22. ⟨inria-00424248⟩
286 View
142 Download

Share

Gmail Facebook X LinkedIn More