Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T17:28:15.707Z Has data issue: false hasContentIssue false
  • English
  • Français

A categorical understanding of environment machines

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Andrea Asperti
Andrea Asperti
Affiliation:
INRIA, Rocquencourt, 78153 Le Chesnay, France ([email protected])
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.

In the last two decades, category theory has become one of the main tools for the denotational investigation of programming languages. Taking advantage of the algebraic nature of the categorical semantics, and of the rewriting systems it suggests, it is possible to use these denotational descriptions as a base for research into more operational aspects of programming languages.

This approach proves to be particularly interesting in the study and the definition of environment machines for functional languages. The reason is that category theory offers a simple and uniform language for handling terms and environments (substitutions), and for studying their interaction (through application).

Several examples of known machines are discussed, among which the Categorical Abstract Machine of Cousineau et al. (1987) and Krivine's machine. Moreover, as an example of the power and fruitfulness of this approach, we define two original categorical machines. The first one is a variant of the CAM implementing a λ-calculus with both call-by-value and call-by-name as parameters passing modes. The second one is a variant of Krivine's machine performing complete reduction of λ-terms.

Type
Articles
Information
Journal of Functional Programming , Volume 2 , Issue 1 , January 1992 , pp. 23 - 59
Copyright
Copyright © Cambridge University Press 1992

References

Abramsky, S. 1989. The lazy λ-calculus. In Turner, D., Ed., Declarative Programming, Addison-Wesley.Google Scholar
Abadi, M., Cardelli, L., Curien, P. L. and Lévy, J. J. 1990. Explicit Substitutions. In Proc. of the 17th Annual Symposium on Principles of Programming Languages, (POPL90). San Francisco. (An extended version is available as Rapport de Recherche INRIA-Rocquencourt no 1176).Google Scholar
Asperti, A. and Longo, G. 1991. Categories, Types and Structures: An introduction to category theory for the working computer scientist. MIT Press.Google Scholar
Asperti, A. 1989. Categorical Topics in Computer Science. PhD thesis, Università degli Studi di Pisa, Dipartimento di Informatica.Google Scholar
Asperti, A. 1990. Integrating strict and lazy evaluation: the λsl-calculus. In Proc. of the 2nd International Workshop on Programming Language Implementation and Logic Programming, PLILP'90, Linköpink, Sweden, Volume 456 of Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Balsters, H. 1986. Lambda Calculus extended with Segments. PhD thesis, University of Eindhoven.Google Scholar
Cardelli, L. 1986. The Amber Machine. In Cousineau, G., Curien, P. L. and Robinet, B., Eds., Combinators and Functional Programming Languages. Volume 242 of Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Cousineau, G., Curien, P. L. and Mauny, M. 1987. The Categorical Abstract Machine. Sci. of Computer Programming, 8.CrossRefGoogle Scholar
Cousineau, G. and Huet, G. 1986. The CAML Primer. Rapport de Recherche Project Formel, INRIA-Rocquencourt&ENS.Google Scholar
Curien, P. L. and Obtulowicz, A. 1989. Partiality, Cartesian Closedness and Toposes. Inf. and Computation, 80 (1).Google Scholar
Crègut, P. 1990. An abstract machine for the normalization of λ-terms. In Proc. of the ACM Conf. on Lisp and Functional Programming, Nice, France.Google Scholar
Curien, P. L. 1986. Categorical Combinators, Sequential Algorithms and Functional Programming. Pitman.Google Scholar
Curien, P. L. 1988. The λρ-calculus: an Abstract Framework for Environment Machines. Rapport de Recherche du LIENS 88-10.Google Scholar
De Bruijn, N. G. 1972. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation. Indag. Math. 34.Google Scholar
Field, J. 1990. On laziness and Optimality in Lambda Interpreters: Tools for Specification and Analysis. In Proc. of the 17th Annual Symposium on Principles of Programming Languages (POPL90). San Francisco.Google Scholar
Fairbairn, J. and Wray, S. 1987. Tim: a simple, lazy, abstract machine to execute supercombinators. Volume 274 of Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Girard, J. Y.Linear Logic. Theor. Computer Sci., 50.Google Scholar
Hardin, T. and Laville, A. 1986. Proof of Termination of the Rewriting System SUBST on CCL. Theor. Computer Sci., 46.CrossRefGoogle Scholar
Hardin, T. and Lévy, J. J. 1990. A Confluent Calculus of Substitutions. Draft.Google Scholar
Hardin, T. 1987. Résultats de Confluence pour les Règies Fortes de la Logique Combinatoire Catégorique et Liens avec les Lambda-Calculs. Thèse de Doctorat, Université Paris VII.Google Scholar
Hardin, T. 1989. Confluence results for the Pure Strong Categorical Combinatory Logic CCL: λ-calculi as Subsystems of CCL. Theor. Computer Sci., 65.CrossRefGoogle Scholar
Hayashi, S. 1985. Adjunctions of Semifunctors: Categorical Structures in Nonextensional Lambda Calculus. Theor. Computer Sci., 41.CrossRefGoogle Scholar
Kennaway, J. 1984. An outline of some results of Staples on optimal reduction orders in Replacement Systems. Internal Report CSA/19/84. University of East Anglia.Google Scholar
Lévy, J. J. 1978. Réductions correctes et optimales dans le lambda-calcul. Thèse de doctorat. Université Paris VII.Google Scholar
Mauny, M. 1985. Compilation des langages fonctionnels dans le combinateurs catégoriques; application au langage ML. Thèse de Troisième Cycle, Université Paris VII.Google Scholar
Martini, S. 1988. Modelli non estensionali del polimorfismo in programmazione funzionale. PhD thesis, Università degli Studi di Pisa, Dipartimento di Infomatica.Google Scholar
Plotkin, G. 1975. Call-by-name, Call-by-value and the λ-calculus. Theor. Computer Sci., 1.CrossRefGoogle Scholar
Revesz, G. 1984. An extension of Lambda Calculus for Functional programming. J. Logic Computation, 3.Google Scholar
Robinson, E. and Rosolini, G. 1988. Categories of Partial maps. infor. and computation, 79 (2).Google Scholar
Seely, R. A. G. 1987. Linear Logic, *-autonomous categories and cofree coalgebras. In Conf. in Category Theory, Computer Science, and Logic, Boulder, CO (AMS notes).Google Scholar
Sleep, M. 1985. Issues for implementing lambda languages. Notes for Ustica Workshop.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.