prolog

Prolog

Prolog-machine consists of two components:

d a t a b a s e

i n t e r p r e t e r

the program (Horn clauses and directives) is entered into the database. then interpreter loads this DB and starts REPL

the task of the programmer is simply to describe problems

the programmer should write down a declarative specification which describes the situation of interest. the programmer shouldn't have to tell the computer what to do. to get information, s/he simply asks the questions - it's up to the logic programming system to figure out how to get the answer

comments

any string starting with % is a comment. there are no multiline comments in Prolog

program

terms

constants
variables
functors

constants

in PROLOG two types of constants are distinguished:

numeric constants, called numbers
symbolic constants, called atoms

an atom is either:

a string of characters made up of upper-case letters, lower-case letters, digits, and the underscore character, that begins with a lower-case letter

for example: name, big_ban, m_2 are atoms

an arbitrary sequence of character enclosed in single quotes

for example 'Arthur', 'The Lord', 'Five_Dollar_Shake', ' ' are atoms

a string of special characters

for example: @= ====> ; :- are all atoms

variables

a variable is a string of upper-case letters, lower-case letters, digits and underscore characters that starts either with an upper-case letter or with underscore. X, Var, Y_24, List2, _head are all PROLOG variables

the variable _ (that is, a single underscore character) is called the anonymous variable

a variable has for its lexical scope the clause in which it occurs - outside that clause, the variable has no influence: PROLOG does NOT have global variables

functors

functor in Prolog is construction p(t1, t2, ..., tn) where

p - a predicate with with arity n
t1, t2, ..., tn - terms

the functor is defined by name (predicate) and arity (number of terms)

the terms of functor are called arguments. the arguments of a functor are enclosed in parentheses, and separated by commas. they can be

atom
variable
functor
list

tuple's matching:

  | ?- (_,_,_,X) = ([a, b], [1, 2], [c], d).
  X = d
  yes

logic

conclusion

Horn clause p :- p1, p2, ..., pn. is interpreted as "p is true if p1 AND p2 AND ... AND pn are true"

Horn clause p :- p1; p2; ...; pn. is interpreted as "p is true if p1 OR p2 OR ... OR pn are true"

p is called conclusion

if a clause contains conditions (that is in clause n ≠ 0), it is called a rule

if there are no conditions (that is in clause n = 0), the clause is said to be a fact
in this case functor is used: p(p1,p2,...,pn).

if the conclusion p is missing then the clause is considered to be a query. in this case the atom :- is replaced by the atom ?-

set of such clauses is viewed as a entire program

procedure

each clause in the program is seen as a procedure
the conclusion p is the procedure heading (composed of a name and an arity)
conditions p1, ..., pn are taken as the body of the procedure
all clauses having the same predicate in their conclusion are viewed as various entries to the same procedure
a clause without any conclusion (a query) acts as the main program

interpreter tries to derive an answer to the query using facts and rules stored in the database. doing so interpreter employs two techniques: matching and backtracking

rules extend the capabilities of a logic program. they are what give Prolog the ability to pursue its decision-making process. the following program contains two rules for temperature:

'it is sunny'.
'it is summer'.
'it is hot'  :- 'it is summer', 'it is sunny'.
'it is cold' :- 'it is winter'; 'it is snowing'.

the first rule is read as follows: "It is hot if it is summer AND it is sunny". the second rule is read as follows: "It is cold if it is winter OR it is snowing". the query:

?- 'it is hot'.
yes

is answered in the affirmative since both 'it is summer' and 'it is sunny' are in the data base while a query

?- 'it is cold'.
no

produces a negative response

listing multiple rules with the same head is a way of expressing logical disjunction (that is, it is a way of saying OR)

fact1(a) :- true .
fact2(b) :- true .

rule01(X) :-
  fact1 .
rule01(X) :-
  fact2 .

there is another way of expressing disjunction. you could replace the pair of rules by the single rule

fact1(a) :- true .
fact2(b) :- true .

