%CUT (!)

%Cut tells Prolog not to backtrack on certain choices that it makes:

l(X,Y) :- a(X,Y).
l(m,n).

a(X,Y) :- b(X),!,c(Y),d.
b(e).
b(f).
c(g).
c(h).
d.

%The location of ! is important (thus spoiling our declarative view again):

a(X,Y) :- b(X),c(Y),!,d.
b(e).
b(f).
c(g).
c(h).
d.

%Uses of cut:
%- to say "you have found the right clause for this goal"

%Example 1: resistance revisited
resistance(N,R) :- 
  number(N), !, R = N.  % only this clause makes sense for numbers
                        % but for efficiency, we cut the rest.
resistance(series(C1,C2),R) :-
  resistance(C1,R1), 
  resistance(C2,R2),
  R is R1 + R2.
resistance(par(C1,C2),R) :-
  resistance(C1,R1),
  resistance(C2,R2),
  R is (R1*R2)/(R1+R2).

%- to say "this is the only solution"

%Example 2: for-loop
%:- for(0,A,...).  % for I = 1 to A do...

%for(A,A,...) :- !.  % if we didn't put a cut here, big trouble
%for(I,A,...) :-
%  NewI is I + 1,
%  ....NewI...
%  for(NewI,A,...).

%- to say "fail immediately without looking for more solutions"

%Example 3: integer division

% div(J,I,Quotient,Remainder): compute I/J in integers
div(0,_,_,_) :- write('Division by zero'),!,fail.  % fail by itself not enough
div(J,I,Q,R) :-
  J > I, !, Q = 0, R = I.  % this cut is of the second kind
div(J,I,Q,R) :-
  IMinusJ is I - J,
  div(J,IMinusJ,QMinus1,R),
  Q is QMinus1 + 1.

%We can also classify cuts into two kinds:
%- *green* cuts: made for efficiency only.  If you take a green cut out,
%  the program may run slower, but you still get all and only the right
%  answers.
%- *red* cuts: enforce correctness.  If you take a red cut out, you
%  may get a wrong answer, or the right answers plus some additional
%  wrong answers.

%Which cuts in the above 3 examples are green?  Which are red?

%Red cuts generally make code less readable, and more prone to error.
%Don't use them.

%Example 4: list membership

%This version backtracks through all members of a list:
member(E,[E|_]).
member(E,[_|Rest]) :- member(E,Rest).

%This version does not - it simply verifies that a given element
%is in the list:
memberchk(E,[E|_] :- !.
memberchk(E,[_|Rest]) :- memberchk(E,Rest).

%Notice that the second is only appropriate when the first argument
%is instantiated in the memberchk/2 goal.  This kind of knowledge,
%about which arguments are to be instantiated and which not, is
%called *mode*.

:- mode memberchk(+E,+List)
:- mode member(?E,+List)

% Some also write mode like this: memberchk(+,+) or member(?,+)

%Example 5: implementing negation as failure

not(Goal) :- call(Goal),!,fail.
not(_Goal).

%SHALLOW CUTS - the if-then-else of Prolog.

%There is a special predicate:  P -> Q ; R

%where P, Q and R are goals.  This means, "if P succeeds, then Q, else
%R."  Shallow cuts never backtrack into P, and, if they have selected
%Q, never backtrack from Q into R, i.e., the ";" in this notation is
%not a real disjunction.  Shallow cuts behave as though they have
%been implemented by:

%P -> Q ; R :-
%  P, !, Q.
%P -> Q ; R :-
%  R.

%Note that the cut used in this would-be definition has scope only over
%the shallow cut.  A shallow cut does not behave like a cut in the
%predicates that use it.

%Example 1:  bind/1 takes a list of terms and attempts to instantiate only
%the ones that are so-far uninstantiated.

bind([]).
bind([X|Xs]) :-
   (var(X) -> X = v ; true),
   bind(Xs).

:- bind([X,1,Y,2,Z,3]).

%Example 2: buggy_bind_ones/1 should do the same thing, but insist that 
%those terms that have already been instantiated be 1:

buggy_bind_ones([]).
buggy_bind_ones([X|Xs]) :-
  var(X) -> X = v, buggy_bind_ones(Xs).
buggy_bind_ones([1|Xs]) :-
  buggy_bind_ones(Xs).

%P -> Q (with no R) is a shorthand for P -> Q ; fail.  Notice that the
%shallow cut in the second clause does not prevent the application of
%the third clause, because the shallow cut does not have scope over
%the clauses of bind_ones/1 - only over the goals Q and fail.  So this
%predicate has a choice point:

:- buggy_bind_ones([X,1,Y,1,Z,1]).

%Better:

bind_ones([]).
bind_ones([X|Xs]) :-
  var(X),
  !, X = v, bind_ones(Xs).
bind_ones([1|Xs]) :-
  bind_ones(Xs).

:- bind_ones([X,1,Y,1,Z,1]).

%or better still:

bind_ones([]).
bind_ones([X|Xs]) :-
  (var(X) -> X = v ; X = 1),
  bind_ones(Xs).

%Big Example: natural language processing with dynamic programming
%             ("chart parsing")

% word-string Ws has category Cat
parse(Ws,Cat) :-
  retractall(edge(_,_,_)),
  length(Ws,Len),
  reverse(Ws,WsRev),
  build(WsRev,Len),
  edge(0,Len,Cat).

retractall(C) :-
  retract(C),
  fail.         % this is called a *failure-driven loop*
retractall(_C). % - it's a good way to find all solutions to a predicate
                % with side-effects.

% close parsing chart from Len-1 to the end
build([],0).
build([W|_],Len) :-
  lex(W,LexCat),
  LenMinus1 is Len - 1,
  assert(edge(LenMinus1,Len,LexCat)),
  close_edge(LenMinus1,Len,LexCat).
build([_|WsRev],Len) :-
  LenMinus1 is Len - 1,
  build(WsRev,LenMinus1).

% close chart with N-M-Cat as leftmost edg
close_edge(N,M,Cat) :-
  rule(Mother,[Cat|Dtrs]),
  find_dtrs(Dtrs,M,R),
  assert(edge(N,R,Mother)),
  close_edge(N,R,Mother).

find_dtrs([],N,N).
find_dtrs([D|Dtrs],N,R) :-
  edge(N,M,D),
  find_dtrs(Dtrs,M,R).

rule(s,[np,vp]).
rule(vp,[v,np]).
rule(np,[adj,np]).

lex(happy,adj).
lex(babies,np).
lex(run,vp).
lex(see,v).
lex(computers,np).

%Chart-parsing makes string-recognition cubic-time with grammars like this.
%Without dynamic programming, it's worst-case exponential.