🚀 go-pugleaf

   I have some knowledge (only "theoretic", though) about the WAM, but I have
   never seen anything about the compilation of the disjunction ';' (and
   also things like '->').

   do you do anything special about this construct, or do you just
   consider it as an ordinary predicate with a definition like:
   P ;_Q :- P.
   _P; Q :- Q.

SICStus Prolog does nothing special, and considers it as an ordinary
predicate as you describe.
--
Mats Carlsson
SICS, PO Box 1263, S-164 28  KISTA, Sweden    Internet: matsc@sics.se
Tel: +46 8 7521543     Ttx: 812 6154 7010 SICS     Fax: +46 8 7517230

In article <1992Sep1.160505.6828@irisa.fr>, serge@irisa.fr (Serge Lehuitouze) writes:
> I have some knowledge (only "theoretic", though) about the WAM, but I have
> never seen anything about the compilation of the disjunction ';' (and
> also things like '->').
> 
> You, WAM gurus, do you do anything special about this construct, or do you just
> consider it as an ordinary predicate with a definition like:
> P ;_Q :- P.
> _P; Q :- Q.

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.  For instance, 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, you can often greatly reduce the number of time- and space-expensive choice points you push.

-- Tim

Tim Lindholm				Manager, Prolog Technology Group
Quintus Corporation                     InterNet:       tim@quintus.com
2100 Geng Road                          FAX:            415 494 7608
Palo Alto, California 94303             Phone:          415 813 3844

In article <MATSC.92Sep2141625@vishnu.sics.se>
	matsc@sics.se (Mats Carlsson) writes:

 |   do you do anything special about this construct, or do you just
 |   consider it as an ordinary predicate with a definition like:
 |   P ;_Q :- P.
 |   _P; Q :- Q.
 |
 |SICStus Prolog does nothing special, and considers it as an ordinary
 |predicate as you describe.

Don't you have to do something special to extend the scope of cut
operators?  As I understand it, the program A below has only one
solution of X=1, while the program B should have both X=1 and X=2.

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

In case of SICStus, this "something special" might have been small.
More complicated mechanisms might be needed in an implementation
without a separate choice point stack.

Takashi Chikayama
ICOT

The main reason for compiling disjunctions is that it can speed up code
like

	p(X) :-
	  (  X >= 0 ->
	     do_something_for_positive_X(X)
	  ;  do_something_for_negative_X(X)
	  ).

This can be converted to test-and-branch code, since it is completely
determinate. Obviously, the plain WAM must be extended with special
instructions to allow such things.

	Jens.
--
Internet: jensk@hpbeo82.bbn.hp.com    HPDESK : JENS_KILIAN%XU@HP1200
MausNet:  Jens Kilian @ BB                     KILIAN_JENS/HP1200_XU@hpbbi4
Phone: (0|+49)7031-14-4308            TELNET : 778-4308
Fax  : (0|+49)7031-14-2049
-------------------------------------------------------------------------------
As the air to a bird, or the sea to a fish, so is contempt to the contemptible.

|>    P ;_Q :- P.
|>    _P; Q :- Q.
|> 
|> SICStus Prolog does nothing special, and considers it as an ordinary
|> predicate as you describe.

You certainly do not do so!
Consider the above example:

go1(X) :- foo(X), ( ! ; true).
go2(X) :- foo(X),  or(!, true).

foo(1).
foo(2).

or(P,_) :- P.
or(_,Q) :- Q.

Executing this in SICSTUS gives:

| ?- go1(X).

X = 1 ? ;

no
| ?- go2(X).

X = 1 ? ;

X = 1 ? ;

X = 2 ? ;

X = 2 ? ;

no
| ?- ^D
{ End of SICStus execution, user time 0.060 }


Is it a kind of remake for "go2 considered harmful" ? :-)


More seriously, how do you treat the so-called "transparency" of the cut ?

> >The main reason for compiling disjunctions is that it can speed up code
> >like
> >
> >	p(X) :-
> >	  (  X >= 0 ->
> >	     do_something_for_positive_X(X)
> >	  ;  do_something_for_negative_X(X)
> >	  ).
> >
> 
> No. The main reason for compiling disjunctions is to avoid to build a structure
> and metacall it. The improvement you mention is also significant, but nowhere as important as this.
> 
> --Micha

I was thinking about the alternative approach of compiling a disjunction
to a call of an auxiliary predicate:

P :- Q; R.       ==>	P :- dummy(...).

			dummy(...) :- Q.
			dummy(...) :- R.

where in place of ... you have to insert the variables occuring in Q and R, as
well as any information needed for handling cuts.

	Sorry about the confusion,

	Jens.
--
Internet: jensk@hpbeo82.bbn.hp.com    HPDESK : JENS_KILIAN%XU@HP1200
MausNet:  Jens Kilian @ BB                     KILIAN_JENS/HP1200_XU@hpbbi4
Phone: (0|+49)7031-14-4308            TELNET : 778-4308
Fax  : (0|+49)7031-14-2049
-------------------------------------------------------------------------------
As the air to a bird, or the sea to a fish, so is contempt to the contemptible.

In article <1992Sep1.160505.6828@irisa.fr>, serge@irisa.fr (Serge Lehuitouze) writes:
> You, WAM gurus, do you do anything special about this construct, or do you just
> consider it as an ordinary predicate with a definition like:
> P ;_Q :- P.
> _P; Q :- Q.

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 yes, disjunction is usually compiled specially, for two important
reasons:
    1.  It would be unreasonably slow and inefficient to do otherwise.
    2.  Disjunction and if->then;else are transparent to cuts, that is,
	a cut inside one of them has effect on the whole predicate,
	not just the disjunction or if->then;else.

-- 
You can lie with statistics ... but not to a statistician.

In article <MATSC.92Sep2141625@vishnu.sics.se>, matsc@sics.se (Mats Carlsson) writes:
>    do you do anything special about this construct, or do you just
>    consider it as an ordinary predicate with a definition like:
>    P ;_Q :- P.
>    _P; Q :- Q.
> 
> SICStus Prolog does nothing special, and considers it as an ordinary
> predicate as you describe.

That cannot be so, because SICStus Prolog gets the right answer for this
program:

    p :- ( q(1), ! ; q(2) ).
    p :- q(3).

    q(X) :- write(X), nl.

    ?- p, fail.

The right answer is to write 1 and then fail.  If it were done this way:

    p :- 'OR'( (q(1),!), q(2) ).
    p :- q(3).

    'OR'(P, Q) :- call(P).
    'OR'(P, Q) :- call(Q).

    q(X) :- write(X), nl.

which _would_ treat ; as an ordinary predicate, then the output would
be 1 2 3.  SICStus Prolog gets this right, so there has to be _something_
special about disjunction.

-- 
You can lie with statistics ... but not to a statistician.

SICStus Prolog do it this way:

p :- (x,! ; y).                 q :- a, (b,! ; c).
p :- z.                         q :- d.

                  is converted to

p :- choice(C), x, cut(C).      q :- choice(C), a, q'(C).
p :- y.                         q :- d.
p :- z.
                                q'(C) :- b, cut(C).
                                q'(_) :- c.

Where choice(C) binds C to a reference to the youngest choicepoint alive
when calling q/0 or p/0, and cut(C) clears all choicepoints younger than C.


 o
Ralle
--
Roland Karlsson             SICS, PO Box 1263, S-164 28 KISTA, SWEDEN
Internet: roland@sics.se    Tel: +46 8 752 15 40          Fax: +46 8 751 72 30
Telex: 812 6154 7011 SICS   Ttx: 2401-812 6154 7011=SICS