%META-LOGICAL PREDICATES
%Prolog has a number of built-in predicates that implement functionality
%that we could never implement ourselves in "pure" Prolog.  That is,
%they add to the expressive power of our programs.  Examples:

%var(X).      X is an uninstantiated variable
%             (NOTE: *binding* two variables, e.g., X = Y, does not instantiate
%              them.  Instantiation is often used only to substitutions of a
%              constant or compound term for a variable).
%nonvar(X).   X is a currently instantiated variable.
%ground(X).   X is currently instantiated to a ground term.
%atom(X).     X is currently instantiated to an *atom*, i.e., a non-numerical 
%              constant.
%atomic(X).   X is currently instantiated to a constant (including numbers).
%compound(X). X is a compound term, i.e., not atomic or an uninstantiated var.

%These are also non-monotonic, because they refer to the CURRENT state of
%instantiation, which may change.  But it ONLY changes in the case of
%uninstantiated variables.  A constant, for example, cannot later become a
%compound term.

%RECURSION
%Another place where our declarative view of programming breaks down is in
%recursion.  Here the problem is termination:

append([],L,L).
append([H|T],L1,[H|L2]) :-
  append(T,L1,L2).

:- append(X,[a,b],Y).

% versus:

append([H|T],L1,[H|L2]) :-
  append(T,L1,L2).
append([],L,L).

:- append(X,[a,b],Y).

%Because of the order in which Prolog tries clauses, the second will never
%terminate on queries with variable first-arguments.  For this reason, we
%adopt the convention that base cases PRECEDE recursive cases in recursive
%predicate definitions.

%BACKTRACKING
%Consider the first (and better) definition of append/3 again:

append([],L,L).
append([H|T],L1,[H|L2]) :-
  append(T,L1,L2).

:- append(X,Y,[a,b,c,d,e]).
:- append(X,[a,b],Y).

%This terminates, in the sense that it provides us with a solution, but
%if we reject this solution:

%X = []
%Y = [a,b] ? ;  [typing ';' means 'fail']

%we get many more - infinitely many, in fact.

%This is an example of Prolog's backtracking mechanism at work.  When
%Prolog reduces a goal for which there is more than one possible reduction,
%it chooses the first, but leaves a *choice point* - a reminder that we
%can return to the goal and find other solutions.  If some later step in
%the reduction fails (either because of the lack of a solution, or because
%Prolog gives us a solution and we type ';'), Prolog returns to the
%most recent choice point to consider the next alternative.

%Example 1:
p(X) :- q(X), r(X).
q(d). q(e). q(f). q(g).
      r(e).       r(g).

:- p(X).

%Example 2:
p(X) :- q(X), r(X).
q(X) :- s(X), t(X).

s(d). s(e). s(f). s(g).
t(d).             t(g).
      r(e).       r(g).

:- p(X).

%Like other languages, Prolog internally uses a stack to keep track of 
%  recursion.
%Prolog also internally uses a stack to keep track of choice points.

%In general, logical disjunction corresponds to *non-deterministic search*
%                                                  (backtracking)
%            logical conjunction corresponds to *continuation*
%                                                  (sequential reduction)

%Backtracking plus reduction gives Prolog the built-in ability to perform
%*top-down search*.  This naturally models program execution in imperative
%languages (main program calls subprograms, which call sub-subprograms, etc.).

%An alternative is *bottom-up search*: starting with facts and using rules
%in their *forward* direction to deduce other facts.  The Coral programming
%language does this.  Bottom-up search is also often used in natural language
%processing.

%Bottom-up search has:
%  - very early access to the axioms of inference, which
%  - often results in greater speed (because variables are bound early, which
%    creates opportunities for failure).  But
%  - it is not goal-oriented --- many useless facts may be derived along the 
%    way.

%Top-down search is:
%  - very goal-oriented, but
%  - it often has problems with:
%    * termination
%    * efficiency

%There are many hybrid search strategies, too.  The best combination depends
%on the empirical domain being modelled.

%NEGATION-AS-FAILURE
%Prolog doesn't have true negation, but it does have a non-monotonic operator
%that corresponds to failure of proof.

%Example:
f(a).
f(c).

:- \+ f(b).
:- \+ f(X).

% \+ G succeeds as a goal, iff G fails.

:- \+ \+ memory_intensive(X),  % exits with X unchanged
   f(Y), g(Y).

%This does not always yield the desired meaning of negation, e.g.:

loves(john,X) :- woman(X), famous(X).

woman(jane).
woman(marilyn).
famous(marilyn).

hates(john,X) :- \+ loves(john,X).

%There are infinitely many women that John hates, not just Jane:
:- hates(john,jane).
:- hates(john,susan).
:- hates(john,betty).
%...

%Plus John hates many things:

:- hates(john,pizza).
:- hates(john,john).

%X is not required to be a woman.

%Better to use:
hates(john,X) :- woman(X), \+ loves(john,X).

woman(X) is a *guard* - it protects \+ from making unwanted inferences.

%DYNAMIC PREDICATES

:- assert(hates(john,pizza)).  % hates/2 is *dynamic*
:- assert(hates(john,jane)).
:- assert(hates(john,X) :- woman(X), \+ loves(john,X)).

:- retract(hates(john,jane)).

%In programs:
:- dynamic hates/2.  % hates/2 is *dynamic*
hates(john,pizza).
hates(john,jane).
hates(john,X) :- woman(X), \+ loves(john,X).

:- retract(hates(john,jane)).

%MORE ABOUT ASSERT

:- assert(C).  % assert clause (you don't care where)
:- asserta(C). % assert clause C at the beginning of the dynamic pred store
:- assertz(C). % assert clause C at the end of the dynamic pred store
:- retract(C). % remove clause C from the dynamic pred store

%Example:

record_marks([]).
record_marks([M|Ms]) :-
  asserta(mark(M)),
  record_marks(Ms).

:- record_marks([50,60,70,80,90]).

%What about with assertz/1?

%RECURSION WITH FUNCTIONS

%We have already seen append/3:

append([],L,L).
append([H|T],L1,[H|L2]) :-
  append(T,L1,L2).

%This recurses on the list in the first argument.
%You can use other recursive term representations to drive a recursive
%program too.

%Example: Simple electrical circuits
%     <number>: single resistor
%series(C1,C2): two circuits in series
%   par(C1,C2): two circuits in parallel

%Problem: write a program to compute the total resistance of a circuit.
%Solution:
resistance(N,R) :- 
  number(N), R = N.
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).

:- resistance(series(3,par(6,3)),R).