A Predicate Construct for Declarative Programming in Imperative Languages

Imperative and object-oriented programming languages are among the most common languages for general-purpose programming. These languages work well for handling many common tasks necessary for most applications. However, there are still many hard problems that remain difficult to implement directly in imperative languages. Declarative languages have worked well for solving many of these problems by providing a syntax that allows the user to focus on modeling the problem rather than on designing an algorithm. Logic programming languages, like Prolog, have seen success in constraint satisfaction problems, logical databases, and various NP-Hard problems. Unfortunately, these languages have not seen the same success in general-purpose programming, and most of the problems they solve do not exist in isolation. Furthermore, many imperative programmers are still unfamiliar with and unaware of logic programming. In this work, we aim to integrate a logical predicate, borrowed from logic programming, into an imperative language to facilitate a model-based approach to programming. Rather than attempting to embed Prolog directly into the language, we provide a logic for reasoning over imperative expressions using the common Boolean operators familiar to imperative programmers. While logic programming relies on unification, our predicate relies on variable assignment which is standard in imperative languages. We have implemented the predicate into the syntax of the Python programming language along with a solver built into the runtime for solving queries on the predicate. We demonstrate the use of the construct through solving commonly-known problems, such as graph coloring and the N-Queens problem. To evaluate the viability of our predicate, we compare the performance results of our predicate against current implementations of Prolog. By bringing this predicate construct to imperative languages, it is our hope that we can help to bridge the gap between imperative and logic programming as well as provide an approach to logic programming that is more intuitive for imperative programmers.