/* COMMENTS:

   Comments in Prolog are written like this */

% or like this (one line only).

/* Note: Slides in the Prolog section of the course will be actual Prolog
   scripts, hence all text will be comments

*/


/* GNU PROLOG:

   The Prolog system on Imada is GNU Prolog.

   See http://pauillac.inria.fr/~diaz/gnu-prolog/ for manual and further
   info.

   Invoked by "gprolog".

   Is an interpreter (compilation to standalone program available).

   Once gprolog is running, a script is (re)loaded by "['script.pl'].".

   Note: "gprolog script.pl" will (rather annoyingly) NOT load a script.

   Remedy: If you are using the tcsh-shell (if "echo $SHELL" gives
   ...../tcsh), you may insert the following line in your .tcshrc file, and
   then "gp script.pl" will start gprolog and load the script:

     alias gp 'gprolog --query-goal "["'\\\'\!\*\\\''"]"'

*/ 


/* ABOUT PROLOG:

   - Automated deduction (in restricted area of logic) made into a
     programming language

   - Highlevel language especially suited for some applications (expert
     systems, language parsing and processing, symbolic computation, AI,
     exhaustive searches).

   - Is basically untyped (a very simple form of dynamic typing is used).

   - A program is a list (often called the database) of facts and deductive
     rules (collectively called clauses).

   - An execution is an systematic attempt (by the Prolog system) to
     logically deduce a statement given by the user (called a goal) using
     the facts and rules of the script.

*/


/* BASIC SYNTAX:

   TERMS are constants, variables, or structures.

   CONSTANTS are either alphanumeric strings starting with lowercase letter
   (underscore is allowed in string too, string may contain any character
   if surrounded by single quotes), or they have number syntax (in gprolog
   divided into INTEGERS and FLOATS, both with well-known syntax).

   Examples:

     george, a, you_may_use_underscore, '4youEye$only'

     234, -42

     34.67, -3.8, 34.2e-4

   They have no meaning except as identifiers. Constants with number syntax
   may, if asked to, later be interpreted as numbers. Strings and
   characters may be thought of as represented by constants in Prolog
   (characters being constants of length one). Constants without number
   syntax are called atoms. Constants in general are called atomic.

   VARIABLES are alphanumeric strings (underscore allowed too)
   starting with uppercase letter.

   Examples:

     X, Result, NumberOfReports, My_tax

   Variables can be bound to other terms through unification (see below)
   during execution. Initially in an execution, they are unbound.


   STRUCTURES consist of an atom (its FUNCTOR) and zero or more sub-terms (its
   arguments or COMPONENTS) in parentheses. They have no intrinsic meaning
   except structural. We may use them both as boolean functions
   (predicates), and as data structures (records). The number of sub-terms
   is called the arity of the structure. Nullary structures use no
   parentheses, i.e. they are just atoms.

   Examples:

     peter
     owns(peter,volvo_S60)
     owns(peter,X)
     owns(X,volvo_S60)

   CLAUSES (in scripts) specifies boolean functions (predicates) by
   specifying what makes them true. They are of the form

     S :- S1, S2, S3, S4,....,Si.

   (note the trailing period), where i >= 0, and S and the Sj's are
   structures (or variables, which then must be instantiated to structures
   at runtime). When i = 0, the clause may be written

     S.

   and is called a FACT. For i >= 1, a clause is called a RULE. S is called
   the head of the clause, and S1, S2, S3, S4,....,Si is the body of the
   clause.

   Examples:

   alice.
   owns(peter,volvo_S60).
   owns(alice,X).

   owns(peter,X) :- car(X),smart(X).

   The comma denotes boolean AND of the structures S1,S2,...,Si.

   One predicate may have several clauses. The predicate is considered
   true if at least one of the clauses for it is true - i.e. the
   clauses of a predicate are combined by boolean OR.

   A Prolog PROGRAM consists of a set of clauses.

   Above, alice is a nullary predicate, and owns is a binary
   predicate. This is expressed by the notation alice/0 and owns/2. Note
   that predname/2 and predname/3 are different predicates.

*/
   