rule01(X) :-
  fact1 ;
  fact2 .

matching

to answer a query, the interpreter starts with the first condition in the query clause, taking it as a procedure call. the database is subsequently searched for a suitable entry to the called procedure

the search starts with the first clause in the database, and continues until a clause has been found which has a conclusion that can be matched with the procedure call

a match is obtained, if there exists a substitution for the variables occurring both in the conclusion and in the procedure call, such that the two become (syntactically) equal after the substitution has been applied to them

such a match exists if

the conclusion and the procedure call contain the same predicate, and
the terms in corresponding argument positions after substitution of the variables are equal

backtracking

if, after the creation of a number of instantiations and matches, the system does not succeed in obtaining the next match, it systematically tries alternatives for the instantiations and matches arrived at so far

interpreter examines clauses in the order in which they have been specifed in the database. the order in which clauses have been specifed in the database may be important. this is a substantial diference between a logic program and a PROLOG program: whereas logic programs are purely declarative in nature, PROLOG programs tend to be much more procedural

u can cut backtracking by using ! . basically, it tells Prolog not to backtrack and stop to look for alternative solutions for the goal

max(A,B,B) :- A < B, !.
max(A,B,A).

but this is kind of "GOTO" in logic domain - so use it carefully

negation

the only method that Prolog can use to tell if a proposition is false is to try to prove it (from the facts and rules that it has been told about), and then if this attempt fails, it concludes that the proposition is false. an obvious problem is that Prolog may not have been told some critical fact or rule, so that it will not be able to prove the proposition. this is sometimes referred to as the closed-world assumption. a less obvious problem is that it may take a very long time to determine that the proposition cannot be proven. in certain cases - infinite time

negation in Prolog is represented using the symbol \+ , which is supposed to be a mnemonic for not provable with the \ standing for not and the + for provable

    ?- \+ (2 = 4).
    yes.

REPL

you start REPL just by:

$> gprolog
GNU Prolog 1.4.5 (64 bits)
Compiled Jul 14 2018, 13:34:14 with gcc
By Daniel Diaz
Copyright (C) 1999-2019 Daniel Diaz
| ?-

the next two in-build predicates tell PROLOG to consult the file "kb.pl", and load the contents as its new knowledge base. you can use

| ?- [kb].
compiling /home/Prolog/kb.pl for byte code...
/home/../kb.pl compiled, 7 lines read - 586 bytes written, 15 ms
yes

or you can use built-in predicate consult/1

| ?- consult('kb.pl').
compiling /home/Prolog/kb.pl for byte code...
/home/../kb.pl compiled, 7 lines read - 586 bytes written, 15 ms
yes

the listing/0 command is a special in-built PROLOG predicate that instructs PROLOG to display the contents of the current knowledge base

| ?- listing.
% file: /home/../kb.pl

man(noi).
man(kain).
man(abel).

father(noi, kain).
father(noi, abel).

yes

a yes means that the information in the data base is consistent with the subject of the query. another way to express this is that the program is capable of proving the query true with the available information in the data base. if a fact is not deducible from the data base the system replys with a no, which indicates that based on the information available (the closed world assumption) the fact is not deducible

to exit from REPL use in-built Prolog predicate halt:

| ?- halt.
$>

or just use Ctrl-D

using Ctrl-C u get additional menu for REPL

example

%%%  file  kb.pl

man(noi).
man(kain).
man(abel).

father(noi, kain).
father(noi, abel).

$> gProlog --consult-file kb.pl
GNU Prolog 1.4.4 (32 bits)...
| ?- man(X).
X = noi ? ;
X = kain ? ;
X = abel
yes
| ?- father(X,abel).
X = noi
yes
| ?- father(noi,X).
X = kain ? ;
X = abel
yes
| ?-

recursion

when you write a recursive predicate, it should always have at least two clauses:

a base clause (the clause that stops the recursion at some point), and
one that contains the recursion

