Can Logic Programming Be Liberated from Backtracking?

by Michael Hanus

Tagungsband zum 21. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS 2021), Kiel Computer Science Series, Numer 2021/7. Department of Computer Science, Faculty of Engineering, Kiel University, pp. 40-47, 2021

Logic programming is historically tight with Prolog and its backtracking search strategy. The use of backtracking was justified by efficiency reasons when Prolog was invented and is still present, although the incompleteness of backtracking destroys the elegant connection of logic programming and the underlying Horn clause logic. Moreover, it causes difficulties to teach logic programming. In this paper we argue that this is no longer necessary if new implementation approaches are taken into account.

Preprint (PDF) BibTeX-Entry Online