The duality of computation under focus - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

The duality of computation under focus

Résumé

We review the close relationship between abstract machines for (call-by-name or call-by-value) lambda-calculi (extended with Felleisen's C) and sequent calculus, reintroducing on the way Curien-Herbelin's syntactic kit expressing the duality of computation. We use this kit to provide a term language for a presentation of LK (with conjunction, disjunction, and negation), and to transcribe cut elimination as (non confluent) rewriting. A key slogan here, which may appear here in print for the first time, is that commutative cut elimination rules are explicit substitution propagation rules. We then describe the focalised proof search discipline (in the classical setting), and narrow down the language and the rewriting rules to a confluent calculus (a variant of the second author's focalising system L). We then define a game of patterns and counterpatterns, leading us to a fully focalised finitary syntax for a synthetic presentation of classical logic, that provides a quotient on (focalised) proofs, abstracting out the order of decomposition of negative connectives.
Fichier principal
Vignette du fichier
TCS-2010.pdf (260.27 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00491236 , version 1 (10-06-2010)
inria-00491236 , version 2 (06-08-2014)

Identifiants

  • HAL Id : inria-00491236 , version 1
  • ARXIV : 1006.2283

Citer

Pierre-Louis Curien, Guillaume Munch-Maccagnoni. The duality of computation under focus. IFIP International Conference on Theoretical Computer Science, Sep 2010, Brisbane, Australia. ⟨inria-00491236v1⟩

Collections

PPS
606 Consultations
222 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More