Pruning in Logic Programming

Lee Naish Computer Science University of Melbourne

These slides are on the World Wide Web:

http://www.cs.mu.oz.au/˜ lee

/papers/prune/index.html

Outline

The good things about pruning The bad things about pruning The ugly things about pruning Why do we need pruning What is pruning used for Modes Better pruning operators Summary

Good things about pruning

Efficiency:

p(X, Y) :- thiscase(X), !, ... p(X1, Y1),...
p(X, Y) :- thatcase(X), ...

• On backtracking, less of the search space is considered

• Some tests (eg, thatcase) may be eliminated — if-then-ELSE

• For forward execution, the stack is smaller and more garbage can be collected

Good things about pruning (cont.)

It allows nondeterminism to be expressed Eg, merge in committed choice languages You get one solution — you don’t care which one

Bad things about pruning

Most pruning operators destroy the declarative reading of programs

q(a, a).
q(a, b).
q(b, a).
q(b, b).
p(X, Y) :- q(X, Y), !.

What is the success set/intended meaning?

{p(a, a), p(a, b), p(b, a), p(b, b)} {p(a, a), p(b, a)} {p(a, a), p(a, b)} {p(a, a)}

Bad things about pruning (cont.)

Pruning can introduce incompleteness Completeness: if an all-solutions computation terminates normally then all true instances of the query have been found Incompleteness + negation as failure leads to unsoundness There are several sound options:

• abandon pruning

• abandon negation (CC languages)

• abandon pruning inside negation (Gödel)

• develop pruning operators with (compatible) declarative semantics

Ugly things about pruning

The scope rules of cut A nuisance for unfolding, meta interpreters etc.

p(X) :- q(X).
p(X) :- r(X).
q(X) :- ... !, ...
q(X) :- ...

Best to transform into -> ; Cuts in conditionals can be a problem

Why do we need pruning

In Prolog

• Anything can be nondeterministic

• Determinism detection is undecidable

• Unless determinism is detected, space is consumed

p(X, Y) :- thiscase(X), ... p(X1, Y1),...
p(X, Y) :- thatcase(X), ...
f(X) = ... f(X1) ..., if thiscase(X)
          % otherwise
f(X) = ..., if thatcase(X)

Why do we need pruning (cont.)

a S0 b  a S1 b

    % Recognises expression (a+b)*b
s0(a.Xs) :- s0(Xs).
s0(b.Xs) :- s1(Xs).
s1(a.Xs) :- s0(Xs).
s1(b.Xs) :- s1(Xs).
s1([]).

Can we run this on a finite state machine?

Why do we need pruning (cont.)

if-then-else with a general condition is very useful for expressing algorithms Negation is very useful for expressing logic Pruning is a very efficient way of implementing negation (negation as failure) Pruning is an adequate way of implementing if-then-else

What is pruning used for

We need to understand • what pruning operators do (procedurally)

• the logic behind the different ways they are used

Cut = Once + Soft cut

There are two things cut does:

• prevent alternative solutions to calls before the cut being considered (once)

• prevent alternative clauses/disjuncts after the cut being considered (soft cut)

Soft cut + Modes = Negation

   % soft cut ($) version
p(I, ...) :- q(I, O), $, r(...).
p(I, ...) :- ...
    % equivalent logical version
p(I, ...) :- q(I, O), r(...).
p(I, ...) :- not (some [O] q(I, O)), ...

Goals before soft cut are negated in subsequent clauses and variables which are not input are quantified

Negation = Soft cut + Modes

NU-Prolog (if some Vars C then A else B)

is logically equivalent to

(some Vars (C, A) ; not (some Vars C), B)

Not is a special case of if-then-else If a variable in Vars appears in A, and C has multiple answers, soft cut must be used Variables in C which are not in Vars must be input (ground in NU-Prolog)

Enforcing Modes

if C then A else B can be implemented soundly in many different ways We can vary

