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.
Lee