A Higher-order Extension Of Prolog With Polymorphic Type Inference

Abstract

Since the design of Prolog, logic programming has been one of the most prominent programming paradigms. Logic programming has traditionally been first-order. However, there have been some attempts to extend it with higher-order features.A recent work by Charalambidis et al. proposes an innovative alternative to the previous attempts. Its authors define a framework, H, with a static typing discipline and an extensional semantics. Unlike previous extensional higher-order frameworks, their framework allows for uninstantiated higher-order variables. They also provide a prototype implementation, H.In this thesis, we build on this work of Charalambidis et al. to overcome two drawbacks:- H is currently incompatible with Prolog, the de-facto standard in logic programming. More specifically, simple Prolog programs which theoretically belong in the first-order subset of H are not accepted by H.- H supports no polymorphic predicates.To overcome these drawbacks, we redesign H, aiming at an implementation that could handle a higher-order proper superset of ordinary Prolog, and extend it with a polymorphic type inference system. The new framework is named polyH. Then, we propose a surface language over our framework, polyH, which is designed to be a higher-order extension of Prolog, and of which we provide a prototype implementation.