Intersection and Union Types Meet Quantitative Semantics, Classically
Inspired by the fine-grained nature of linear logic, we lift Curien and Herbelin’s syntactic duality of computation in the classical sequent calculus to a resource-aware quantitative denotational semantics that captures the duality of intersection and union types.
Our starting point is the translation of classical logic into linear logic due to Danos, Joinet, and Schellinx, which provides the framework for developing idempotent and non-idempotent intersection/union type systems for the classical sequent calculus, in which the ! modality is interpreted by finite intersection types and ? by finite union types. Our idempotent type system gives a qualitative characterization of normalization, while the non-idempotent system provides a quantitative one, yielding exact measures of evaluation lengths.
Finally, we develop a coarse-grained relational model for the untyped classical sequent calculus and show that our non-idempotent system yields a finer-grained, more expressive syntactic account of this model.
Notably, thanks to the symmetry of all our constructions, the entire technical development dualizes uniformly from call-by-name to call-by-value, at no additional cost.