• the strictness of the mode constraint

• when the mode constraint is checked

• what happens if the mode constraint isn’t satisfied

Cut − Modes = Nonsense

It is impossible to safely include cut in programs without mode information You don’t know if it will prune off parts of the search space that you need You don’t know what logic it corresponds to (what variables are quantified in the negation)

Pruning − Modes = Nonsense

The same applies to • once

• soft cut

• Gödel commit

• Parlog commit

• GHC/AKL commit

• NU-Prolog if-then-else

• functional programming

Once

There are many different uses of once

• p(I, ) — the output variables are never used (implemented as some [O] p(I,O) in NU-Prolog)

• dfid(I,O) — you want the first solution — this depends on the selection and computation rules but may be logically well defined (implemented in Trilogy)

• slowsort(I,O) — there is only one answer (possibly returned more than once)

• compile(I,O) — you want any solution (this may affect completeness if used other than at the top level)

• …

Better pruning operators

There is logic behind each occurrence of once But different occurrences correspond to different logic Using a different operator for each different logic makes programs easier to understand

Better pruning operators (cont.)

A new operator: only [O] slowsort(I,O)

What does this mean? For a query it means the same as slowsort(I,O) It is also an assertion: ∀x(slowsort(x, y_{1}) ∧ slowsort(x, y_{2}) ⇒ y_{1} = y_{2}) The meaning of a program is the clauses (or completion) plus the assertions, and the intended interpretation should be a model The additional logic can be used to make the execution more efficient, by pruning Declarative debugging could be used

Pushing pruning

If a program has a one solution operator

P :- once Q.
Q :- (R ; S), T.
T :- U, V.
R :- W.
...

pruning can be done earlier by adding more...

P :- once Q.
    % only one solution needed
Q :- once ((R ; S), T).
T :- U, V.
R :- W.
...

Pushing pruning (cont.)

and more...

P :- once Q.
    % only one solution needed
Q :- once ((R ; S), once T).
    % only one solution needed
T :- once (U, once V).
R :- W.
...

and more...

P :- once Q.
    % only one solution needed;
    % any solution to R can be
    % extended to a solution to T
Q :- once (once R, once T ; S, once T).
    % only one solution needed
T :- once (U, once V).
    % only one solution needed
R :- once W.
...

Pushing pruning (cont.)

The resulting program is a mess BUT It can be much more efficient: O(1) space instead of O(N) space It is the basis of many instances of don’t care nondeterminism (eg, committed choice merge)

Pushing pruning (cont.)

To push pruning you need

• the context of the computation (if multiple solutions are needed)

• the computation rule (generally left to right)

• additional logic (eg, relating solutions to R with solutions to T)

• modes (to make use of the additional logic)

Better pruning operators (cont.)

    % any solution to r can be
    % extended to a solution to t
q(I,O) :- (r(I,L) =-> t(L,O) ; s(I,L), t(L,O)).

The declarative meaning of the program (if O is output) is the same as

q(I,O) :- (r(I,L), t(L,O) ; s(I,L), t(L,O)).

plus the assertion

∀x∀y(r(x, y) ⇒ ∃z t(y, z))

The quantification can be made explicit by adding exists [O] to the code, or the modes could be specified

Better pruning operators (cont.)

In a multiple solution context for Q no pruning is done In a single solution context for Q, T and R are called in single solution contexts Pruning can be done in a similar way to

(R -> T ; S, T) but better!

The disjunction can be pruned as soon as it is known that W will succeed Eg, as soon as it is known X will succeed if W is defined as follows

W :- X =-> Y.

Summary

We would like • Declarative semantics and soundness • Completeness with normal termination • Expressiveness

• Space efficiency

• Time efficiency

Summary (cont.)

Some pruning operators are used in many different ways Declarative semantics can be given for pruning operators which are used in one way Modes are essential for pruning Mode checks can vary according to strictness, when they are done, and the result if they fail