Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-26T10:02:33.174Z Has data issue: false hasContentIssue false
  • English
  • Français

Categorical models of the differential λ-calculus

Published online by Cambridge University Press:  06 June 2019

Robin Cockett  and
Jonathan Gallagher
Robin Cockett*
Affiliation:
Department of Computer Science, University of Calgary, Calgary, Canada
Jonathan Gallagher
Affiliation:
Department of Computer Science, University of Calgary, Calgary, Canada
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper shows how the Scott–Koymans theorem for the untyped λ-calculus can be extended to the differential λ-calculus. The main result is that every model of the untyped differential λ-calculus may be viewed as a differential reflexive object in a Cartesian-closed differential category. This extension of the Scott–Koymans theorem depends critically on unraveling the somewhat subtle issue of which idempotents can be split so that differential structure lifts to the idempotent splitting.

The paper uses (total) Turing categories with “canonical codes” as the basic categorical semantics for the λ-calculus. It develops the main result in a modular fashion by showing how to add left-additive structure to a Turing category, and then – on top of that – differential structure. For both levels of structure, it is necessary to identify how “canonical codes” must behave with respect to the added structure and, furthermore, how “universal objects” must behave. The latter is closely tied to the question – which is the crux of the paper – of which idempotents can be split while preserving the differential structure of the setting.

This paper is the full version of a conference paper and includes the proofs which were omitted from that version due to page-length restrictions.

Keywords

λ calculusdifferential λ calculusdifferential categories
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 29 , Issue 10 , November 2019 , pp. 1513 - 1555
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

This work was partially supported by National Science and Engineering Research Council (NSERC) of Canada.

References

Birkedal, L. (1999). Developing Theories of Types via Computability and Realizability. Phd. thesis, Carnegie Mellon University.Google Scholar
Blute, R., Cockett, J. and Seely, R. (2006). Differential categories. Mathematical Structures in Computer Science 16 1049–1083.CrossRefGoogle Scholar
Blute, R., Cockett, J. and Seely, R. (2009). Cartesian differential categories. Theory and Application of Categories 22 622–672.Google Scholar
Blute, R., Cockett, J. and Seely, R. (2015). Cartesian differential storage categories. Theory and Application of Categories 30 620–686.Google Scholar
Boudol, G. (1993). The λ-calculus with multiplicities. In: Proceedings of the 4th International Conference on Concurrency Theory, Lecture Notes in Computer Science, vol 715. Springer, Berlin, Heidelberg. 1–6.Google Scholar
Boudol, G., Curien, P. and Lavatelli, C. (1999). A semantics for λ-calculi with resource. Mathematical Structures in Computer Science 9 437–482.CrossRefGoogle Scholar
Boudol, G. and Laneve, C. (1995). λ-Calculus, Multiplicities, and the π-Calculus. Technical report RR-2581, Institut National de Recherche en Informatique et en Automatique.Google Scholar
Bucciarelli, A., Ehrhard, T. and Manzonetto, G. (2010) Categorical models for simply typed resource calculi. Electronic Notes in Theoretical Computer Science 265 213–230.CrossRefGoogle Scholar
Cockett, J. and Gallagher, J. (2016). Categorical models of the λ-calculus revisted. Electronic Notes in Theoretical Computer Science 325 63–83.CrossRefGoogle Scholar
Cockett, J. and Hofstra, P. (2008). Introduction to Turing categories. Annals of Pure and Applied Logic 156 183–209.CrossRefGoogle Scholar
Dezani-Ciancaglini, M. (1996). Logical Semantics for Concurrent λ-Calculus. Phd thesis, Katholieke Universiteit Nijmegen.Google Scholar
Ehrhard, T. (2002). On Köthe sequence spaces and linear logic. Mathematical Structures in Computer Science 12 579–623.CrossRefGoogle Scholar
Ehrhard, T. (2005). Finiteness spaces. Mathematical Structures in Computer Science 15 615–646.CrossRefGoogle Scholar
Ehrhard, T. and Regnier, L. (2003). The differential λ-calculus. Theoretical Computer Science 309 1–41.CrossRefGoogle Scholar
Faure, G. and Miguel, A. (2009). A Categorical Semantics for the Parallel λ-Calculus. Technical report RR-7063, Institut National de Recherche en Informatique et en Automatique.Google Scholar
Fiore, M. (2007). Differential structure in models of multiplicative biadditive intuitionistic linear logic. In: Typed Lambda Calculi and Applications, Lecture Notes in Computer Science, vol 4583. Springer, Berlin, Heidelberg. 163–177.CrossRefGoogle Scholar
Gallagher, J. (2018). The Differential λ-Calculus: Syntax and Semantics for Differential Geometry. Phd thesis, University of Calgary.Google Scholar
Hindley, R. and Longo, G. (1980). Lambda-calculus models and extensionality. Zeitschrift fur Mathematische Legik 26 289–310.Google Scholar
Koymans, C. (1982). Models of the λ-calculus. Information and Control 52 306–332.CrossRefGoogle Scholar
Lambek, J. and Scott, P. (1986). An Introduction to Higher Order Categorical Logic, Cambridge University Press.Google Scholar
Longo, G. and Moggi, E. (1990). A category theoretic characterization of functional completeness. Theoretical Computer Science 70 193–211.CrossRefGoogle Scholar
Manzonetto, G. (2012). What is a categorical model of the differential and the resource λ calculi? Mathematical Structures in Computer Science 22 451–520.CrossRefGoogle Scholar
Scott, D. (1980). Relating theories of the λ-calculus. In: Curry, H.B. (ed.) Essays on Combinatory Logic, Lambda Calculus, and Formalism, Academic Press. 403–450.Google Scholar
Vaux, L. (2009). The algebraic λ-calculus. Mathematical Structures in Computer Science 19 1029–1059.CrossRefGoogle Scholar