% Sample Prolog code.

% Can you guess how to put comments in Prolog?  :-o

above(X,Y) :- on(X,Y).
above(X,Z) :- on(X,Y), above(Y,Z).

pyramid(X) :- not(block(X)).

on(a,b).
on(b,c).
on(c,d).

% Other kinds of well-formed Prolog clauses:

on(a,X) :- pyramid(X); X = b.
on(a,b) :- (on(b,c); on(c,d)), on(a,c).

% ------ Examples of INVALID Prolog clauses:

% on(a,b), on(b,c) :- on(d,c). : non-atomic formula on left of :-
% not(on(X,Y)) :- on(Y,X). : again, non-atomic formula on left of :-
% on(X,Y) :- (on(a,b) :- on(b,c)), on(a,c). : embedded ":-" not allowed.

%  -----  More Prolog Examples  -----

owns(harry,ferari).
owns(larry,spot).
dog(spot).

loves(harry,mary).
loves(mary,larry).
loves(spot,X).
loves(larry,X) :- dog(X).
loves(harry,X) :- owns(harry,X).

%------ family relations

friendof(nick,rick).
friendof(rick,dick).

friendof(X,Y) :- friendof(Y,X).
% why should the above rule be last?



%   .......................................................
%------- Generic Programming examples.      (don't worry about these
% too much until we've talked more about inductive definitions.

% The examples above all have an AI-ish flavor.  But Prolog can
% be used for general purpose programming as well.

% linked list notation:
% [] : empty list (null in java)
% [H|T] : list with first element H (head, datatum), and T (next, tail) as
% rest of the list.
% [1,2,3] : shorthand for [1|[2|[3|[]]]].
% In Java, (integer) lists are usually represented by a class:
% class list { int head; list tail }.  It is very important to understand that
% the tail of a list is ANOTHER list.  It works just as well to invent our own
% notation using lists.  Pick the constant "null" as the empty list, and
% "cons(H,T)" instead of [H|T] (prolog lets you use new constants and variables
% without declaring them!).  The [1,2,3] would be the equivalent of 
% "cons(1,cons(2,cons(3,null)))".  We shall use the built-in prolog 
% notation for convenience.

% Determining if something is inside a list (acutally, the built-in predicate
% "member" does this also):

inlist(X,[X|T]).
inlist(X,[H|T]) :- inlist(X,T).

% "inlist" as a predicate axiomatizes the property of list membership in the
% sense that inlist(X,L) is provable from the two clauses above if AND ONLY if
% X is a member of the list L (assuming L terminates in the empty list).


% Taking two lists and merging them end to end (the built-in "append" does this
% also):  Notice that though a prolog query is simlilar to a function call,
% a query does not RETURN anything except true or false.  The result of the
% computation is stored in one of the variables that the interpreter instantiates.
% This is called "relational programming" as opposed to functional and imperative
% programming used in Java.
% We want "merge" to be axiomatized so that "merge(A,B,C)" holds if and only if
% C is the result of merging lists A and B:

merge([],L,L).  
merge([H|T],L,[H|M]) :- merge(T,L,M).

% The first clause states that merging the empty list onto a list has no effect.
% The second clause says, the result of merging a list of the form [H|T] onto
% a list L is of the form [H|M] where M is the result of (recursively) merging
% T onto L.

% finding the smallest number in a list of numbers:  
% Want: "min(X,L)" if and only if X is the smallest number in list L:
min([X],X).    % the smallest number of a singleton list is the single element
min([A,B|T],M) :- (A < B), min([A|T],M).
min([A,B|T],M) :- (B =< A), min([B|T],M).

% reversing a list:
% Want: "reverse(A,B)" iff A is the reverse of list B.
reverse([],[]).
reverse([H|T],L) :- reverse(T,S), merge(S,[H],L).

% Deleting all occurance of an element from a list:
% Want: "delete(X,L,M)" iff M is L with all occurences of X removed:
delete(X,[],[]).
delete(X,[X|T],R) :- delete(X,T,R).
delete(X,[H|T],[H|R]) :- not(X = H), delete(X,T,R).

% Removing duplicates
% Want "remdups(L,M)" iff M is L with all duplicate elements removed - e.g,
% remdups([3,4,3,5],X) will return true with X = [3,4,5]:

remdups([],[]).
remdups([H|T],[H|R]) :- delete(H,T,S), remdups(S,R).

%  Just as these axioms has a natural declarative interpretation, they can
% also be given a procedural interpretation because of the manner in which
% the clauses are written.  The first clause says to terminate the procedure
% at the empty list (because the result of removing duplicates from the
% empty list is the empty list).  The second clause says, procedurally, that
% to remove duplicates from a non-empty list of the form [H|T], we first
% delete all occurences of H from T, recording the result in S.  Then we
% (recursively) remove all duplicates from S, recording the result in R.
% The final result of removing duplicates from [H|T] will be [H|R].

% Compare delete and remdups with the Java equivalents: note the similarities!

% class intlist {int H; intlist T;}
%
% public class stuff_about_lists {
%
% intlist delete(int X, intlist L)
%  { if (L == null) return null;
%	 else if (X == L.H) return delete(X,L.T);
%	   else { L.T = delete(X,L.T);
%		    return L; }
%  }  
%
%  intlist remdups(intlist L)
%   { if (L == null) return null;
%	  else { L.T = remdups(delete(L.H,L.T));
%		   return L; }
%   }
%					   }  // end of stuff_about_lists

% The major differences between the Java and the Prolog renditions are 
% that:
%	1. java uses functions instead of relational predicates.
%       2. as a consequence of the above, prolog tends to use separate
%          clauses instead of a single function with if-else statements.
%       3. java is object-oriented, so we need to use classes, while
%          prolog can use the simpler, algebraic notation as in "[H|T]".
%       4. we have to declare types (int, intlist) in java.
%	5. java uses "assignment" as in L.T = delete(X,L.T), while prolog
%          avoids this "imperative" feature.  The java version may seem more
%	   efficient because it modifies the same list instead of creating new
%          ones.  But this kind of optimization can be performed by the compiler
%	   also, so the prolog version is not necessarily inefficient.

%  But the ALGORITHMS, and the LOGIC, are the same!

