FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Proof-relevant Horn Clauses for Dependent Type Inference and Term Synthesis

Authors: Frantisek Farka, Ekaterina Komendantskaya and Kevin Hammond

Paper Information

Title:Proof-relevant Horn Clauses for Dependent Type Inference and Term Synthesis
Authors:Frantisek Farka, Ekaterina Komendantskaya and Kevin Hammond
Proceedings:ICLP Proceedings of ICLP 2018
Editors: Paul Tarau and Alessandro Dal Palu'
Keywords:Proof-relevant logic, Horn clauses, Dependent types, type inference
Abstract:

ABSTRACT. First-order resolution has been used for type inference for many years, including in Hindley-Milner type inference, type-classes, and constrained data types, to name but a few. Dependent types are a new trend in functional languages. In this paper, we show that proof-relevant first-order resolution can play an important role in automating type inference and term synthesis for dependently typed languages. We propose a calculus that translates type inference and term synthesis problems in a dependently typed language to a logic program and a goal in the proof-relevant first-order Horn clause logic. The computed answer substitution and proof term then provide a solution to the given type inference and term synthesis problem. We prove the decidability and soundness of our method.

Pages:18
Talk:Jul 14 14:00 (Session 96D: Foundations II)
Paper: