Compilation of Disjuncts

Appeared in Volume 6/1, February 1993

Keywords: disjunctions.

micha@ecrc.de
Micha Meier
3rd September 1992

Serge Lehuitouze writes:
I have never seen anything about the compilation of the disjunction ';' (and also things like '->') for the WAM. Does the WAM do anything special about this construct, or is it treated like an ordinary predicate with a definition like:

 P ;_Q :- P.
 _P; Q :- Q.

There are two basic ways to compile disjunctive constructs, one is with auxiliary procedures and the other in-line. If you have a clause:

p(X, Y) :- q, (r(X); s(Y)), t.

then the former method (used in SICStus, KCM, etc) is to transform it into:

p(X, Y) :- q, aux(X, Y), t.

aux(X, _) :- r(X).
aux(_, Y) :- s(Y).

In case there is a cut involved, one might need to pass additional information to aux/2).

The other method is done at the WAM level, the WAM code looks something like:

	allocate
	get_variable Y1, A1
	get_variable Y2, A2
	call q/0
	try_me_else L1
	put_value Y1, A1
	call r/1
	branch L2
L1:  trust_me
	put_value Y2, A1
	call s/1
L2:   deallocate
	execute t/0

This method is used by (as far as I know) Quintus and Sepia. Both methods have advantages and disadvantages. I think the latter is more efficient, because no additional environment is created for the auxiliary procedures. Also, the disjunction choice point always has an arity of zero, which means less branching. However, the main reason for compiling disjunctions is to avoid building a structure and then using the metacall.

The former method can easily be done at the Prolog level with a preprocessor, modulo cut and the like. However, the in-line expansion, especially if one wants to improve special cases like not/1, once/1 and if-then-else with a simple condition, can very quickly become difficult.

matsc@sics.se
Mats Carlsson
3rd September 1992

SICStus uses the first method.The second approach would not be readily applicable, since the SICStus emulator does not have try/retry/trust instructions.

chik@icot.or.jp
Takashi Chikayama
3rd September 1992

Serge Lehuitouze writes:
do you do anything special about this construct ...

You have to do something special to extend the scope of cut operators. Program A below has only one solution of X=1, while program B should have both X=1 and X=2.

% program A:
p(X) :- q(X), (true, !; fail).
q(1). q(2).
?- p(X).

% program B:
p(X) :- q(X), or((true, !), fail).
q(1). q(2).
or(T, _F) :- T.
or(_T, F) :- F.
?- p(X).

More complicated mechanisms might be needed in an implementation without a separate choice point stack.

tim@quintus.com
Tim Lindholm
2nd September 1992

Quintus Prolog compiles disjunction and if-then-else in line rather than calling out to a predicate, although to a first approximation it comes down to the same thing - pushing a choice point allowing you to backtrack to the second horn of the disjunction, then calling the first horn. Doing so in line has a few advantages like avoiding the cost of the call and leaving you free to customize the choice point to best suit disjunction.

However, when compiling disjunction and if-then-else you also need to worry about the scope of cuts. Takashi Chikayama gives an example above, another is the nonsensical program:

go :- ( write('first horn'), nl,
	!,
	fail
 ; write('second horn'), nl
 ).
go.

writes "first horn" and fails in Quintus Prolog, the cut cutting away the choice point for go/0 as well as the choice point for the disjunction. If you defined ;/2 as above, the cut in the first horn would only affect the meta- called goal, cutting neither the choice point for ;/2 nor go/0.

Quintus compiles general if-then-elses similarly, except that it optimizes many cases where failure of an "if" test doesn't need all the power of backtracking to recover and get to the "then". These include things like term type tests, arithmetic and term comparisons (==/2), etc. Calls to user- defined predicates are never optimized like this, as compilation doesn't know what all they are going to do (e.g. create structure, bind variables) when they are called.

Knowing how your Prolog handles disjunction and if-then-else, and whether there are cases that it optimizes, allows you to often greatly reduce the number of time- and space-expensive choice points you push.

ok@goanna.cs.rmit.oz.au
Richard A. O'Keefe
8th September 1992

There is a third possibility: when a clause contains a goal of the form (P ; Q), e.g.

H :- A, (P ; Q), B

split that goal out as a separate predicate:

T(Xs) :- P.
T(Xs) :- Q.
H :- A, T(Xs), B.

where Xs is vars([P,Q]) intersect vars([H,A,B]).

But disjunction is usually compiled specially, for two important reasons:

It would be unreasonably slow and inefficient to do otherwise.
Disjunction and if->then;else are transparent to cuts, that is, a cut inside one of them has an effect on the whole predicate, not just the disjunction or if->then;else.