A Proof-Theoretic Foundation of Abortive Continuations

Zena Ariola (1) , Hugo Herbelin (2) , Amr Sabry (3)

1 Department of Computer and Information Science
2 LOGICAL - Logic and computing
3 Computer Science Department

We give an analysis of various classical axioms and characterize a notion of minimal classical logic that enforces Peirce's law without enforcing Ex Falso Quodlibet. We show that a "natural" implementation of this logic is Parigot's classical natural deduction. We then move on to the computational side and emphasize that Parigot's lambda-mu corresponds to minimal classical logic. A continuation constant must be added to lambda-mu to get full classical logic. The extended calculus is isomorphic to a syntactical restriction of Felleisen's theory of control that offers a more expressive reduction semantics. This isomorphic calculus is in correspondence with a refined version of Prawitz's natural deduction.

Mots clés: callcc; minimal logic; intuitionistic logic; classical logic

Domaines: Logique en informatique [cs.LO]; Langage de programmation [cs.PL]

Zena Ariola, Hugo Herbelin, Amr Sabry. A Proof-Theoretic Foundation of Abortive Continuations. Higher-Order and Symbolic Computation, 2007, 20 (4), ⟨10.1007/s10990-007-9007-z⟩. ⟨hal-00697242⟩