Gluing together Proof Environments: Canonical extensions of LF Type Theories featuring Locks

Furio Honsell
(University of Udine, Italy)
Luigi Liquori
(Inria Sophia Antipolis Méditerranée, France)
Petar Maksimović
(Inria Rennes Bretagne Atlantique, France)
Ivan Scagnetto
(University of Udine, Italy)

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 gluing together diverse Type Theories and proof development environments. The oracle can be invoked either to check that a constraint holds or to provide a suitable witness. The systems are presented in the canonical style developed by the CMU School. The first system, CLLFP, is the canonical version of the system LLFP, presented earlier by the authors. The second system, CLLFP?, features the possibility of invoking the oracle to obtain a witness satisfying a given constraint. We discuss encodings of Fitch-Prawitz Set theory, call-by-value lambda-calculi, and systems of Light Linear Logic. Finally, we show how to use Fitch-Prawitz Set Theory to define a type system that types precisely the strongly normalizing terms.

In Iliano Cervesato and Kaustuv Chaudhuri: Proceedings Tenth International Workshop on Logical Frameworks and Meta Languages: Theory and Practice (LFMTP 2015), Berlin, Germany, 1 August 2015, Electronic Proceedings in Theoretical Computer Science 185, pp. 3–17.
Published: 27th July 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.185.1 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org