Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-11T08:47:48.042Z Has data issue: false hasContentIssue false

A semantics for lambda calculi with resources

Published online by Cambridge University Press:  01 August 1999

GÉRARD BOUDOL
Affiliation:
INRIA, BP93, F-06902 Sophia Antipolis Cedex
PIERRE-LOUIS CURIEN
Affiliation:
ENS DMI, 45 Rue d'Ulm, F-75230 Paris, Cedex 05
CAROLINA LAVATELLI
Affiliation:
ENS DMI, 45 Rue d'Ulm, F-75230 Paris, Cedex 05
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present the λ-calculus with resources λr, and two variants of it: a deterministic restriction λm and an extension λcr with a convergence testing operator. These calculi provide a control on the substitution process – deadlocks may arise if not enough resources are available to carry out all the substitutions needed to pursue a computation. The design of these calculi was motivated by Milner's encoding of the λ-calculus in the π-calculus. As Boudol and Laneve have shown elsewhere, the discriminating power of λm (given by the contextual observational equivalence) over λ-terms coincides with that induced by Milner's π-encoding, and coincides also with that provided by the lazy algebraic semantics (Lévy–Longo trees). The main contribution of this paper is model-theoretic. We define and solve an appropriate domain equation, and show that the model thus obtained is fully abstract with respect to λcr. The techniques used are in the line of those used by Abramsky for the lazy λ-calculus, the main departure being that the resource-consciousness of our calculi leads us to introduce a non-idempotent form of intersection types.

Type
Research Article
Copyright
© 1999 Cambridge University Press