A cornerstone of theoretical computer science is the Curry-Howard correspondence where formulas are types, proofs are programs, and proof normalization is computation. In this framework we introduce the atomic λμ-calculus, an interpretation of a classical deep inference proof system. It is based on two extensions of the λ-calculus, the λμ-calculus and the atomic λ-calculus. The former interprets classical logic, featuring continuation-like constructs, while the latter interprets intuitionistic deep inference, featuring explicit sharing operators. The main property of the atomic λ-calculus is reduction on individual constructors, derived from atomicity in deep inference. We thus work on open deduction, a deep inference formalism, allowing composition with connectives and with derivations, and using the medial rule to obtain atomicity. One challenge is to find a suitable formulation for deriving a computational interpretation of classical natural deduction. A second design challenge leads us to work on a variant of the λμ-calculus, the ΛμS-calculus, adding streams and dropping names. We show that our calculus has preservation of strong normalization (PSN), confluence, fully-lazy sharing, and subject reduction in the typed case. There are two challenges with PSN. First, we need to show that sharing reductions strongly normalize, underlining that only β, μ-reductions create divergence. Our proof is new and follows a graphical approach to terms close to the idea of sharing. Second, infinite reductions of the atomic calculus can appear in weakenings, creating infinite atomic paths corresponding to finite ΛμS-paths. Our solution is to separate the proof into two parts, isolating the problem of sharing from that of weakening. We first translate into anintermediate weakening calculus, which unfolds shared terms while keeping weakened ones, and preserves infinite reductions. We then design a reduction strategy preventing infinite paths from falling into weakenings.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:761031 |
| Date | January 2018 |
| Creators | He, Fanny |
| Contributors | Heijltjes, Willem ; McCusker, Guy |
| Publisher | University of Bath |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0023 seconds