if you don't do this, Prolog can spiral off into an unending sequence of useless computations

recursive rules are really important. they enable to pack an enormous amount of information into a compact form and to define predicates in a natural way. most of the work you will do as a Prolog programmer will involve writing recursive rules

numeral(0).
numeral(succ(X)) :-
   numeral(X).

add(0, Y, Y).
add(succ(X), Y, succ(Z)) :-
   add(X, Y, Z).

lists

there is a special notation for lists in PROLOG: [ ]. lists in Prolog are geterogenious

| ?- X = [alfa, beta, 5, Y, [gamma, 12], man(iosif)].
yes

a in-built operator | which can be used to decompose a list into its head and tail

| ?- [Head | Tail] = [alfa, beta, delta, gamma].
Head = alfa
Tail = [beta,delta,gamma]
yes

a in-built predicate length/2

| ?- X = [1,2,3,4], length(X,N).

N = 4
X = [1,2,3,4]

yes

a in-built predicate member/2

| ?- member(X, [alfa, beta, delta, gamma]).
X = alfa;
X = beta;
X = delta;
X = gamma;
yes

a in-built predicate append/3

| ?- X = [1,2,3], append(X,[25,26],Y), write(Y).
[1,2,3,25,26]

X = [1,2,3]
Y = [1,2,3,25,26]

yes

a in-built predicate reverse/2

| ?- reverse([1,2,3],X).
X = [3,2,1]
yes

a in-built predicate sort/2

| ?- sort([1,3,2],X).
X = [1,2,3]
yes

comparison

for any terms:
T1 = T2
true if terms are equal
T1 \= T2
true if terms are not equal

true if X matches the value of the arithmetic expression Expr:
X is Expr

true if the values of the arithmetic expressions Expr1 and Expr2 are equal:
Expr1 =:= Expr2
the complementary relation:
Expr1 =\= Expr2

true if terms are identical:
Term1 == Term2
that is, they have exactly the same structure and all the corresponding components are the same. the complementary relation:
Term1 \== Term2

| ?- X = myatom, read(Y), X = Y.
myatom.
X = myatom
Y = myatom
yes
| ?- X = myatom, read(Y), X = Y.
youratom.
no
| ?-

T1 < T2

T1 =< T2

T1 > T2

T1 >= T2

arithmetic

there are built-in procedures for these ops: + - * / mod/2

calculation triggers by built-in operator is and also by comparison operators

| ?- 8 is 6 + 2.
yes
| ?- 12 is 6 * 2.
yes
| ?- -2 is 6 - 8.
yes
| ?- 3 is 6 / 2.
yes
| ?-  R is mod(7, 2), write(R).
1
R = 1
yes

there is also predicate is/2 which is equivalent to op is

| ?- is(X,2 + 3).
is(X,2 + 3).
X = 5
yes

% file ddd.pl

add_3_and_double :- read(X), Y is (X + 3) * 2, write(Y).

len([], 0).
len([_ | T], N) :- len(T, X), N is X + 1.

| ?- consult('ddd.pl').
compiling /home/../ddd.pl for byte code...
/home/../ddd.pl compiled, 2 lines read - 607 bytes written, 14 ms
yes
| ?- add_3_and_double.
23.
52
yes
| ?- X = [1, a, 5], len(X, Y), write(Y).
3
X = [1,a,5]
Y = 3
yes
| ?- is(X, +(3, 2)).
X = 5
yes

%  file eee.pl

accLen([], A) :- write(A).
accLen([_|T], A) :-  ANew is A + 1, accLen(T, ANew).

leng(List) :- accLen(List,0).

accMax([H|T],A,Max) :- H > A,  accMax(T,H,Max).
accMax([H|T],A,Max) :- H =< A, accMax(T,A,Max).
accMax([],A,A).

max(List,Max) :- List = [H|_], accMax(List,H,Max).

