========================[ Prolog readings ]=========================

The textbook describes the history and concepts of Prolog in Chapter 15. Read it!

The online free "Learn Prolog Now!" book is useful to get up to speed on writing
and reading Prolog:
  https://cs.union.edu/~striegnk/learn-prolog-now/html/index.html

The internals of Prolog's unification and resolution are best explained in the book
"Warren's Abstract Machine, A Tutorial Reconstruction" by Hassan A ̈it-Kaci
  https://cliplab.org/~logalg/slides/8_wam_AitKaci_book.pdf

Finally, for a bit of history, you can read this story of why you don't see
Prolog more often: https://vanemden.wordpress.com/2010/08/21/who-killed-prolog/

=========================[ Prolog examples ]=========================

Prolog's worked examples are among the best-trained by the generative AI models,
because Prolog has been around since early 1970s and has many carefully edited
tutorials. I had the following examples AI-generated, but it's highly likely
they are literal reproductions of classic code.

We saw these examples in class, executing under the free software SWI Prolog: 

% =============================================================
%  Prolog genealogy: worked examples
%  Load with:  ?- [family].
% =============================================================
%
%        tom + pam
%        /       \
%   bob + kate   liz + dan
%    /      \        |
%  jim      sue     amy
%   |
%  leo

% ---------- Facts ----------
parent(tom, bob).   parent(pam, bob).
parent(tom, liz).   parent(pam, liz).
parent(bob, jim).   parent(kate, jim).
parent(bob, sue).   parent(kate, sue).
parent(liz, amy).   parent(dan, amy).
parent(jim, leo).

male(tom).  male(bob).  male(dan).  male(jim).  male(leo).
female(pam). female(liz). female(kate). female(sue). female(amy).

% ---------- Simple rules ----------
father(F, C) :- parent(F, C), male(F).
mother(M, C) :- parent(M, C), female(M).

grandparent(G, C) :- parent(G, P), parent(P, C).

% Full siblings: same father and same mother, not the same person.
sibling(X, Y) :-
    father(F, X), father(F, Y),
    mother(M, X), mother(M, Y),
    X \== Y.

brother(B, X) :- sibling(B, X), male(B).
sister(S, X)  :- sibling(S, X), female(S).

uncle(U, N) :- parent(P, N), sibling(U, P), male(U).
aunt(A, N)  :- parent(P, N), sibling(A, P), female(A).

cousin(X, Y) :- parent(PX, X), parent(PY, Y), sibling(PX, PY).

% ---------- Recursive rules ----------
ancestor(A, D) :- parent(A, D).
ancestor(A, D) :- parent(A, X), ancestor(X, D).

% Same, but also counts generations (1 = parent, 2 = grandparent, ...)
ancestor(A, D, 1) :- parent(A, D).
ancestor(A, D, N) :- parent(A, X), ancestor(X, D, N0), N is N0 + 1.

% =============================================================
%  Worked queries (type ; to see further answers)
% =============================================================
%
% 1. Who is Jim's father?
%    ?- father(F, jim).
%    F = bob.
%
% 2. Which children does Pam have?
%    ?- mother(pam, C).
%    C = bob ; C = liz.
%
% 3. Who are Amy's grandparents?
%    ?- grandparent(G, amy).
%    G = tom ; G = pam.
%
% 4. Siblings, uncles, aunts, cousins
%    ?- sibling(jim, S).     S = sue.
%    ?- uncle(U, amy).       U = bob.
%    ?- aunt(A, jim).        A = liz.
%    ?- cousin(jim, C).      C = amy.
%
% 5. All of Leo's ancestors, sorted and without duplicates
%    ?- setof(A, ancestor(A, leo), L).
%    L = [bob, jim, kate, pam, tom].
%
% 6. All of Tom's descendants, and how many there are
%    ?- setof(D, ancestor(tom, D), L).
%    L = [amy, bob, jim, leo, liz, sue].
%    ?- aggregate_all(count, ancestor(tom, _), N).
%    N = 6.
%
% 7. Leo's great-grandparents (3 generations up)
%    ?- ancestor(A, leo, 3).
%    A = tom ; A = pam.
%
% 8. People with no children (leaves of the tree).
%    P^ means "for some P", so results aren't grouped by parent.
%    ?- setof(C, P^(parent(P, C), \+ parent(C, _)), L).
%    L = [amy, leo, sue].
%
% 9. Founders: parents whose own parents aren't recorded
%    ?- setof(X, C^(parent(X, C), \+ parent(_, X)), L).
%    L = [dan, kate, pam, tom].