/*

   OPERATORS are (as usual) binary structures where the functor is written
   using infix notation. Unary operators with prefix notation (but no
   parentheses) exist too.

   Noteworthy built-in operators are the LIST constructor '.', and the
   standard arithmetic operators ('+', '-', '*', etc). The identifier "[]"
   is a special constant (used to denote the empty list). There is
   the usual syntactic sugar/notational convenience for lists.

   Examples:

     .(3,.(4,[])) is the same as 3.(4.[]) which can be written [3,4].
     *(6,+(8,9)) is the same as 6*(8+9)

   Note: the last is a structure and is different from the constant 102(!).

   More examples:

     [peter,alice,[],[[[2,3],[3]],0],f(peter,alice)]
     [Head|Tail]

*/

/* UNIFICATION:

   Unification of two structures tests if they can possibly be equal
   (using pattern matching). If parts of the structures are variables,
   successful unification INSTANTIATES the variables in question.

		THIS IS HOW ASSIGNMENTS ARE MADE IN PROLOG.

   Examples:

   [1,peter,X,f(Y,20)] and [Z,peter,alice,f(2,20)] will unify
   succesfully, and the following instantiations will take place:

   X = alice
   Y = 2
   Z = 1

   f(X,X) and f(20,20) will unify succesfully and X will be instantiated to
   20.

   f(X,X) and f(19,20) will not unify succesfully. Nothing will be
   instantiated.

   X and Y will unify, and X and Y will now co-refer (must have same
   value, if one later is instantiated to something specific, the
   other is too).

   [Head|Tail] is shorthand for .(Head,Tail), and will unify with
   [1,2,3,4]. Head will be instantiated to 1, and Tail will be instantiated
   to [2,3,4]. So [H|T] in prolog corresponds to the pattern (h:t) in
   Haskell.

*/


/* GOALS are boolean questions asked by the user (at prompt in
   gprolog). More precisely, they are boolean statements (of the same form
   as right hand sides of rules) which the user would like to know if can
   be derived as true, given the facts and rules of the script.

   Prolog will try to SATISFY a goal using a search procedure among the
   clauses of the script:

   The clauses of the script are tested for unification with the goal one
   by one, topmost first.

   If the goal unifies with a fact, the goal is satisfied. If the goal
   unifies with a rule, the goal is substituted by the body of the
   rule. The terms of this right-handside are now subgoals, which the
   system will try to satisfy in the same manner, one by one from left to
   right.

   In general during the search, our current goal will be a list of
   subgoals with commas (signifying AND) in between, and the left-most of
   these is attempted unified with a head of a clause in the script. If
   there is a unification possible, the body of the clause is substituted
   for this subgoal - in particular, if the clause is a fact, the list of
   subgoals become shorter.

   If the list of subgoals vanishes, the original goal has been satisfied -
   i.e. a derivation of it has been found (it has been proven true based on
   the facts and rules in the script).

   If a subgoal cannot be satisfied, backtracking will take place, where
   earlier satisfied subgoals are tried for satisfaction in further ways
   (using other clauses).

   During satisfaction, variables may be instantiated (when expressions are
   unified). During backtracking, instantations are undone, and
   re-instantiations take place during repeated search.

   The entire search procedure is equivalent to a depth-first search in a
   tree defined by the clauses of the script and the instantiations of
   variables during the search.

   Prolog stops at first solution (if any), and displays any instantiated
   variables.

   All solutions can be generated. (typing ';' repeatedly, of 'a' once).

*/

/********** Examples *************/

/* A simple script about (heterosexual) couples: */

male(peter).
male(paul).
female(beatrice).
female(alice).
female(clepatra).

diffSex(X,Y) :- male(X),female(Y).

possibleCouple(X,Y) :-diffSex(X,Y), likes(X,Y), likes(Y,X).

likes(peter,alice).
likes(alice,peter).
likes(paul,alice).
likes(paul,beatrice).
likes(paul,clepatra).