| ?- [eee].
compiling /home/../eee.pl for byte code...
/home/../eee.pl compiled, 5 lines read - 865 bytes written, 14 ms

yes
| ?- X = [1,a,5,man(juda)], accLen(X,0).
4
X = [1,a,5,man(juda)]
yes
| ?- X = [1,a,5,man(juda)], leng(X).
4
X = [1,a,5,man(juda)]
yes
| ?- max([4,1,52,-73,6],X).
X = 52 ?
yes

database dynamic changing

asserta(Clause).
converts the term Clause to a clause and then adds it to the current internal database. the clause is inserted before the first clause of the predicate. if the predicated is undefined it is created

assertz(Clause).
converts the term Clause to a clause and then adds it to the current internal database. the clause is inserted after the last clause of the predicate. if the predicated is undefined it is created

retract(Clause).
erases the first clause of the database that unifies with Clause. removing all clauses of a procedure does not erase the procedure definition. to achieve this use abolish/1

abolish(Pred/Arity).
removes from the database the procedure whose predicate indicator is Pred and arity is equial to Arity

IF ... THEN ... ELSE

p(t1,t2,...tn) -> yesway(tc1,...) ; noway(te1,...) .

example:

pass(auckland, hamilton, bus).
pass(bangkok, auckland, plane).
pass(frankfurt, bangkok, plane).
pass(frankfurt, singapore, plane).
pass(hamilton, raglan, bus).
pass(losAngeles, auckland, plane).
pass(metz, frankfurt, train).
pass(metz, paris, train).
pass(paris, losAngeles, plane).
pass(saarbruecken, frankfurt, train).
pass(saarbruecken, paris, train).
pass(valmont, metz, bus).
pass(valmont, saarbruecken, bus).

travel(X,Y) :-
  pass(X, Y, T) -> 
    write([T, X, Y]), ! , nl ;
  pass(X, Z, T1) ,
  pass(Z, Y, T2) -> 
    write([T1, X, Z, T2, Z, Y]), !, nl ;
  pass(X,  Z1, T1) ,
  pass(Z1, Z2, T2) ,
  pass(Z2,  Y, T3) -> 
    write([T1, X, Z1, T2, Z1, Z2, T3, Z2, Y]), !, nl ;
  pass(X,  Z1,  T1) ,
  pass(Z1, Z2,  T2) ,
  pass(Z2, Z3, T3) ,
  pass(Z3,  Y,  T4) -> 
    write([T1, X, Z1, T2, Z1, Z2, T3, Z2, Z3, T4, Z3, Y]), !, nl .

queries

findall(Object, Goal, List).
produces a List of all Object that satisfy the Goal

/*    file mydb.pl    */

tab1('Aaa').
tab1('Bbb').
tab1('Ccc').

now:

| ?- consult(mydb).
compiling /home/.../Prolog/mydb.pl for byte code...
/home/.../Prolog/mydb.pl compiled, 3 lines read - 350 bytes written, 12 ms
yes
| ?- findall(X,tab1(X),L), length(L,N).
L = ['Aaa','Bbb','Ccc']
N = 3
yes
| ?-

example

in source file 'levi.pl':

%% hasband clan, wife clan, offspring clan
aliance(a , b , c).
aliance(b , c , d).
aliance(c , d , a).
aliance(d , a , b).

testM(X) :-               %% male - grandpa and grandchild
    aliance(X, _, Y),
    aliance(Y, _, not(X)), !.
    
testF(X) :-               %% female - grandgrandgrandma and grandgrandgrandchild
    aliance(_, X, Y),
    aliance(_, Y, Z),
    aliance(_, Z, K),
    aliance(_, K, not(X)), !.

and now in Prolog repl:

| ?- [levi].
[levi].
compiling /home/Prolog/levi.pl for byte code...
/home/Prolog/levi.pl compiled, 32 lines read - 3311 bytes written, 13 ms

yes
| ?- testM(X).
testM(X).

no
| ?- testF(X).
testF(X).

no