Abstract
We study the problem of local and asynchronous computation in the context of multiplicative exponential linear logic (MELL) proof nets. The main novelty is in a complete set of rewriting rules for cut-elimination in presence of weakening (which requires garbage collection). The proposed reduction system is strongly normalizing and confluent.
Partially supported by: HCM Project CHRX-CT93-0046 and CNR GNSAGA (Guerrini, Martini); BRA 8130 LOMAPS (Masini).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andrea Asperti, Vincent Danos, Cosimo Laneve, and Laurent Regnier. Paths in the lambda-calculus: three years of communications without understanding. In Proceedings of 9th Annual Symposium on Logic in Computer Science, pages 426–436, Paris, France, July 1994. IEEE.
Andrea Asperti and Stefano Guerrini. The Optimal Implementation of Functional Programming Languages. Cambridge University Press, 1997. To appear.
Andrea Asperti and Cosimo Laneve. Interaction system II: The practice of optimal reductions. Theoretical Computer Science, 159(2):191–244, 3 June 1996.
Andrea Asperti. Linear logic, comonads and optimal reductions. Fundamenta infomaticae, 22:3–22, 1995.
Richard Banach. Sequent reconstruction in LLM—A sweepline proof. Annals of Pure and Applied Logic, 73:277–295, 1995.
Georges Gonthier, Martín Abadi, and Jean-Jacques Lévy. Linear logic without boxes. In Proceedings of 7th Annual Symposium on Logic in Computer Science, pages 223–234, Santa Cruz, CA, June 1992. IEEE.
Jean-Yves Girard. Linear logic. Theoretical Computer Science, 50(1):1–102, 1987.
Jean-Yves Girard. Towards a geometry of interaction. Number 92 in Contemporary Mathematics, pages 69–108. AMS, 1989.
Stefano Guerrini and Andrea Masini. Parsing MELL proof nets. Technical report, Dipartimento di Informatica, Pisa, 1996.
Stefano Guerrini, Simone Martini, and Andrea Masini. Coherence for sharing proof-nets. In Harald Ganzinger, editor, RTA '96, number 1103 in LNCS, pages 215–229, New Brunswick, NJ, July 1996. Springer-Verlag.
Stefano Guerrini. Theoretical and Practical Issues of Optimal Implementations of Functional Languages. Phd thesis, Dipartimento di Informatica, Pisa, 1996. TD-3/96.
John Lamping. An algorithm for optimal lambda calculus reduction. In Proceedings of Seventeenth Annual ACM Symposyum on Principles of Programming Languages, pages 16–30, San Francisco, California, January 1990. ACM.
Jean-Jacques Lévy. Réductions Correctes et Optimales dans le lambdacalcul. PhD Thesis, Université Paris VII, 1978.
S. Martini and A. Masini. On the fine structure of the exponential rule. In J.-Y. Girard, Y. Lafont, and L. Regnier, editors, Advances in Linear Logic, pages 197–210. Cambridge University Press, 1995. Proceedings of the Workshop on Linear Logic, Ithaca, New York, June 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guerrini, S., Martini, S., Masini, A. (1997). Proof nets, garbage, and computations. In: de Groote, P., Roger Hindley, J. (eds) Typed Lambda Calculi and Applications. TLCA 1997. Lecture Notes in Computer Science, vol 1210. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62688-3_36
Download citation
DOI: https://doi.org/10.1007/3-540-62688-3_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62688-6
Online ISBN: 978-3-540-68438-1
eBook Packages: Springer Book Archive