/* Here are some questions asked, and the answers produced by gprolog using
the script above. See if you can follow the derivation procedure.

Q:

| ?- female(alice).

A:

yes

Q:

| ?- female(Y).              

A:

Y = beatrice ? ;

Y = alice ? ;

Y = clepatra

yes

Q:

| ?- likes(paul,X).

A:

X = alice ? ;

X = beatrice ? ;

X = clepatra

yes

Q:

| ?- likes(cleopatra,X).

A:

no

Q:

| ?- diffSex(X,Y).

A:

X = peter
Y = beatrice ? ;

X = peter
Y = alice ? ;

X = peter
Y = clepatra ? ;

X = paul
Y = beatrice ? ;

X = paul
Y = alice ? ;

X = paul
Y = clepatra

yes


Q:

| ?- possibleCouple(X,Y).

A:

X = peter
Y = alice ? ;

no

*/


/* Another script with a predicate myAppend(L1, L2, L3) which is true iff
the concatenation of L1 and L2 is equal to L3 */

myAppend([],L,L).
myAppend([X|L1],L2,[X|L3]) :- myAppend(L1,L2,L3).

/*

Q:

| ?- myAppend([1,2],[3],[1,2,3]).

A:

yes

Q:

| ?- myAppend([1,2],[3],[1,2,4]).

A:

no

Q:

| ?- myAppend([1,2],[3],L3).

A:

L3 = [1,2,3].

Q:

| ?- myAppend(L1,[3],[1,2,3]).

A: L1 = [1,2]

Q:

| ?- myAppend(L1,L2,[1,2,3]). 

A:

L1 = []
L2 = [1,2,3]

L1 = [1]
L2 = [2,3]

L1 = [1,2]
L2 = [3]

L1 = [1,2,3]
L2 = []

Q:

| ?- myAppend(L1,L2,L3).     

A:

L1 = []
L3 = L2 ? ;

L1 = [A]
L3 = [A|L2] ? ;

L1 = [A,B]
L3 = [A,B|L2] ? ;

L1 = [A,B,C]
L3 = [A,B,C|L2] ? ;

L1 = [A,B,C,D]
L3 = [A,B,C,D|L2] ? ;

L1 = [A,B,C,D,E]
L3 = [A,B,C,D,E|L2] ? ;

L1 = [A,B,C,D,E,F]
L3 = [A,B,C,D,E,F|L2] ? 

etc....

NOTE: As seen, predicates can be used as FUNCTIONS (with results created
through unification). The RETURN VALUE of the function is one of the
arguments. Actually, for many prolog predicates, the situation is as above
- ALL arguments may potentially serve as the return value.

*/


/* An example finding N factorial (the predicate factorial(N,F) is true if
(N is instantiated and) F is N factorial). */

factorial(0,1). 

factorial(N,F) :-  
        N>0, 
        N1 is N-1, 
        factorial(N1,F1), 
        F is N * F1.


/* Here, '>' is a built-in predicate which is written as an infix
operator. The arguments must instantiated to numerical values (or be
numerical constants) at the time satisfaction is attempted. Note that N-1
is a structure, not a number. The built-in predicate 'is' evaluates such a
structure (any structure which is interpretable as an arithmetic
expression), finding its numerical equivalent, and unifies the result with
the left argument to 'is'.

Q:

| ?- factorial(4,24).

A:

true

Q:

| ?- factorial(4,25).

A:

no

Q:

| ?- factorial(3,F).

A: 

F = 6

Q:

| ?- factorial(N,6).

A:

An error message, because variables taking part in '>' and 'is' are not
instantiated.

*/


/* Programming example: Towers of Hanoi */

hanoi(N) :- move(N,left,centre,right).

/* Arguments: Number of discs, source disc, distination disc, spare disc */

move(0,_,_,_).
move(N,A,B,C) :-
        N >= 1,
        M is N-1,
	move(M,A,C,B),
	inform(A,B),
	move(M,C,B,A).

inform(X,Y) :-
        write(X),write('->'),write(Y),nl.

/* 

Here, write/1 is a built-in predicate which succeeds once, and as a side
effect prints a representation of its argument on screen. The predicate
nl/0 similarly prints a newline.

 */


/* Test run:

| ?- hanoi(3).                  
left->centre
left->right
centre->right
left->centre
right->left
right->centre
left->centre

*/