Abstract
Despite decades of research in the λ-calculus, the syntactic properties of the weak λ-calculus did not receive great attention. However, this theory is more relevant for the implementation of programming languages than the usual theory of the strong λ-calculus. In fact, the frameworks of weak explicit substitutions, or computational monads, or λ-calculus with a let statement, or super-combinators, were developed for adhoc purposes related to programming language implementation. In this paper, we concentrate on sharing of subterms in a confluent variant of the weak λ-calculus. We introduce a labeling of this calculus that expresses a confluent theory of reductions with sharing, independent of the reduction strategy. We finally state that Wadsworth’s evaluation technique with sharing of subterms corresponds to our formal setting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abadi, M., Cardelli, L., Curien, P.-L., Lévy, J.-J.: Explicit substitutions. Journal of Functional Programming 6(2), 299–327 (1996)
Ariola, Z.M., Felleisen, M., Maraist, J., Odersky, M., Wadler, P.: A call-by-need lambda calculus. In: Proc. 22nd ACM Symposium on Principles of Programming Languages, January 1995, pp. 233–246 (1995)
Asperti, A., Coppola, P., Martini, S. (Optimal) duplication is not elementary recursive. Information and Computation 193/1, 21–56 (2004)
Asperti, A., Guerrini, S.: The Optimal Implementation of Functional Programming Languages. Cambridge University Press, Cambridge (1999)
Barendregt, H.P.: The Lambda Calculus, Its Syntax and Semantics. North-Holland, Amsterdam (1981)
Çağman, N., Hindley, J.R̃.: Combinatory weak reduction in lambda calculus. Theoretical Computer Science 198, 239–249 (1998)
Curien, P.-L., Hardin, T., Lévy, J.-J.: Confluence properties of weak and strong calculi of explicit substitutions. Journal of the ACM 43(2), 362–397 (1996)
Fernández, M., Mackie, I.: Closed reductions in the lambda-calculus. In: Flum, J., Rodríguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol. 1683, pp. 220–234. Springer, Heidelberg (1999)
Gonthier, G., Abadi, M., Lévy, J.-J.: The geometry of optimal lambda reduction. In: Proc. of the 19th Conference on Principles of Programming Languages, pp. 15–26. ACM Press, New York (1992)
R̃oger Hindley, J.: Combinatory reductions and lambda reductions compared. Zeit. Math. Logik 23, 169–180 (1977)
Klop, J.W.: Combinatory Reduction Systems. PhD thesis, Rijksuniversiteit Utrecht (1980)
Lafont, Y.: Interaction nets. In: Principles of Programming Languages, pp. 95–108. ACM Press, New York (1990)
Lamping, J.: An algorithm for optimal lambda-calculus reduction. In: Proceedings of the 17th Annual ACM Symposium on Principles of Programming Languages, pp. 16–30 (1990)
Launchbury, J.: A natural semantics for lazy evaluation. In: Proc. of the 1993 conference on Principles of Programming Languages, pp. 144–154. ACM Press, New York (1993)
Lawall, J.L., Mairson, H.G.: On the global dynamics of optimal graph reduction. In: ACM International Conference on Functional Programming, pp. 188–195 (1997)
Leroy, X.: The ZINC experiment: an economical implementation of the ML language. Technical report 117, INRIA (1990)
Lévy, J.-J.: Réductions correctes et optimales dans le lambda-calcul. PhD thesis, Univ. of Paris 7, Paris (1978)
Lévy, J.-J., Maranget, L.: Explicit substitutions and programming languages. In: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.) FST TCS 1999. LNCS, vol. 1738, pp. 181–200. Springer, Heidelberg (1999)
Maraist, J., Odersky, M., Turner, D.N., Wadler, P.: Call-by-name, call-by-value, call-by-need, and the linear lambda calculus. In: Electronic Notes in Theoretical Computer Science, March 1995, pp. 41–62 (1995)
Maranget, L.: La stratégie paresseuse. PhD thesis, Univ. of Paris 7, Paris (1992)
Melliès, P.-A.: Description Abstraite des Systèmes de Réécriture. PhD thesis, Univ. of Paris 7, december (1996)
Peyton-Jones, S.L.: The implementation of Functional Programming Languages. Prentice-Hall, Englewood Cliffs (1987)
Shivers, O., Wand, M.: Bottom-up beta-substitution: uplinks and lambda-dags. Technical report, BRICS RS-04-38, DAIMI, Department of Computer Science, University of Århus, Århus, Denmark (2004)
Terese: Term Rewriting Systems. Cambridge University Press, Cambridge (2003)
Wadsworth, C.P.: Semantics and pragmatics of the lambda-calculus. PhD thesis, Oxford University (1971)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Blanc, T., Lévy, JJ., Maranget, L. (2005). Sharing in the Weak Lambda-Calculus. In: Middeldorp, A., van Oostrom, V., van Raamsdonk, F., de Vrijer, R. (eds) Processes, Terms and Cycles: Steps on the Road to Infinity. Lecture Notes in Computer Science, vol 3838. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11601548_7
Download citation
DOI: https://doi.org/10.1007/11601548_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30911-6
Online ISBN: 978-3-540-32425-6
eBook Packages: Computer ScienceComputer Science (R0)