Plugging-in proof development environments using Locks in LF
File(s)MSCS2016.pdf (860.15 KB)
Accepted version
OA Location
Author(s)
HONSELL, F
LIQUORI, L
MAKSIMOVIĆ, P
SCAGNETTO, I
Type
Journal Article
Abstract
We present two extensions of the LF constructive type theory featuring monadic locks. A lock is a monadic type construct that captures the effect of an external call to an oracle. Such calls are the basic tool for plugging-in and gluing together, different metalanguages and proof development environments. Oracles can be invoked either to check that a constraint holds or to provide a witness. The systems are presented in the canonical style developed by the ‘CMU School.’ The first system, CLLFð «, is the canonical version of the system LLFð «, presented earlier by the authors. The second system, CLLFð «?, features the possibility of invoking the oracle to obtain also a witness satisfying a given constraint. In order to illustrate the advantages of our new frameworks, we show how to encode logical systems featuring rules that deeply constrain the shape of proofs. The locks mechanisms of CLLFð «and CLLFð «?permit to factor out naturally the complexities arising from enforcing these ‘side conditions,’ which severely obscure standard LF encodings. We discuss Girard's Elementary Affine Logic, Fitch–Prawitz set theory, call-by-value λ-calculi and functions, both total and even partial.
Date Issued
2018-10-01
Date Acceptance
2018-02-11
Citation
Mathematical Structures in Computer Science, 2018, 28 (9), pp.1578-1605
ISSN
0960-1295
Publisher
Cambridge University Press
Start Page
1578
End Page
1605
Journal / Book Title
Mathematical Structures in Computer Science
Volume
28
Issue
9
Copyright Statement
© 2018 Cambridge University Press. This paper has been accepted for publication and will appear in a revised form, subsequent to peer-review and/or editorial input by Cambridge University Press.
Subjects
Science & Technology
Technology
Computer Science, Theory & Methods
Computer Science
PI-CALCULUS
FRAMEWORK
0802 Computation Theory and Mathematics
Computation Theory & Mathematics
Publication Status
Published
Date Publish Online
2018-05-15