LF+ in Coq for "fast and loose" reasoning

Abstract

We develop the metatheory and the implementation of LF+, and discuss several applications. LF+ capitalizes on research work, carried out by the authors over more than a decade, on Logical Frameworks. It builds on various conservative extensions of LF, which feature "lock"-type constructors, and on the new perspectives offered by its novel "shallow" implementation in Coq. The L^P(N:sigma)[.] constructor, and its binding variant L^P(?x:sigma)[.], capture monadically the concept of inhabitability up-to. They were originally introduced for factoring-out, postponing, or delegating to external tools the verification of time-consuming judgments, which are "morally" proof-irrelevant, thus allowing for integrating different sources of epistemic evidence in a unique Logical Framework. Experimenting with "locks" has shown that they are also a very flexible tool for expressing in Type Theory several diverse cognitive attitudes and mental strategies used in ordinary reasoning. These range from the emerging paradigm of "fast and loose reasoning", which trades off efficiency for correctness, as in naive Set Theory, or in computer architecture and distributed systems, when branch prediction and optimistic concurrency control are implemented. Lock-types naturally express also Typical Ambiguity provisos, "squash"' types, and many forms of "reasoning-up-to".

Keywords

• type theory
• logical frameworks
• computer aided formal reasoning