Prolog Notes

Syntax of Prolog - (courtesy of Dr. Sunderranman)
----------------

(I) Terms represent data objects. There are 3 types of terms:

    (a) Atoms: symbolic atoms begin with lower-case letter
                 ex. tom, bill, a1
               numeric atoms
                 ex. 217, -32, 2.76

    (b) Variables: begin with upper-case letter or underscore
          ex. X, U, _x1, Tom, A1

    (c) Structures: two types:
             function structure: f(t1, ..., tn)
             list structure:      [t1, ..., tn]

                  where f is a symbolic atom called functor
                  and t1, ..., tn are terms


               ex. edge(3,7), f(g(1),h(2,3))
                   [a,b,c], [tom,X,f(tom)], [], [[a],[b]]

         Special Notation for lists: [c1, ..., cm|T]
              where c1, ..., cm are the first m elements of the list and
                    T is a LIST of the remaining elements

(II) Relation: r(t1, ..., tn)
          where r is a symbolic atom and t1, ..., tn are terms.

         ex. round, father(tom,bill), student(1111,jones,freshman,4.0)

(III) A Prolog Program consists of a finite number of Facts and Rules,
      where

      Fact: relation.
      Rule: relation :- relation-1, ..., relation-n.

(IV) Query:    ?- relation-1, ..., relation-n.

     used to invoke a program.


SAMPLE PROLOG PROGRAMS:
-----------------------


Ancestor program
----------------

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

List manipulation programs
--------------------------

member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).

append([],L,L).
append([A|X],Y,[A|Z]) :- append(X,Y,Z).

prefix(P,L) :- append(P,_,L).

suffix(S,L) :- append(_,S,L).

sublist(S,L) :- prefix(S,L).
sublist(S,[_|R]) :- sublist(S,R).

remove_contiguous([],[]).
remove_contiguous([X,X|L],R) :- remove_contiguous([X|L],R).
remove_contiguous([X|L],[X|R]) :- remove_contiguous(L,R).

reverse([],[]).
reverse([H|L],R) :- reverse(L,L1), append(L1,[H],R).

palindrome(L) :- reverse(L,L).

minmax(X,X,[X]).
minmax(Min,Max,[X|L]) :- minmax(Min2,Max2,L),
                         min(X,Min2,Min),
                         max(X,Max2,Max).
min(X,Y,X) :- X =< Y.
min(X,Y,Y) :- Y =< X.
max(X,Y,X) :- Y =< X.
max(X,Y,Y) :- X =< Y.

Replacing non-tail recursion with tail-recursion
--------------------------------------------------
Pumping technique.
-----------------

     reverse a list
     --------------

     reverse(L,R) :- reverse1(L,[],R).

     reverse1([],P,P).
     reverse1([X|L],P,S) :- reverse1(L,[X|P],S).


     minmax problem
     --------------

     minmax(X,X,[X]).
     minmax(Min,Max,[X|L]) :- minmax1(Min,Max,L,X,X).

     minmax1(Cmin,Cmax,[],Cmin,Cmax).
     minmax1(Min,Max,[X|L],Cmin,Cmax) :- X =< Cmin, minmax1(Min,Max,L,X,Cmax).
     minmax1(Min,Max,[X|L],Cmin,Cmax) :- Cmax =< X, minmax1(Min,Max,L,Cmin,X).
     minmax1(Min,Max,[X|L],Cmin,Cmax) :- minmax1(Min,Max,L,Cmin,Cmax).


Manipulating numbers
---------------------

V is Expression

   factorial
   ---------
     factorial(0,1).
     factorial(N,Nfac) :- N >= 1, M is N-1, factorial(M,Mfac),
                          Nfac is N * Mfac.


Delete an element from a list
-----------------------------

del(X,[X|Tail],Tail).
del(X,[Y|Tail],[Y|Tail1]) :- del(X,Tail,Tail1).

Generate all subsets of a set
-----------------------------

subset([],[]).
subset(S,SS) :- del(X,S,Y), subset(Y,SS).
subset(S,[X|Z]) :- del(X,S,Y), subset(Y,Z).

Permutations of a list
----------------------

permute([],[]).
permute(L,[X|P]) :- del(X,L,L1), permute(L1,P).

Given two equal sized lists, generate all possible pairings
-----------------------------------------------------------

generate(L1,L2,Pairs) :-
        permute(L2,M2),
        combine(L1,M2,Pairs).

combine([],[],[]).
combine([H1|T1],[H2|T2],[[H1,H2]|T]) :- combine(T1,T2,T).


Quick Sort
----------

qsort([],[]).
qsort([H|T],S) :-
  qsplit(H,T,A,B),
  qsort(A,A1),
  qsort(B,B1),
  append(A1,[H|B1],S).

qsplit(H,[A|X],[A|Y],Z) :- A =< H, qsplit(H,X,Y,Z).
qsplit(H,[A|X],Y,[A|Z]) :- A > H, qsplit(H,X,Y,Z).
qsplit(_,[],[],[]).

Merge Sort
----------

mergesort([],[]) :- !.
mergesort([X],[X]) :- !.
mergesort(X,Z) :- msplit(X,L1,L2),
                  mergesort(L1,M1),
                  mergesort(L2,M2),
                  merge(M1,M2,Z).

msplit([],[],[]) :- !.
msplit([X],[X],[]) :- !.
msplit([X,Y|Z],[X|L1],[Y|L2]) :- msplit(Z,L1,L2).

merge([],X,X) :- !.
merge(X,[],X) :- !.
merge([X|L],[Y|M],[X|N]) :- X @=< Y, !, merge(L,[Y|M],N).
merge([X|L],[Y|M],[Y|N]) :- Y @=< X, merge([X|L],M,N).

A LOGIC PUZZLE
--------------

Three friends came first, second and third in a programming contest.
Each of the three had a different first name, liked a different
sport, and had a different nationality. Following are some clues:

- Michael likes basketball and did better than the American.
- Simon, the Israeli, did better than the tennis player.
- The cricket player came first.

Who is the Australian? What sport does Richard play?

did_better(A,B,[A,B,C]).
did_better(A,C,[A,B,C]).
did_better(B,C,[A,B,C]).

name_of(person(A,B,C),A).
nationality(person(A,B,C),B).
sport(person(A,B,C),C).

first([X|Xs],X).

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

friends(0,[]) :- !.
friends(N,[person(Name,Nat,Sport)|List]) :- M is N-1, friends(M, List).

answer(Aussie,Richards_Sport) :-
    friends(3,Friends),

    did_better(M1,M2,Friends),     % First Clue
    name_of(M1,michael),
    sport(M1,basketball),
    nationality(M2,american),

    did_better(M3,M4,Friends),     % Second Clue
    name_of(M3,simon),
    nationality(M3,israeli),
    sport(M4,tennis),

    first(Friends,M5),             % Third Clue
    sport(M5,cricket),

    member(Q1,Friends),            % First Question
    name_of(Q1,Aussie),
    nationality(Q1,australian),

    member(Q2,Friends),            % Second Question
    name_of(Q2,richard),
    sport(Q2,Richards_Sport).