TOWARDS BANISHING THE CUT FROM PROLOG.

The author considers the use of the 'cut' language feature in logic programming to provide greater efficiency by returning some control to the user. He argues that it is not necessary to resort to such impure features for efficiency. This point is illustrated by considering how most of the common uses of cut can be eliminated from Prolog source programs, relying on static analysis to generate them at compile time. Three common situations where the cut is used are considered. Static analysis techniques are given to detect such situations, and applicable program transformations are described. The author also proposes new language constructs, 'firstof' and 'oneof,' for situations involving 'don't care' nondeterminism. These constructs have better declarative readings than the cut and extend better to parallel evaluation strategies.