Implementing Type Theory in Higher Order Constraint Logic Programming

Abstract : In this paper we are interested in high-level programming languages to implement the core components of an interactive theorem prover for a dependently typed language: the kernel — responsible for type-checking closed terms — and the elaborator — that manipulates terms with holes or, equivalently, partial proof terms. In the first part of the paper we confirm that λProlog, the language developed by Miller and Nadathur since the 80s, is extremely suitable for implementing the kernel, even when efficient techniques like reduction machines are employed. In the second part of the paper we turn our attention to the elaborator and we observe that the eager generative semantics inherited by Prolog makes it impossible to reason by induction over terms containing metavariables. We also conclude that the minimal extension to λProlog that allows to do so is the possibility to delay inductive predicates over flexible terms, turning them into (set of) constraints to be propagated according to user provided constraint propagation rules. Therefore we propose extensions to λProlog to declare and manipulate higher order constraints, and we implement the proposed extensions in the ELPI system. Our test case is the implementation of an elaborator for a type theory as a CLP extension to a kernel written in plain λProlog.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger
Contributeur : Enrico Tassi <>
Soumis le : vendredi 17 novembre 2017 - 11:31:06
Dernière modification le : jeudi 11 janvier 2018 - 16:18:58


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01410567, version 2



Ferruccio Guidi, Claudio Sacerdoti Coen, Enrico Tassi. Implementing Type Theory in Higher Order Constraint Logic Programming. 2017. 〈hal-01410567v2〉



Consultations de la notice


Téléchargements de fichiers