Fibrations with indeterminates: contextual and functional completeness for polymorphic lambda calculi
Authors:
- Claudio HermidaCHClaudio Hermida
- Bart JacobsBJBart Jacobs
- 1 September 1995
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 5 (4) , 501-531
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.Keywords
This publication has 9 references indexed in Scilit:
- An algebraic view of structural induction1995
- Fibrations, Logical Predicates and IndeterminatesDAIMI Report Series, 1993
- The fibrational formulation of intuitionistic predicate logic ${\rm I}$: completeness according to Gödel, Kripke, and Läuchli. I.Notre Dame Journal of Formal Logic, 1993
- Deliverables: a categorical approach to program development in type theory1993
- Comprehension categories and the semantics of type dependencyTheoretical Computer Science, 1993
- Elementary observations on 2-categorical limitsBulletin of the Australian Mathematical Society, 1989
- Review of the elements of 2-categories1974
- The formal theory of monadsJournal of Pure and Applied Algebra, 1972
- Categories for the Working Mathematician1971