Syntax and Models of a non-Associative Composition of Programs and Proofs

The thesis is a contribution to the understanding of the nature, role, and mechanisms of polarisation in programming languages, proof theory and categorical models. Polarisation corresponds to the idea that we can relax the associativity of composition, as we show by relating duploids, our direct model of polarisation, to adjunctions. As a consequence, polarisation underlies many models of computation, which we further show by decomposing continuation-passing-style models of delimited control in three fundamental steps. It also explains constructiveness-related phenomena in proof theory, which we illustrate by providing a formulae-as-types interpretation for polarisation in general and for an involutive negation in particular. The cornerstone of our approach is an interactive term-based representation of proofs and programs (L calculi) which exposes the structure of polarities. It is based on the correspondence between abstract machines and sequent calculi, and it aims at synthesising various trends: the modelling of control, evaluation order and effects in programming languages, the quest for a relationship between categorical duality and continuations, and the interactive notion of construction in proof theory. We give a gentle introduction to our approach which only assumes elementary knowledge of simply-typed λ calculus and rewriting.

Data and Resources

Additional Info

Field Value
Source https://theses.hal.science/tel-00918642
Author Munch-Maccagnoni, Guillaume
Maintainer CCSD
Last Updated May 7, 2026, 19:35 (UTC)
Created May 7, 2026, 19:35 (UTC)
Identifier tel-00918642
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Preuves, Programmes et Systèmes (PPS) ; Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
creator Munch-Maccagnoni, Guillaume
date 2013-12-10T00:00:00
harvest_object_id 283c19e2-e305-4c57-89ea-bcbd06fea6b7
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-08-12T00:00:00
set_spec type:THESE