50 years of Prolog: Becoming More Declarative - David S. Warren

Prolog was invented by A. Colmerauer for processing natural languages, and formalized by R. Kowalksi as SLD resolution on Definite Horn Clauses in 1972.

It was touted as the “original” declarative language: Just “declare” your knowledge as Horn clauses in FOL to describe relations, and Prolog inference will automatically answer queries to those relations.

But, it’s not always (often?) so easy. In general, there are problems with:
loops (incompleteness),
performance,
negative knowledge,
weak numeric inferencing,
etc.
Each problem detracts from Prolog’s declarativity; they must be addressed by the user using more procedural thinking, turning the “declarer” into a “programmer.” But over the 50 years, each of these issues have been addressed (not “solved”).

In this talk I will focus on how Prolog has been extended with “tabling” to address the issue of incompleteness (looping), how that leads to interest in a specialization of the Prolog language to the language of Datalog, how Datalog generalizes SQL view definitions with inductive definitions. I’ll show some applications of Datalog. I’ll also describe how the improved completeness provided by tabling contributes to a better understanding and implementation of negation.

Keywords: Keywords: Prolog, Horn clauses, incompleteness, looping, tabling, negation