/* 
*  This file builds on what we learned in class, concerning
*  CUT (!).  Referring to the slide "Cut Can Reduce your Search
*  Space".  I've defined 4 versions of q(X), with and without CUT 
*  and trace various queries.
*/


even(2).
even(4).
even(6).
odd(1).
odd(3).
odd(5).
odd(7).
a(4).
b(3).

q(X) :- even(X), a(X).       /* (1) */
q(X) :- odd(X), b(X).        /* (2) */

qcut(X) :- even(X), !, a(X). /* (3) */
qcut(X) :- odd(X), !, b(X).  /* (4) */


/*******************************************************************
*  Example 1.  Prolog tries to find an X such that q(X).
*  It first tries to prove it with (1) with X instantiated to 2. 
*  even(2) succeeds, but a(2) fails, so it backtracks trying to
*  find another instantiation of X within (1) for which even(X).
*  It tries 4 and succeeds.  *  I press ; to continue the search.
*  Please look through the trace to see what happens.  It tries all 
*  X that succeed on even(X), once there is nothing else to try, 
*  it proceeds to rule (2) and tries to prove q(X) this way, using 
*  X instantiated to 1, 3, 5, and then 7. Having exhausted the search 
*  space, it stops.


?- trace.

Yes
[trace]  ?- q(X).
   Call: (7) q(_G283) ? creep
   Call: (8) even(_G283) ? creep
   Exit: (8) even(2) ? creep
   Call: (8) a(2) ? creep
   Fail: (8) a(2) ? creep
   Redo: (8) even(_G283) ? creep
   Exit: (8) even(4) ? creep
   Call: (8) a(4) ? creep
   Exit: (8) a(4) ? creep
   Exit: (7) q(4) ? creep

X = 4 ;
   Redo: (8) even(_G283) ? creep
   Exit: (8) even(6) ? creep
   Call: (8) a(6) ? creep
   Fail: (8) a(6) ? creep
   Redo: (7) q(_G283) ? creep
   Call: (8) odd(_G283) ? creep
   Exit: (8) odd(1) ? creep
   Call: (8) b(1) ? creep
   Fail: (8) b(1) ? creep
   Redo: (8) odd(_G283) ? creep
   Exit: (8) odd(3) ? creep
   Call: (8) b(3) ? creep
   Exit: (8) b(3) ? creep
   Exit: (7) q(3) ? creep

X = 3 ;
   Redo: (8) odd(_G283) ? creep
   Exit: (8) odd(5) ? creep
   Call: (8) b(5) ? creep
   Fail: (8) b(5) ? creep
   Redo: (8) odd(_G283) ? creep
   Exit: (8) odd(7) ? creep
   Call: (8) b(7) ? creep
   Fail: (8) b(7) ? creep

No

*/
/*******************************************************************
*  Example 2.  Now we try to prove q(2).  Same query, but with the
*  argument of q already instantiated.
*  even(2) suceeds from the Prolog database, so we try to prove a(2)
*  and fail.  There is no way to backrack with rule (1) so we try 
*  rule (2).  odd(2) fails.  There is no where to backtrack, so
*  q(2) fails.  We could have predicted that trying to use rule (2)
*  to prove q(2) would be fruitless, since we know that even(X) is 
*  true iff odd(X) is false for the numbers we've defined.  This is
*  the motivation for introducing the CUT.


?- trace.

Yes
[trace]  ?- q(2).
   Call: (8) q(2) ? creep
   Call: (9) even(2) ? creep
   Exit: (9) even(2) ? creep
   Call: (9) a(2) ? creep
   Fail: (9) a(2) ? creep
   Redo: (8) q(2) ? creep
   Call: (9) odd(2) ? creep
   Fail: (9) odd(2) ? creep

No

*/
/*******************************************************************
*  Example 3.  Now we try another q(X)-like query using the predicate qcut(X), 
*  which is just the predicate q(X) with the CUT inserted, as we did in class.
*  Again, Prolog tries to find an X such that qcut(X).
*  It first tries to prove it with rule (3) with X instantiated to 2. even(2)
*  succeeds, ! (CUT) succeeds, but then a(2) fails.  We could backtrack to
*  find another way to prove a(2), if we had various rules for a(2).  (This
*  would make the example more interesting.) Since there is no other way
*  to prove a(2), we are done.  We cannot backtrack back over the ! (CUT)
*  to look for another instantiation for X, as we did with q(X).



?- trace.

Yes
[trace]  ?- qcut(X).
   Call: (8) qcut(_G286) ? creep
   Call: (9) even(_G286) ? creep
   Exit: (9) even(2) ? creep
   Call: (9) a(2) ? creep
   Fail: (9) a(2) ? creep
   Fail: (8) qcut(2) ? creep

No

*/
/*******************************************************************
*  Example 4.  Now we try the prove qcut(2).  This is analogous to
*  Example 2, but with the ! (CUT) inserted in the predicate definition.
*  even(2) holds from the Prolog database, ! (CUT), succeeds, so we try 
*  to prove a(2) and fail.  Again, if there were several rules for defining
*  a(2) or a(X), then we could backtrack to try each of these. In this
*  example, I did not add these.  Since a(2) fails, we try to backtrack
*  but cannot because we cannot backtrack over the ! (CUT), so the predicate
*  qcut(2) fails.  Note that in contrast to Example 2, it does not try
*  to prove qcut(2) using rule (4) because we knew this would be fruitless
*  since a term that is even is not odd, so we placed the CUT in rule (3)
*  to preclude this search from occuring as it did in Example 2.

[debug]  ?- trace.

Yes
[trace]  ?- qcut(2).
   Call: (8) qcut(2) ? creep
   Call: (9) even(2) ? creep
   Exit: (9) even(2) ? creep
   Call: (9) a(2) ? creep
   Fail: (9) a(2) ? creep
   Fail: (8) qcut(2) ? creep

No

*/