?- [family].
true.

?- parent(X,leo).
X = jim.

?- grandparent(X,leo).
X = bob ;
X = kate ;
false.

?- grandfather(X,leo).
ERROR: Unknown procedure: grandfather/2 (DWIM could not correct goal)
?- grandparent(X,leo).
X = bob ;
X = kate ;
false.

%%  At this point I added the rule
%     grandfather(G, C) :- grandparent(G, C), male(G).
%   and reloaded:

?- [family].
true.

?- grandfather(X,leo).
X = bob ;
false.

%% When given multiple variables, Prolog will iterate through all of their
%%  matching combinations so long as you press ; . It will stop if you press . 

?- parent(X,Y).
X = tom,
Y = bob ;
X = pam,
Y = bob ;
X = tom,
Y = liz ;
X = pam,
Y = liz ;
X = bob,
Y = jim ;
X = kate,
Y = jim ;
X = bob,
Y = sue ;
X = kate,
Y = sue ;
X = liz,
Y = amy ;
X = dan,
Y = amy ;
X = jim,
Y = leo.

?- grandparent(X,Y).
X = tom,
Y = jim ;
X = tom,
Y = sue ;
X = pam,
Y = jim ;
X = pam,
Y = sue ;
X = tom,
Y = amy ;
X = pam,
Y = amy ;
X = bob,
Y = leo ;
X = kate,
Y = leo ;
false.

%% Let's see the 8 queens solution. It's surprisingly short but relies on a bit
%%  of groundwork. Think the AMB examples from Scheme, but optimized for tree search.

?- help(permutation).
            Availability: :- use_module(library(lists)). (can be autoloaded)

permutation(?Xs, ?Ys)                                               [nondet]
    True when Xs is a permutation of Ys. This can solve for  Ys given  Xs or
    Xs  given  Ys,  or  even  enumerate  Xs and  Ys together.  The predicate
    permutation/2 is primarily intended to generate permutations.  Note that
    a  list  of  length  N  has N!  permutations, and  unbounded permutation
    generation becomes prohibitively expensive, even for rather  short lists
    (10! = 3,628,800).

    If both Xs and  Ys are  provided and  both lists  have equal  length the
    order is |Xs|^2. Simply testing whether Xs is a permutation of Ys can be
    achieved in order log(|Xs|) using msort/2 as illustrated below  with the
    semidet predicate is_permutation/2:

        is_permutation(Xs, Ys) :-
          msort(Xs, Sorted),
          msort(Ys, Sorted).

    The example below illustrates that Xs and Ys being proper lists is not a
    sufficient condition to use the above replacement.

        ?- permutation([1,2], [X,Y]).
        X = 1, Y = 2 ;
        X = 2, Y = 1 ;
        false.

    Errors
        type_error(list, Arg) if either argument is not a proper  or partial
        list.
true.

?- permutation([1,2,3], X).
X = [1, 2, 3] ;
X = [1, 3, 2] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
false.

%% Now let's see the 8 queens solution. Note the recursive function definitions
%%   of safe and noattack, and the pattern for matching the head and the tail of
%%   a list, [Q1|Qs] .

%%---- begin queens.pl ----------------

queens(Qs) :- permutation([1,2,3,4,5,6,7,8], Qs), safe(Qs).

safe([]).
safe([Q|Qs]) :- noattack(Q, Qs, 1), safe(Qs).

noattack(_, [], _).
noattack(Q, [Q1|Qs], D) :- abs(Q - Q1) =\= D, D1 is D + 1, noattack(Q, Qs, D1).

%%----- end queens.pl

?- [queens].
true.

