the unadorned typed lambda calculus correspond to the closed cartesian categories, but if we add in dependent or parametric types how are they then characterised?
2 Answers
Dependent type theory, i.e., $\lambda$-calculus with dependent products and dependent sums corresponds to locally cartesian closed categories, which was written up by R. Seely in "Locally cartesian closed categories and type theory", Math. Proc. Phil. Comb. Soc, (1984), 95, 33.
If by "parametric types" you mean the kind of polymorphism that is present in ML, then one possible semantics is that of relationally parametric models. Probably the most influental in the development of this idea was John Reynolds, see for example his "Types, abstraction and parametric polymorphism" from 1983.
-
$\begingroup$ I was thinking of what wikipedia calls the polymorphic lambda calculus or system F. As it is a form of 2nd-order logic, would this mean it would be modelled by some kind of bicategory? $\endgroup$ Sep 22, 2012 at 22:18
-
2$\begingroup$ You can't run analogies like that. The prefix "bi" in bicategories has nothing to do with "second" in "second order arithmetic. System F is quite a bit trickier to get right. See for example Paul Taylor's "Semantics of System F" at paultaylor.eu/stable/semsf.pdf. $\endgroup$ Sep 22, 2012 at 22:53
-
$\begingroup$ @Bauer: It was a guess, and a bad guess at that :), thanks for the reference. $\endgroup$ Sep 23, 2012 at 15:59
The internal language of a locally Cartesian closed category is a dependent type theory. A category $\mathcal C$ is locally Cartesian closed, if all of its slices $\mathcal C/X$ are Cartesian closed. An arrow $f:X\to Y$ is both interpreted as a variable substitution and as a family of types indexed over $Y$ in the type theory.