The list is a simple data structure widely used in non-numeric programming.
A list is a sequence of any number of items, such as ann, tennis, tom, skiing. Such a list can be written in Prolog as:
[ann,tennis,tom,skiing]
Lists can be empty or non-empty. Empty list is shown as [] atom. Non-empty list can be viewed as consisting of two things:
The first item called head,
The remaining part called tail.
Showing posts with label prolog. Show all posts
Showing posts with label prolog. Show all posts
Sunday, 18 January 2009
Unification Rules
Unification rules
A constant unifies only with itself.
Two structures unify if and only if they have the same functor and the same number of arguments, and the corresponding arguments unify recursively.
A variable unifies with anything.
Unification = Matching + Occurs check
What happens when we ask Prolog:
?- X = f(X).
Matching succeeds, unification fails
A constant unifies only with itself.
Two structures unify if and only if they have the same functor and the same number of arguments, and the corresponding arguments unify recursively.
A variable unifies with anything.
Unification = Matching + Occurs check
What happens when we ask Prolog:
?- X = f(X).
Matching succeeds, unification fails
Labels:
prolog,
rules,
Unification
Unification
How do we ask: ''what does Fred eat ?'‘
eats(fred,oranges).
How do we ask: “what Fred eats” ?
?- eats(fred,what).
But Prolog will say “no” to this question. The reason is that Prolog can't find the relation “eats(fred,what)” in its database.
In this case we have to use a variable which will be unified to match a relation given in the program. This process is known as unification.
Now that we know how to use a variables, we can ask the same question as before using the variable What instead of an atom.
?- eats(fred,What).
What=orange
Yes
In this case Prolog try to unify the variable with an atom. ''What=oranges'' means that the query is successfull when “what” is unified with oranges.
With the same program if we ask :
?- eats(Who,oranges).
Which means who eats oranges. To this query Prolog should answer :
?- eats(Who,oranges).
Who=fred
yes
eats(fred,oranges).
How do we ask: “what Fred eats” ?
?- eats(fred,what).
But Prolog will say “no” to this question. The reason is that Prolog can't find the relation “eats(fred,what)” in its database.
In this case we have to use a variable which will be unified to match a relation given in the program. This process is known as unification.
Now that we know how to use a variables, we can ask the same question as before using the variable What instead of an atom.
?- eats(fred,What).
What=orange
Yes
In this case Prolog try to unify the variable with an atom. ''What=oranges'' means that the query is successfull when “what” is unified with oranges.
With the same program if we ask :
?- eats(Who,oranges).
Which means who eats oranges. To this query Prolog should answer :
?- eats(Who,oranges).
Who=fred
yes
Labels:
program,
prolog,
Unification
Order of Clauses and Goals: Infinite Loops
Consider the following clause:
P:-p.
This means ‘p is true if p is true’. This is declaratively perfectly correct, but procedurally is quite useless.
?-p.
Using the clause above, the goal p is replaced by the same goal p; this will be in turn replaced by p, etc. Prolog will enter an infinite loop not noticing that no progress is being made.
Any differences in order of the clauses may cause finite loops. For example you can’t move if you don’t get up.
Different variation of clauses produces different answers.
The predecessor procedure consists of two clauses, and one of them has two goals in the body. There are,therefore, 4 variations of this program, which have the same declarative meaning, can be obtained by:
Swapping both clauses, and
Swapping the goals for each order of clause.
The Original version:
pred1(X, Z) :- parent(X, Z).
pred1(X, Z) :- parent(X, Y), pred1( Y, Z).
Variation a:
pred2(X, Z) :- parent(X, Y), pred2( Y, Z).
pred2(X, Z) :- parent(X, Z).
Variation b:
pred3(X, Z) :- parent(X, Z).
pred3(X, Z) :- pred3( X, Y), parent(Y, Z).
Variation c:
pred4(X, Z) :- pred4( X, Y), parent(Y, Z).
pred4(X, Z) :- parent(X, Z).
Let’s see what happens if we ask whether Tom is a predecessor of Pat using the four variations of the predecessor relation:
?- pred1(tom, pat).
yes
?- pred2(tom, pat).
yes
?- pred3(tom, pat).
yes
?- pred4(tom, pat).
Prolog can not find the answer and this is manifested on the terminal by a Prolog message such as “More core needed” or “Stack Overflow”.
P:-p.
This means ‘p is true if p is true’. This is declaratively perfectly correct, but procedurally is quite useless.
?-p.
Using the clause above, the goal p is replaced by the same goal p; this will be in turn replaced by p, etc. Prolog will enter an infinite loop not noticing that no progress is being made.
Any differences in order of the clauses may cause finite loops. For example you can’t move if you don’t get up.
Different variation of clauses produces different answers.
The predecessor procedure consists of two clauses, and one of them has two goals in the body. There are,therefore, 4 variations of this program, which have the same declarative meaning, can be obtained by:
Swapping both clauses, and
Swapping the goals for each order of clause.
The Original version:
pred1(X, Z) :- parent(X, Z).
pred1(X, Z) :- parent(X, Y), pred1( Y, Z).
Variation a:
pred2(X, Z) :- parent(X, Y), pred2( Y, Z).
pred2(X, Z) :- parent(X, Z).
Variation b:
pred3(X, Z) :- parent(X, Z).
pred3(X, Z) :- pred3( X, Y), parent(Y, Z).
Variation c:
pred4(X, Z) :- pred4( X, Y), parent(Y, Z).
pred4(X, Z) :- parent(X, Z).
Let’s see what happens if we ask whether Tom is a predecessor of Pat using the four variations of the predecessor relation:
?- pred1(tom, pat).
yes
?- pred2(tom, pat).
yes
?- pred3(tom, pat).
yes
?- pred4(tom, pat).
Prolog can not find the answer and this is manifested on the terminal by a Prolog message such as “More core needed” or “Stack Overflow”.
Procedural Meaning
The procedural meaning specifies how Prolog answers questions.
Input: a program and a goal list.
Output: a success/failure indicator and an instantiation of variables.
The meaning of the two output results is as follows:
The success/failure indicator is ‘yes’ if the goals are satisfiable and ‘no’ otherwise.
An instantiation of variables is only produced in the case of a successful termination; in the case of failure there is no instantiation.
Input: a program and a goal list.
Output: a success/failure indicator and an instantiation of variables.
The meaning of the two output results is as follows:
The success/failure indicator is ‘yes’ if the goals are satisfiable and ‘no’ otherwise.
An instantiation of variables is only produced in the case of a successful termination; in the case of failure there is no instantiation.
Labels:
Meaning,
Procedural,
prolog
Declerative Meaning
Declarative reading of the clause “P:-Q,R” are:
P is true if Q and R are true.
From Q and R follows P.
Procedural readings of this clause are:
To solve the problem P, first solve the subproblem Q and then R.
To satisfy P, satisfy Q and then R.
Note that ‘,’ character indicates AND operator.
Note that ‘;’ character indicates OR operator.
AND operator has a higher priority then the OR operator.
“P :- Q, R; S, T, U.” and “P :- (Q, R); (S, T, U).” clauses gives the same results.
Same clauses can be written as:
P :- Q, R.
P :- S, T, U.
P is true if Q and R are true.
From Q and R follows P.
Procedural readings of this clause are:
To solve the problem P, first solve the subproblem Q and then R.
To satisfy P, satisfy Q and then R.
Note that ‘,’ character indicates AND operator.
Note that ‘;’ character indicates OR operator.
AND operator has a higher priority then the OR operator.
“P :- Q, R; S, T, U.” and “P :- (Q, R); (S, T, U).” clauses gives the same results.
Same clauses can be written as:
P :- Q, R.
P :- S, T, U.
Labels:
Declerative,
Meaning,
prolog
Matching
Matching is operation on terms (structures).
Given two terms, they match if:
They are identical, or
They can be made identical by properly instantiating the variables in both terms.
Matching two dates:
date( D1, M1, 2006) = date( D2, june, Y2).
This causes the variables to be instantianted as:
D1 = D2
M1 = june
Y2 = 2006
The terms below don’t match:
date( D, M, 2008) = date( D1,M1, 2000).
In order to check whether the given dates are matching or not in Prolog we use ‘=‘ operator.
?-date( D, M, 2008) = date( D1,May, Y1).
Example:
?- date(D, M, 2001) = date(D1, may, Y1),
date(D, M, 2001) = date(15, M, Y).
D=15, D1= 15, M= may, Y1 = 2001, Y= 2001
Example:
?- date( D1, M1, 2006) = date( D2, june, Y2),
date( D1, M1, 2006) = date( 17, M3, Y3).
D1 = 17, D2 = 17, M1 = june, M3 = june,Y2 = 2006, Y3 = 2006
Matching succeeds or fails; if succeeds then it results in the most general instantiation
To decide whether terms S and T match:
If S and T are constants then they match only if they are identical
If S is a variable and T is anything then matching succeeds, S is instantiated to T and vice versa.
If S and T are structures then they match only if:
S and T have the same principal functor ,and
All their corresponding components match.
Matching succeeds or fails; if succeeds then it results in the most general instantiation
To decide whether terms S and T match:
If S and T are constants then they match only if they are identical
If S is a variable and T is anything then matching succeeds, S is instantiated to T and vice versa.
If S and T are structures then they match only if:
S and T have the same principal functor ,and
All their corresponding components match.
Given two terms, they match if:
They are identical, or
They can be made identical by properly instantiating the variables in both terms.
Matching two dates:
date( D1, M1, 2006) = date( D2, june, Y2).
This causes the variables to be instantianted as:
D1 = D2
M1 = june
Y2 = 2006
The terms below don’t match:
date( D, M, 2008) = date( D1,M1, 2000).
In order to check whether the given dates are matching or not in Prolog we use ‘=‘ operator.
?-date( D, M, 2008) = date( D1,May, Y1).
Example:
?- date(D, M, 2001) = date(D1, may, Y1),
date(D, M, 2001) = date(15, M, Y).
D=15, D1= 15, M= may, Y1 = 2001, Y= 2001
Example:
?- date( D1, M1, 2006) = date( D2, june, Y2),
date( D1, M1, 2006) = date( 17, M3, Y3).
D1 = 17, D2 = 17, M1 = june, M3 = june,Y2 = 2006, Y3 = 2006
Matching succeeds or fails; if succeeds then it results in the most general instantiation
To decide whether terms S and T match:
If S and T are constants then they match only if they are identical
If S is a variable and T is anything then matching succeeds, S is instantiated to T and vice versa.
If S and T are structures then they match only if:
S and T have the same principal functor ,and
All their corresponding components match.
Matching succeeds or fails; if succeeds then it results in the most general instantiation
To decide whether terms S and T match:
If S and T are constants then they match only if they are identical
If S is a variable and T is anything then matching succeeds, S is instantiated to T and vice versa.
If S and T are structures then they match only if:
S and T have the same principal functor ,and
All their corresponding components match.
Structures
Structure objects are objects that have several components. The components themselves can be structures.
date(,,).
Structures can be presented using simple geometric objects. The root of the tree is the functor and the leafs are components.
date(
Structures can be presented using simple geometric objects. The root of the tree is the functor and the leafs are components.
Labels:
prolog,
structures
Variables
Variables are string of letters, digits and underscore character. They start with an upper case letter or an underscore character:
X
X2
X_Y
_x123
_12
Variables without a name are called anonymous variables, which is written as a single underscore character.
hasachild(X):-parent(X,_).
Each time a single underscore character occurs in a clause it represents a new anonymous variable.
“Somebody_has_a_child:-parent(_,_).” is equal to,
“Somebody_has_a_child:-parent(X,Y).” but not equal to,
“Somebody_has_a_child:-parent(X,X).”
Is Ali have any children and if it is so what are their names?
?- parent(ali,Y).
Is Ali have any children?
?-parent(ali,_).
X
X2
X_Y
_x123
_12
Variables without a name are called anonymous variables, which is written as a single underscore character.
hasachild(X):-parent(X,_).
Each time a single underscore character occurs in a clause it represents a new anonymous variable.
“Somebody_has_a_child:-parent(_,_).” is equal to,
“Somebody_has_a_child:-parent(X,Y).” but not equal to,
“Somebody_has_a_child:-parent(X,X).”
Is Ali have any children and if it is so what are their names?
?- parent(ali,Y).
Is Ali have any children?
?-parent(ali,_).
Atoms and Numbers
Atoms and variable examples:
Upper case letters: A,B,…,Z
Lower case letters: a,b,…,z
Digits: 0,1,…,9
Special characters: +,-,<,>,/,*,=,:,.,_,~
Atoms can be constructed in three ways:
String of letters,digits and the underscore character starting with a lower case letter:
anna
x25
x_
x__y
Strings of special characters:
…
.:.
::=
String of characters enclosed in single quotes:
‘Tom’
‘South_America’
‘Sarah Jones’
Numbers used in Prolog include integer numbers and real numbers.
1
-97
-0.035
Using real numbers may cause numerical errors due to rounding, because of this they are not used very often.
Error example in real numbers:
sum(X,Y,Z):-Z is X+Y.
?- sum(2,0.3,C).
C = 2.3 ;
No
?- sum(200,0.0003,C).
C = 200.0 ;
No
The evaluation of the expression “10000+0.0001-10000 “ may result in 0 instead of the correct result 0.0001
Upper case letters: A,B,…,Z
Lower case letters: a,b,…,z
Digits: 0,1,…,9
Special characters: +,-,<,>,/,*,=,:,.,_,~
Atoms can be constructed in three ways:
String of letters,digits and the underscore character starting with a lower case letter:
anna
x25
x_
x__y
Strings of special characters:
…
.:.
::=
String of characters enclosed in single quotes:
‘Tom’
‘South_America’
‘Sarah Jones’
Numbers used in Prolog include integer numbers and real numbers.
1
-97
-0.035
Using real numbers may cause numerical errors due to rounding, because of this they are not used very often.
Error example in real numbers:
sum(X,Y,Z):-Z is X+Y.
?- sum(2,0.3,C).
C = 2.3 ;
No
?- sum(200,0.0003,C).
C = 200.0 ;
No
The evaluation of the expression “10000+0.0001-10000 “ may result in 0 instead of the correct result 0.0001
First Program
Rules:
In order to work, people must be full and delighted.
work(X) :- delighted(X), full(X).
In order to be full, people must eat something.
full(X) :- ate(X).
In order to be delighted, people must sleep and have fun.
delighted(X) :- slept(X), fun(X).
Facts:
Mustafa ate.
ate(mustafa).
Mustafa slept.
slept(mustafa).
Mustafa had fun.
fun(mustafa).
Query:
Can Mustafa work?
Facts:
eats(fred,oranges).
eats(tony,apple).
eats(john,apple).
Queries:
?- eats(fred,oranges). /* yes
?- eats(john,apple). /*yes
?- eats(mike,apple). /*no
In order to work, people must be full and delighted.
work(X) :- delighted(X), full(X).
In order to be full, people must eat something.
full(X) :- ate(X).
In order to be delighted, people must sleep and have fun.
delighted(X) :- slept(X), fun(X).
Facts:
Mustafa ate.
ate(mustafa).
Mustafa slept.
slept(mustafa).
Mustafa had fun.
fun(mustafa).
Query:
Can Mustafa work?
Facts:
eats(fred,oranges).
eats(tony,apple).
eats(john,apple).
Queries:
?- eats(fred,oranges). /* yes
?- eats(john,apple). /*yes
?- eats(mike,apple). /*no
Atoms
likes(john,mary).
In the above fact john and mary are two atomes.
Atoms are usally made from letters and digits with lowercase characters.
Atoms can also be legally made from symbols. The followings are legal atoms :
atoms
hello
zz42
two_words
====>
'two words'
The followings are not legal atoms :
Hello
4hello
_Hello
two words
two-word
The fact likes(john,mary). say that there is a relation between john and mary. It can be read as either john likes mary or mary likes john.
In the above fact john and mary are two atomes.
Atoms are usally made from letters and digits with lowercase characters.
Atoms can also be legally made from symbols. The followings are legal atoms :
atoms
hello
zz42
two_words
====>
'two words'
The followings are not legal atoms :
Hello
4hello
_Hello
two words
two-word
The fact likes(john,mary). say that there is a relation between john and mary. It can be read as either john likes mary or mary likes john.
Labels:
atoms,
characters,
Problems,
prolog,
words
Rules
Prolog clauses such as:
“offspring(Y,X):-parent(X,Y).” are called rules.
There is difference between facts and rules.
Fact syntax and the meaning:
parent(tom,liz).
Rule has two parts a condition (head) and a conclusion part (body).
“offspring(Y,X):-parent(X,Y).” are called rules.
There is difference between facts and rules.
Fact syntax and the meaning:
parent(tom,liz).
Rule has two parts a condition (head) and a conclusion part (body).
Facts with Arguments
A general fact model with arguments:
relation(,,...., ).
The arguments can be any legal Prolog term.
The basic Prolog terms are an integer, an atom, a variable or a structure. Various Prolog implementation enhance this basic list with other data types, such as floating point numbers, or strings.
relation(
The arguments can be any legal Prolog term.
The basic Prolog terms are an integer, an atom, a variable or a structure. Various Prolog implementation enhance this basic list with other data types, such as floating point numbers, or strings.
Simple Facts
In Prolog we can make some statements by using facts. Facts either consist of a particular item or a relation between items. For example we can represent the fact that it is sunny by writing the program :
sunny.
We can now ask a query of Prolog by asking
?- sunny.
?- is the Prolog prompt. To this query, Prolog will answer yes. sunny is true because (from above) Prolog matches it in its database of facts.
Facts have some simple rules of syntax.
Facts should always begin with a lowercase letter and end with a full stop.
The facts themselves can consist of any letter or number combination, as well as the underscore _ character.
However, names containing the characters -,+,*,/, or other mathematical operators should be avoided.
sunny.
We can now ask a query of Prolog by asking
?- sunny.
?- is the Prolog prompt. To this query, Prolog will answer yes. sunny is true because (from above) Prolog matches it in its database of facts.
Facts have some simple rules of syntax.
Facts should always begin with a lowercase letter and end with a full stop.
The facts themselves can consist of any letter or number combination, as well as the underscore _ character.
However, names containing the characters -,+,*,/, or other mathematical operators should be avoided.
SWI-Prolog
SWI-Prolog is an open source implementation of the programming language Prolog, commonly used for teaching and semantic web applications, which is designed by Jan Wielemaker in 1987
SWI-Prolog runs on Unix, Windows, and Macintosh platforms.
SWI-Prolog can be downloaded from “http://www.swi-prolog.org”.
The program, sometimes called database is a text file (*.pl or *.pro) that contain the facts and rules that will be used by the user of the program.
First you have to create a facts and rules file which can be done by using notepad.
It contains all the relations that make this program.
When you launch a program you are in query modequery mode.
This mode is represented by the sign ? - at the begining of the line.
In query mode you ask questions about relations described in the program.
You can run the facts and rules file by double clicking, after running SWI-Prolog, by using “Consult” menu via “File” menu or typing the file name after ?- sign.
After running the file, all rules and facts are stored in prolog.
You can now use queries.
SWI-Prolog runs on Unix, Windows, and Macintosh platforms.
SWI-Prolog can be downloaded from “http://www.swi-prolog.org”.
The program, sometimes called database is a text file (*.pl or *.pro) that contain the facts and rules that will be used by the user of the program.
First you have to create a facts and rules file which can be done by using notepad.
It contains all the relations that make this program.
When you launch a program you are in query modequery mode.
This mode is represented by the sign ? - at the begining of the line.
In query mode you ask questions about relations described in the program.
You can run the facts and rules file by double clicking, after running SWI-Prolog, by using “Consult” menu via “File” menu or typing the file name after ?- sign.
After running the file, all rules and facts are stored in prolog.
You can now use queries.
What is Prolog?
Prolog is a logic programming language, which has an association with artificial intelligence and computational linguistics.
It is designed by Alain Colmerauer who is a French computer scientist in 1972.
Prolog’s major implementations: BProlog, ECLiPSe, Ciao Prolog, GNU Prolog, Quintus, SICStus, Strawberry, SWI-Prolog, YAP-Prolog, tuProlog
Prolog’s dialects: ISO Prolog, Edinburgh Prolog
Having its roots in formal logic, and unlike many other programming languages, Prolog is declarative.
The program logic is expressed in terms of relations, and execution is triggered by running queries over these relations.
Relations and queries are constructed using Prolog's single data type, the term.
Relations are defined by clauses.
Clauses are statements about what is true about a problem, instead of instructions how to accomplish the solution, the Prolog system uses the clauses to work out how to accomplish the solution by searching through the space of possible solutions.
It is designed by Alain Colmerauer who is a French computer scientist in 1972.
Prolog’s major implementations: BProlog, ECLiPSe, Ciao Prolog, GNU Prolog, Quintus, SICStus, Strawberry, SWI-Prolog, YAP-Prolog, tuProlog
Prolog’s dialects: ISO Prolog, Edinburgh Prolog
Having its roots in formal logic, and unlike many other programming languages, Prolog is declarative.
The program logic is expressed in terms of relations, and execution is triggered by running queries over these relations.
Relations and queries are constructed using Prolog's single data type, the term.
Relations are defined by clauses.
Clauses are statements about what is true about a problem, instead of instructions how to accomplish the solution, the Prolog system uses the clauses to work out how to accomplish the solution by searching through the space of possible solutions.
Subscribe to:
Posts (Atom)