Write a Blog >>
Wed 20 Jan 2016 11:45 - 12:10 at Grand Bay South - Track 2: Types and Foundations Chair(s): Robert Atkey

We consider the Curry-Howard-Lambek correspondence for effectful computation and resource management, specifically proposing polarised calculi together with enriched adjunction models as the starting point for a comprehensive semantic theory relating logical systems, typed calculi, and categorical models in this context.

Our thesis is that the combination of effects and resources should be considered orthogonally. Model theoretically, this leads to an understanding of our categorical models from two complementary perspectives: (i) as a linearisation of CBPV (Call-by-Push-Value) adjunction models, and (ii) as an extension of linear/non-linear adjunction models with an adjoint resolution of computational effects. When the linear structure is cartesian and the resource structure is trivial we recover Levy’s notion of CBPV adjunction, while when the effect structure is trivial we have Benton’s linear/non-linear adjunction models. Further instances of our model theory include the dialogue categories with a resource modality of Melliès and Tabareau, and the [E]EC ([Enriched] Effect Calculus) models of Egger, Møgelberg and Simpson. Our development substantiates the approach by providing a lifting theorem of linear models into cartesian ones.

To each of our categorical models we systematically associate a typed term calculus, each of which corresponds to a variant of the sequent calculi LJ (Intuitionistic Logic) or ILL (Intuitionistic Linear Logic). The adjoint resolution of effects corresponds to polarisation whereby, syntactically, types locally determine a strict or lazy evaluation order and, semantically, the associativity of cuts is relaxed. In particular, our results show that polarisation provides a computational interpretation of CBPV in direct style. Further, we characterise depolarised models: those where the cut is associative, and where the evaluation order is unimportant. We explain possible advantages of this style of calculi for the operational semantics of effects.

Wed 20 Jan

POPL-2016-papers
10:30 - 12:10: Research Papers - Track 2: Types and Foundations at Grand Bay South
Chair(s): Robert AtkeyUniversity of Strathclyde
POPL-2016-papers10:30 - 10:55
Talk
Matt BrownUCLA, Jens PalsbergUniversity of California, Los Angeles
Media Attached File Attached
POPL-2016-papers10:55 - 11:20
Talk
Thorsten AltenkirchUniversity of Nottingham, Ambrus KaposiUniversity of Nottingham
Media Attached File Attached
POPL-2016-papers11:20 - 11:45
Talk
Yufei CaiUniversity of Tübingen, Germany, Paolo G. GiarrussoUniversity of Tübingen, Germany, Klaus OstermannUniversity of Tübingen, Germany
Media Attached
POPL-2016-papers11:45 - 12:10
Talk
Pierre-Louis CurienUniv. Paris Diderot and INRIA Paris-Rocquencourt, Marcelo FioreComputer Laboratory, University of Cambridge, Guillaume Munch-MaccagnoniComputer Laboratory, University of Cambridge