Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-08T02:53:33.631Z Has data issue: false hasContentIssue false
  • English
  • Français

Fibrations with indeterminates: contextual and functional completeness for polymorphic lambda calculi

Published online by Cambridge University Press:  04 March 2009

Claudio Hermida  and
Bart Jacobs
Get access Rights & Permissions [Opens in a new window]

Abstract

Lambek used categories with indeterminates to capture explicit variables in simply typed λ-calculus. He observed that such categories with indeterminates can be described as Kleisli categories for suitable comonads. They account for ‘functional completeness’ for Cartesian (closed) categories.

Here we refine this analysis, by distinguishing ‘contextual’ and ‘functional’ completeness, and extend it to polymorphic λ-calculi. Since the latter are described as certain fibrations, we are lead to consider indeterminates, not only for ordinary categories, but also for fibred categories. Following a 2-categorical generalisation of Lambek's approach, such fibrations with indeterminates are presented as 'simple slices' in suitable 2-categories of fibrations; more precisely, as Kleisli objects. It allows us to establish contextual and functional completeness results for some polymorphic calculi.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 5 , Issue 4 , December 1995 , pp. 501 - 531
Copyright
Copyright © Cambridge University Press 1995

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.)

References

Barendregt, H. (1984) The Lambda Calculus: its syntax and semantics, revised edition, North-Holland.Google Scholar
Burstall, R. and McKinna, J. (1992) Deliverables: a categorical approach to program development in type theory, Technical Report ECS-LFCS-92–242, Department of Computer Science, Edinburgh University.Google Scholar
Carboni, A., Kelly, G. M. and Wood, R. (1990) A 2-categorical approach to change of base and geometric morphisms, Research Report 90–1, Department of Pure Mathematics, University of Sidney.Google Scholar
Fourman, M. and Phoa, W. (1992) A proposed categorical semantics for Pure ML. In: Proceedings ICALP 92.Google Scholar
Hasegawa, M. (1994) Decomposing typed lambda calculus into a couple of categorical programming languages, Draft, Department of Computer Science, Edinburgh University.Google Scholar
Hermida, C. (1993) Fibrations, logical predicates and indeterminates, PhD. Thesis, University of Edinburgh. (Technical Report ECS-LFCS-93–277; also available as Aarhus University DAIMI Technical Report PB-462.)CrossRefGoogle Scholar
Hermida, C. and Jacobs, B. (1994) An algebraic view of structural induction. In: CSL'94. (Extended version in preparation)Google Scholar
Jacobs, B. (1991) Categorical Type Theory, PhD. Thesis, University of Nijmgen.Google Scholar
Jacobs, B. (1993a) Comprehension categories and the semantics of type dependency. Theoretical Computer Science.CrossRefGoogle Scholar
Jacobs, B. (1993b) Parameters and parametrization in specification, Technical Report 786, Department of Mathematics, University of Utrecht.Google Scholar
Jacobs, B. and Streicher, T. (1993) A categorical view of equality in type theory, Technical Report 820, Department of Mathematics, University of Utrecht.Google Scholar
Kelly, G. M. (1989) Elementary observations on 2-categorical limits. Bulletin Australian Mathematical Society 39 301–317.CrossRefGoogle Scholar
Kelly, G. M. and Street, R. (1974) Review of the elements of 2-categories. In: Dold, A. and Eckmann, B. (eds.) Proceedings Sydney Category Theory Seminar 1972/73. Springer-Verlag Lecture Notes in Mathematics 420 75–103.CrossRefGoogle Scholar
Lambek, J. and Scott, P. J. (1986) Introduction to higher-order categorical logic, Studies in Advanced Mathematics 7, Cambridge University Press.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Springer-Verlag.CrossRefGoogle Scholar
Makkai, M. (1993) The fibrational formulation of intuitionistic predicate logic I: Completeness according to Gödel, Kripke and Läuchi, Part I. Notre Dame Journal of Symbolic Logic 34 (3) 334–377.Google Scholar
Street, R. (1972) The formal theory of monads. Journal of Pure and Applied Algebra 2 149–168.CrossRefGoogle Scholar