?- queens(Q).
Q = [1, 5, 8, 6, 3, 7, 2, 4] ;
Q = [1, 6, 8, 3, 7, 4, 2, 5] ;
Q = [1, 7, 4, 6, 8, 2, 5, 3] ;
Q = [1, 7, 5, 8, 2, 4, 6, 3] ;
Q = [2, 4, 6, 8, 3, 1, 7, 5] ;
Q = [2, 5, 7, 1, 3, 8, 6, 4] ;
Q = [2, 5, 7, 4, 1, 8, 6, 3] ;
Q = [2, 6, 1, 7, 4, 8, 3, 5] ;
Q = [2, 6, 8, 3, 1, 4, 7, 5] ;
Q = [2, 7, 3, 6, 8, 5, 1, 4] ;
Q = [2, 7, 5, 8, 1, 4, 6, 3] ;
Q = [2, 8, 6, 1, 3, 5, 7, 4] ;
Q = [3, 1, 7, 5, 8, 2, 4, 6] .   % stopped here

%% Now for a creative interpretation of the family examples, inspired by
%%  the "I am my own grandpa" song.

%% ----------------------[ grandpa example ]---------------------
% =============================================================
%  "I'm My Own Grandpa" in Prolog
%  Load on its own:  ?- [own_grandpa].
%  (Self-contained: it defines its own parent/2, male/1, etc.)
%
%  Inspired by https://www.youtube.com/watch?v=eYlJH81dSiw
%
% =============================================================
%
%  The story: Ray marries a widow who has a grown-up daughter.
%  Ray's dad then marries that daughter. Each couple has a son.
%
%     widow ==== ray          dad ==== daughter
%       |     \  |            |   \      |
%   daughter   son1          ray    son2
%
%  (==== is marriage; daughter is widow's child from before)

% ---------- Facts ----------
male(ray).  male(dad).  male(son1).  male(son2).
female(widow).  female(daughter).

parent(dad, ray).
parent(widow, daughter).
parent(ray, son1).      parent(widow, son1).
parent(dad, son2).     parent(daughter, son2).

married(ray, widow).
married(dad, daughter).

% ---------- Rules from family.pl (biological only) ----------
grandparent(G, C) :- parent(G, P), parent(P, C).

% Sibling relaxed to include half-siblings (share at least one parent)
sibling(X, Y) :- parent(P, X), parent(P, Y), X \== Y.
brother(B, X) :- sibling(B, X), male(B).

% ---------- New: marriage and step-relations ----------
spouse(X, Y) :- married(X, Y) ; married(Y, X).

stepparent(S, C) :- spouse(S, P), parent(P, C), \+ parent(S, C).

% A "family parent" is a parent or a step-parent
family_parent(P, C) :- parent(P, C) ; stepparent(P, C).

family_grandparent(G, C) :- family_parent(G, P), family_parent(P, C).
grandpa(G, C)    :- family_grandparent(G, C), male(G).
grandma(G, C)    :- family_grandparent(G, C), female(G).

uncle(U, N)      :- family_parent(P, N), sibling(U, P), male(U).
son_in_law(S, P) :- spouse(S, C), family_parent(P, C), male(S).
brother_in_law(B, X) :- spouse(X, S), sibling(B, S), male(B).

% =============================================================
%  Worked queries: the song, one twist at a time
% =============================================================
%
% 1. Ray's wife's daughter married Ray's dad, so she is Ray's stepmother.
%    ?- stepparent(daughter, ray).
%    true.
%
% 2. And Ray's dad became Ray's son-in-law.
%    ?- son_in_law(dad, ray).
%    true.
%
% 3. Ray's son (son1) is Ray's stepmother's half-brother, so he's Ray's uncle...
%    ?- uncle(U, ray).
%    U = son1.
%
% 4. ...and he's Ray's dad's brother-in-law.
%    ?- brother_in_law(son1, dad).
%    true.
%
% 5. Dad's new son (son2) is Ray's brother, and also his grandchild,
%    since his mother is his stepdaughter.
%    ?- brother(son2, ray).
%    true.
%    ?- family_grandparent(ray, son2).
%    true.
%
% 6. Ray's wife is Ray's stepmother's mother, so she's Ray's grandmother.
%    ?- grandma(G, ray).
%    G = widow.
%
% 7. The punchline: as Ray's grandmother's husband...
%    ?- grandpa(G, ray).
%    G = ray.
%
% 8. Note that it only works through step-relations. Without these it fails:
%    ?- grandparent(ray, ray).
%    false.


?- [grandpa].
[.. skipped ..]
true.

?- family_grandparent(ray,ray).
true ;
false.

%% --- To be continued .