/* COMMENTS:

   Comments in Prolog are written like this */

/* 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".

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

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

*/ 


/* 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 simple form of dynamic typing is used).

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

   - 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 (standard
   integer and float syntax)

   Examples:

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

     234, 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 name (its functor) and zero or more sub-terms (its
   arguments, 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.

   Examples:

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


   CLAUSES (in script) 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
   terms. When i = 0, the clause may be written

     S.

   and is called a FACT. For i >= 1, a clause is called a RULE.

   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.

*/
   

/*

   OPERATORS are (as usual) binary structures where the functor is written
   using infix notation.

   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
   syntactic sugar for the 

   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 different structure than 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.

   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).

   [H|T] will unify with [1,2,3,4]. H will be instantiated to 1, and T
   will be instantiated to [2,3,4].

   More list examples on p. 53.

*/


/* GOALS are boolean questions asked by the user (at prompt in
   gprolog). More precisely, they are terms 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 rules, the goal is substituted by the right-hand side 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, there will be a list of subgoals with
   commas (signifying AND) in between, and a "current" subgoal for which
   the clauses of the script are searched for unification. The subgoals to
   the left of the current one in the list have already been satisfied, the
   subgoals to the right have not yet. If the current subgoal becomes
   satisfied, its neighbor to the right will become the current subgoal. If
   the end of the list is reached, 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.
   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 somewhat similar to depth-first search
   (in a tree defined by the clauses of the script and the instantiations
   of variables during the search).

   The book gives a nice graphical explanation of the search procedure.

   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

*/


/* 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],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....

*/

/* 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. The same
applies to '-'. Note that N-1 is a structure, not a number. The
built-in predicate 'is' evaluates such a structure, 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.

*/