Pruning in logic programming

This material was originally produced for an advanced tutorial at the International Conference on Logic Programming in Japan, 13-16 June, 1995.

Pruning in logic programming

Lee Naish

The logic programming community has a love-hate relationship with operators for pruning the search space of logic programs such as cut, commit, once, conditionals and variations on these. Pruning operators typically are not declarative, result in incompleteness and/or unsoundness, decrease readability and flexibility of code and make program analysis and transformation more difficult. Despite this, nearly all non-trivial Prolog programs contain cuts, nearly all more recent logic programming languages have similar pruning operators and many languages insist on pruning operators in every clause. In practice, logic programming is less logical than functional programming.

Why it this so? Do we really need pruning operators? Can we have sufficiently powerful pruning operators which do not destroy the declarative semantics of programs? How are pruning operators related to logic, modes, functions and lazy evaluation? This tutorial attempts to answer some of these questions.