Prolog
The syntax will look very familiar now that you’ve seen clause form, but it embodies most of what you can say in FOL.
many books and articles on Prolog, if you’re interested in doing more than you see here – Also Comp 3440
Prolog is available free for most platforms – sbprolog for Unix (just type ‘prolog’), amzi prolog for Windows or Linux; open prolog for the mac, and swi-prolog (www.swi-prolog.org) for all platforms
Prolog
Prolog
We’re going to do Prolog in two parts: basic, then more advanced, with some material separating them
Programming in Logic – based on first-order logic Illustrates the computational manipulation of
The motivation for seeing some prolog now is so that you can see the idea of symbol manipulation in practice while you’re doing an assignment on paper, and connect all this up
symbols
However, there is still a lot to see as far as basic
AI goes, and I don’t want you to lose sight of it
and think that logical representation is all there is to it! 3
We’re looking at Prolog, because it lets you get to interesting things faster – it includes search and unification algorithms, for example, so that you don’t have to write them
© 2020 J.E. Anderson
than building manipulation facilities 4 © 2020 J.E. Anderson
Implementing Logical Systems
Prolog is the most well-known logic-based programming language
We write files of logic code in Prolog, then consult them and query the logical system. Prolog then proves the query,returningvariablesboundduringthisprocess. 2
You could do all of this in other symbol manipulation languages like LISP
You can concentrate on defining knowledge rather
© 2020 J.E. Anderson
Prolog Programming
Knowledge Rep. In Prolog
Prolog is a complete programming language that follows the logical paradigm of computation [as opposed to procedural (e.g. C) or functional (e.g. Lisp)]
The facts that are known about a problem domain are defined using predicates:
There will be equivalents in Prolog for anything you can do procedurally or functionally – they may not be recognizable to you from current experience though!
male(bill). female(sally). parent(bill, sally).
Take 3440 for a much broader look at how we do what you would think of as procedural coding using a language like Prolog
The order of the objects in a predicate obviously has meaning and must be used consistently
Predicates
Predicates
A1 is intended to show you that the selection of an appropriate set of predicates is not trivial
Much more suitable: father(bill, sally). mother(jane, sally).
a well organized set of predicates can make problem solving much easier than if a poorly organized set of predicates is defined
…and the addition of another fact that says that a parent in general can be either a mother or a father.
e.g. parent(bill, jane, sally). ????
It is impossible to define all possible predicates for all combinations of objects in a complex system – that’s why it’s a model!
bill is the father and jane is the mother of sally? Trying to say too much in one predicate makes it much less extendable (and even less useful in many cases)
Obviously much of our knowledge is in the form of more generally applicable rules, such as the parent rule we mentioned above
Remember to focus on generality when doing
prolog assignments!
78 © 2020 J.E. Anderson © 2020 J.E. Anderson
5 © 2020 J.E. Anderson
6 © 2020 J.E. Anderson
A period ends a statement
Predicates are analogous to relations in relational database systems
Rules in Prolog
Prolog Rules
When you think of the term rule, you usually think of an implication: if we have X, then we have Y
father(X,Y) :- male(X), parent(X,Y).
No different in Prolog – we define rules using implication that make generic statements about the objects in a system
All variables used in Prolog statements are assumed to be universally quantified (all part of clause form used internally!)
e.g. the rule if (male(X) and parent(X,Y)) then father(X,Y)
:- is implication in prolog, but we list the conclusion before the operator, and follow with the conditions allowing the implication
In Prolog this would look like: father(X,Y) :- male(X), parent(X,Y).
This reverse notation is used because prolog cares about the goal we’re looking for, so things concluding in that are easy to find
In a logical system (not in clause form) what would we have to do to X and Y?
They would have to be universally quantified…
© 2020 J.E. Anderson
The comma indicates an AND operation 10 © 2020 J.E. Anderson
male(bill).
father(X,Y) :- male(X), parent(X,Y).
programmer must explicitly define all possible
…..
fact relations male(bill).
father(bill,sally).
female(sally).
parent(bill, sally). parent(jane, sally). father(bill, sally). mother(jane,sally). sister(jane,sue). aunt(sue,sally). sister_in_law(bill,sue). …
Deductions
Prolog
Prolog can make deductions by unifying variables and constants much as we did by hand:
parent(bill,sally).
Prolog can also be used to mimic propositional logic if we remove the use of variables
11 © 2020 J.E. Anderson
12 © 2020 J.E. Anderson
9
not terribly interesting then though: the
male(bill). female(sally). parent(bill, sally). parent(jane, sally). parent(jill, jane). parent(jill, sue).
variable: first letter upper case; represents a generic object or symbol
% comment to end of line /* arbitrary comment */
male(bill).
female(sally).
parent(bill,sally).
father(X,Y):- male(X), parent(X,Y).
Prolog
Prolog Syntax
If facts and rules are used, then only a small set of base base facts are required, e.g. parent and gender
constant: first letter lower case; represents a specific object or symbol
The additional information is then defined using rules father(X,Y) :- male(X), parent(X,Y).
Connectives
Prolog Program
:- implies (i.e. conclusion first) ; OR
, AND
. end-of-statement
Prolog programs are stored in text files and can be edited by any simple text editor
13 © 2020 J.E. Anderson
14 © 2020 J.E. Anderson
15 © 2020 J.E. Anderson
16 © 2020 J.E. Anderson
Amzi prolog and swi-prolog both have complete environments for editing
predicate: lower case; defines a fact about an object or a relationship between/among objects
Using Prolog
Using Prolog
The standard prompt in most versions of Prolog is ?-
The Prolog system is terminated using the halt command: ?- halt. (AMZI: ?- quit.)
• actually the operator for making a query – in some you have to type it
Prolog source files may include an extension
• In those where it’s the prompt everything you type there has to be a query
Unix (sb) prolog does not require an extension
The Prolog source file is loaded into the Prolog system using the consult command
?- consult(test).
?- consult(‘test.pro’).
?- consult(myfile). (single quotes around filename in sb-prolog; it’s a menu choice in amzi)
Amzi prolog uses the extension .pro to associate the source file with the ALE (Amzi Logic Explorer) system
• You’re actually giving the system a goal to consult the file (shades of procedural coding!) 17
Swi-prolog uses .pl for the extension
18 © 2020 J.E. Anderson
Editing Files
Amzi Prolog Basics
If you aren’t using an IDE-based prolog, use a couple of terminal sessions to allow you to switch from Prolog to the editor to make changes to the source file
Open it up
start a listener: Select the Start command
Save the source file before returning to Prolog, then consult the file again
Consult consults a file of prolog code
There is a reconsult that is supposed to erase old predicates and put in new ones, but it is flaky in sb-prolog
halt. kills the listener but does not stop the system
© 2020 J.E. Anderson
19 © 2020 J.E. Anderson
20 © 2020 J.E. Anderson
from the Listener menu
Use the file exit menu command to stop the system
% prolog
?- consult(filename). ?- halt.
The system will give you warnings if all your predicates of one type do not appear together in the source file. Do not worry about this.
Unix Prolog Basics
Swi-Prolog basics
Gnu Prolog is available on some cc Unix
Run the application; edit brings up the editing environment
systems: ccl.cc.umanitoba.ca for certain (possibly
others)
Consult consults the file of your choice; within the editing environment, you can consult the current editing window (buffer) or a selection of it.
Use an X-windows terminal/vnc session to edit the source file and run Prolog at the same time, or open up two separate terminal sessions using a terminal emulator
Type queries after the ?- prompt in the main window
Remember to save the source before consulting again when you make changes
Exit from the file menu when done (no halt)
© 2020 J.E. Anderson
Making Queries in Prolog
Asking Questions
Prolog can answer questions concerning the symbols and symbol expressions that have been defined
?- father(bill,sally).
Assume we have our earlier facts and rules encoded in Prolog, and ask:
Prolog examines the facts and can not find the explicit fact that indicates that bill is the father of sally
?- male(bill).
However, there is a rule that permits Prolog to conclude that bill is the father of sally
Is bill male?
Prolog examines the facts using resolution and responds with YES or NO (T/F in SWI)
Prolog responds with YES
In this case, the answer is YES
In SWI, you may have to type a . to get the next
query prompt (the reason will be clear soon)
21 © 2020 J.E. Anderson
22
23 © 2020 J.E. Anderson
24 © 2020 J.E. Anderson
Is bill the father of sally?
?- male(sally). Is sally male?
?- father(Name,sally).
No.
Name is a variable that does not have a value (i.e. it is unbound)
Asking Questions
Instantiation
Prolog can not find a fact or a rule that indicates that Sally is male so Prolog concludes that the answer is No.
Prolog is able to find a value for the variable Name (Name is instantiated) that causes the statement to be true
Name = bill.
Note that Prolog does not prove that male(sally) is not true – No only means it couldn’t be proven given the knowledge in the system
If there is no value that causes the statement to be true, Prolog returns the value No
Instantiation and the Anonymous V ariable
Expressions
Who has bill as a father? ?-father(bill,Name).
Name = sally.
Who is Sally’s grandfather?
I can make this query using the rules already
• prolog returns the substitution required to unify the solution with your query
in the system if I want to:
Does bill have a child? ?-father(bill, _).
Yes.
?- father(X,Y), father(Y,sally).
But it’s useful enough to use in a rule!
The underscore represents an “anonymous” variable that is instantiated by Prolog but the value is not displayed
Here you see that rules and queries can introduce intermediate variables
We use it when we don’t care about remembering what’s actually there, just if there’s something that fits or not!
Notice that this rule is incomplete – it
identifies only the paternal grandfather and ignores the maternal grandfather 28
© 2020 J.E. Anderson
© 2020 J.E. Anderson
27 © 2020 J.E. Anderson
© 2020 J.E. Anderson
Who is sally’s father?
25 26
grandfather(X,Z):- father(X,Y), father(Y,Z).
Two Possible Fixes
More than One Result
grandfather(X,Z):- (father(X,Y), father(Y,Z)); (father(X,Y), mother(Y,Z)).
In situations where more than one object can fit a query, prolog returns the first. We can force it to keep going using the or operator typed after the
Better:
grandfather(X,Z):- father(X,Y), parent(Y,Z). %mother/father should be connected to %the generic parent concept
father(X,Y) :- male(X), parent(X,Y). mother(X,Y) :- female(X), parent(X,Y).
result: In a file we consult… parent(jill,jane).
The query now becomes:
?- grandfather(Name,sally).
29 © 2020 J.E. Anderson
A=jane, B=joe;
A=joe, B=jane;
A=jane, B=jane;
A=joe, B=joe
–To stop the search, type . Instead of ;
30 © 2020 J.E. Anderson
More than One Result
Facts that Change
You can see that prolog doesn’t care about cases where the same object can fill more than one variable (it’s looking for anything that unifies!)
The basic facts are permanently true
That’s because we haven’t told it to care – it doesn’t know that you can’t be your own sibling
Some information is temporal – true for a particular period in time
We have to tell it:
If the marriage were to end, how would this knowledge be represented?
sibling(X,Y):- parent(Z,X), parent(Z,Y), X\=Y.
• \= is not the same as not-equal – it says that X and Y do not unify – i.e. don’t match, can’t be bound to the same object. = is unification.
31 © 2020 J.E. Anderson
32 © 2020 J.E. Anderson
parent(jill,joe).
sibling(X,Y):- parent(Z,X), parent(Z,Y). ?- sibling(A,B).
married(bill, jane).
Facts that Change
Temporal Knowledge
married(bill, jane). divorced(bill, jane). ?- married(bill, jane). Yes
married(bill, jane).
divorced(bill, jane).
married(bill, sue).
currently_married(X,Y) :- married(X,Y), not divorced(X,Y). ?- currently_married(bill, jane).
This does not capture the fact that married and divorced are mutually exclusive concepts
No.
?- currently_married(bill, sue). Yes.
Prolog will manipulate symbols any way it possibly can, and so we need to capture all the desired nuances
This is one way of dealing with a knowledge representation problem – there are many specifics missing (when did they change from being married to not?) but it gives you the general idea
Temporal Knowledge
Non-Monotonic Systems
married(bill, sue, date_start).
married(bill, jane, date_start, date_end). currently_married(X,Y) :- married(X, Y, Date_start).
Prolog as we have seen it thus far is a monotonic system – facts are added but never removed (monotonic = monotone increasing = consistently increasing, never decreasing)
• this rule works if when a couple becomes divorced, the 3-parameter predicate is replaced by the 4-parameter predicate
To properly reflect real life we need non- monotonic features – the ability to remove facts as well as add them
• They’d both exist, we’d just have to know and look for the 4-parameter predicate first
Non-monotonic systems are difficult to manage, because what is deduced as true may not be a moment later if a supporting fact is removed
• This gives you a taste of some of the awkwardness we find in Prolog sometimes!
Here we are dancing around that logically, by
33 © 2020 J.E. Anderson
34 © 2020 J.E. Anderson
35 © 2020 J.E. Anderson
handling change in a monotonic way 36 © 2020 J.E. Anderson
Some Prolog Don’ts
More Prolog Don’ts
Do not nest predicates: parent(parent(X,Y),Z) :- …
Do not use “not” to left of the :- not female(X,Y) :- …
Do not place more than one term to the left of the implication ( :- )
“not” in prolog is not a boolean not, as we’ll see, and this can also cause problems
parent(X,Y),father(X,Y):-
There are always ways around these!
A(X,Y) :- …
We can’t quantify over predicates (FOL!)
Prolog’s Search
Prolog’s Search
Prolog begins with our goal – it looks for the goal itself or rules concluding in our goal and then attempts to prove the preconditions of those rules
That’s why we have code that looks like this:
This is done in a depth-first manner, starting with the first rule (or fact) whose conclusion matches
(you originally saw this with an ‘or’ earlier)
In this way it will eventually search back to the initial facts we defined
If at some point it doesn’t find an initial fact, it will hit a dead end – a state that is not the goal state and to which no more rules can be applied
If this fails, back up and try to find a different rule for concluding grandparent, and test its clauses
In this case, Prolog backtracks to the last choice
point and makes the next available choice (applies
the next applicable rule) 39
all cases tested with no success? Answer is No. The system will look at facts before rules
37 © 2020 J.E. Anderson
38 © 2020 J.E. Anderson
© 2020 J.E. Anderson
40 © 2016 J.E. Anderson
Do not use a variable as a predicate name
These are two different cases of someone being a grandfather. If we ask if X is Y’s grandfather, the first rule is tried and we see if we can prove the two father clauses
grandfather(X,Z):- father(X,Y), father(Y,Z).
grandfather(X,Z):- father(X,Y), mother(Y,Z).
Prolog’s Search
Recursion
Supposewewantedanancestorpredicate?
Apersonwhoistheparentofsomeoneis
Apersonwhoistheancestorofanancestor is also an ancestor
that person’s ancestor ancestor(X,Y):- parent(X,Y).
ancestor(X,Y) :- ancestor(X,Z), ancestor(Z,Y).
There’s clearly more to it than this though, because we can go back to their parents and so on:
While this rule is logically correct, this does not work with Prolog
A better way to think of it…
Following the Recursion
A person who is the ancestor of a parent is also an ancestor
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y). parent(richard,mary). parent(mary,john).
ancestor(X,Y):- ancestor(X,Z), parent(Z,Y).
?-ancestor(richard,X).
Will try first rule, and for this, needs to prove parent(richard,X).
This rule on its own works in some cases but goes on infinitely in other cases
Finds parent(richard,mary) and returns Y=mary
The correct definition is:
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
Typing ; causes it to go to the second rule, where it now needs to find parent(richard,Z). Again finds parent(richard,mary), and now must find ancestor(mary,Y).
Why? Think of how Prolog would use these in its search!
This is just one level of recursion – there may of course be very many
41 © 2020 J.E. Anderson
42 © 2020 J.E. Anderson
43 © 2020 J.E. Anderson
What if the order of the rules were reversed?
44 © 2020 J.E. Anderson
Prolog’s depth first search causes an infinite recursion – there’s nothing to stop this same rule from being applied over and over forever.
Searching for ancestor(mary,Y) is recursive – we start again, find the first rule, and need to find parent(mary,Y). Find parent(mary,john) and return Y=john.
Recursion
Forcing Backtracking
The termination condition must be defined first (as it would in procedural code!)
Recall that you can type ; (or) after a query result to tell prolog to keep going:
In general, a predicate may have any number of definitions; Prolog examines them in a depth-first manner in the order in which we defined them
?-grandfather(Name,sally). Name=fred ;
Name=joe ;
No.
In some systems (seems to be the case in swi- prolog), ancestor is a system predicate, so be careful of the name you choose (use ancestor_of or something like that)
What you’re really doing here is forcing prolog to backtrack – making it treat the solution it found as if it were a dead end.
some versions of prolog (gnu) force you to place
all definitions of a predicate together by giving
you an error rather than a warning (like swi does)
– be careful! © 2020 J.E. Anderson
“no” is returned last because looking for more
Your ; response
Output
Is actually manually causing the search to fail – it’s saying ignore what you found so far, and try to find something else
The write() predicate can be used to display values on the monitor
This behaviour is sometimes useful to reproduce internally. For example…
You can insert blank spaces using the tab(n) predicate where n is the number of blanks
47 © 2020 J.E. Anderson
48 © 2020 J.E. Anderson
45
at that point causes the search to fail 46 © 2020 J.E. Anderson
display_a_person :- person(X), write(X).
The nl predicate generates a carriage return to the next line
What if we want to print out all persons?
them, but we want them all at once
not does not mean logical negation – instead, it causes a predicate to fail if what the not is given succeeds, and vice versa
Output
One more thing to be careful of
display_all_persons:- person(X), write(X),nl.
We could keep typing ; and eventually we’d get
Using NOT
display_all_persons:- person(X),write(X),nl, fail.
fail is a system predicate that causes the rule to fail at that point – we’ve already written a value out, but prolog then fails and backtracks to try to find its goal another way
sounds the same but it isn’t…consider:
Prolog finds another binding for person, prints the object, fails, etc.
and parent(bill,sue). parent(mary,sue).
The trouble with not…
End of Prolog Intro
Now suppose I ask ?-mother(X,sue).
I get NO
mother(X,Y):-not(father(X,Y)),parent(X,Y).
but more to come!
• father(X,sue) succeeds (X=bill) • So not(father(bill,X)) fails
• …so the rule fails!
This rule is semantically stating that X is sue’s mother if sue has no father and X is sue’s parent
That isn’t what we intended, but it’s what the semantics of ‘not’ give us in a query with an
52 © 2020 J.E. Anderson
unbound X
51 © 2020 J.E. Anderson
49 © 2020 J.E. Anderson
50 © 2020 J.E. Anderson
mother(X,Y):-not(father(X,Y)),parent(X,Y).
and assume I have: father(X,Y):-parent(X,Y),male(X).
male(bill).
female(sue).
time in a recursive manner
53 © 2020 J.E. Anderson
list constant (null) 54 © 2020 J.E. Anderson
Prolog Lists
Matching Lists
A Prolog list is a collection of object constants separated by commas and enclosed in [ ] brackets
[H | T], where H and T are variables. | splits a list
[george, sam, jane]
An empty list consists of
A list may contain sublists arbitrarily deep
The first element in the list (the head) is bound to the variable before the | (H in this case). There has to be something for this to unify with – i. e. this will match only a list of at least one item
[ ]
This is how we build data structures in Prolog
The remaining elements in the list (the tail) are bound to the variable following the | (T in this case). The tail can be null, so this will still match to a one- item list.
[[a,b],c,[d]]
Prolog includes a special notation that permits the elements of a list to be extracted one at a
H & T can obviously be any variable name
List Example
Recursive List Example
process([H|T]):- write(H), nl, write(T). /*split head & tail, write head, write tail*/ ?- process([a,b,c]).
a
[b,c]
?- process([a]).
a
[]
?- process([]).
no. /*[H|T] won’t match to []!*/
The elements of a list can be printed recursively
55 © 2020 J.E. Anderson
56 © 2020 J.E. Anderson
if you specified [] you’d be talking about the empty
in fact because [H|T] separates off only one element (the head), we must process things recursively.
print_list([]). /*terminate on a null list*/ print_list([H|T]) :- write(H), print_list(T).
A Member relation
User-Defined Functions
We can define a member relation to determine whether or not the first argument is a member of the second argument (which must be a list)
The first parameter must appear at the “top level” of the second parameter
member(X, [X|_]).
member(X, [H|T]) :- member(X,T). ?- member(b,[a,b,c]).
yes.
?- member(e,[b,a,d]).
no.
?- member([a], [[b],[a],[d]]). yes.
?- member([a],[b,[d,[a]]]). no.
Lists: a Membership relation
Built-In List Producers
This version “returns” 1 or 0 rather than just letting prolog note success or failure
Prolog contains a special system predicate that can be used build a list of all objects that have a property
person_list(List):- bagof(Name,person(Name),List).
The concept of returning something doesn’t really work with predicates – but we can bind a 1 or a 0 to the third argument if it is a variable, which can be treated the same way
If an unbound variable is supplied in the third position, it is bound to a list of all objects that satisfy the predicate in the second position
member(X, [X|_], 1).
member(X, [], 0).
member(X, [H|T], R) :- member(X, T, R).
assuming we have person(george). person(sam). person(jane)., List gets bound to [george, sam, jane]
Using predicate arguments in this manner is very common in Prolog – the “caller” just has to supply
an unbound variable in that position 59
60 © 2020 J.E. Anderson
57 © 2020 J.E. Anderson
?- member(a, a). 58
© 2020 J.E. Anderson
With the member function, it is not necessary to ensure that the second parameter is a list – – if a parameter is not a list, it will not be unifiable because of the [Head|Tail]
no.
© 2020 J.E. Anderson
Bagof
Be careful with Bagof
person_list(List):-bagof(Name,person(Name),List).
When using the bagof (and setof) predicate, the internal predicate must either have only one parameter or, if there is more than one parameter, the additional parameter(s) must already be instantiated
When processing this statement, Prolog attempts to find bindings (instantiations) for Name that satisfy the predicate person(Name)
Its possible with some relations to have an item appear more than once (e.g. our problems with siblings!). So, there’s also setof, which has each element appearing only once
For example, attempting to determine the names of all parents using the statement below will not work correctly unless Child has already been instantiated by some earlier part of the rule/query. On its own this will NOT work:
For each such instantiation, Prolog adds the value of the variable Name to the variable List
Existential Quantifier
V ariables
However, Prolog supports a feature that is similar to the existential quantifier in first- order logic that eliminates the need for an additional predicate
Prolog does not support global variables
Variables that are instantiated in a rule remain
bagof(Name,Child^parent(Name,Child),List)
run:-bagof(Name, male(Name), List), write(List). %list is bound first, then written
This statement locates all people for which there is a parent-child relationship but ignores the child in each relationship (this is not the same as an anonymous variable)
If the value of a variable is required in another rule/predicate, the variable must be passed to or from the predicate as a parameter
61 © 2020 J.E. Anderson
62 © 2020 J.E. Anderson
63 © 2020 J.E. Anderson
run(List):-bagof(Name, male(Name), List). 64 © 2020 J.E. Anderson
X bagof(Name, parent(Name, Child), List)
X
instantiated for the duration of the rule
run:-bagof(Name, male(Name), List), print_list(List).
V ariables
V ariables
A variable can also be given a value (instantiated) directly, using the assignment operator (“is”)
If X had been instantiated to 4, then a subsequent X is 4 would have been successful (since X is 4, the is would succeed, it matches)
run:-X is 3, process(X).
Once a variable has been given a value, the value cannot be modified. If X has a value, this becomes normal unification, and is compared to the value supplied
If X had not been instantiated when process was called, the binding/assignment would have been successful
run:-X is 3, process(X). process(X):-X is 4.
?- run.
no.
run:-process(X), write(X). process(X):-X is 4.
?- run.
4
So X is X+4 will not change X!
Variables will still be made unbound when backtracking, but that is not the same as a traditional (imperative) assignment statement © 2020 J.E. Anderson
yes. 66 © 2020 J.E. Anderson
Variables
Another use of Fail
Since we can’t modify a variable, we have to assign a changed value to a new variable
Mary likes all animals except snakes
process(X,Y):-Y is X+4.
run:- X is 3, process(X,Y),
If X is a snake, then Mary does not like X; otherwise, if X is an animal, Mary likes X
animal(X):-snake(X).
write(X),tab(2), write(Y). ?- run.
37
yes.
likes(mary,X) :- snake(X), fail. likes(mary,X) :- animal(X).
67 © 2020 J.E. Anderson
• 2 interpretations, inconsistent! We want to it not just to fail, but to quit looking 68
65
This strategy does not work because Prolog will backtrack after the first rule fails, and use the second rule to deduce that Mary likes any snake, since snakes are animals
© 2020 J.E. Anderson
It is NOT always used with fail
The procedural knowledge defines how to solve problems in the domain
person(jack). person(sam). person(janet). likes(jack, janet).
?- friends(jack,janet).
Cut
Declarative/Procedural Knowledge
we can insert ! (cut) to tell prolog not to backtrack: likes(mary,X) :- snake(X) , !, fail.
Most Prolog programs for non-trivial applications will include both declarative knowledge and procedural knowledge
When you place a cut in a rule, it tells prolog not to backtrack on anything to the left of it
The declarative knowledge defines what is known about the problem domain
If there’s stuff to prove to the right of it, backtracking will still occur in these clauses though
For example, procedural knowledge might define how to retrieve knowledge so that duplicates are removed
• So it doesn’t have to appear at the end of a rule, even though you see it there a lot!
Good programming practice to keep the two types
Example
Deductions
Jack is a person.
Sam and Janet are also persons.
Jack likes Janet.
Friends are people who like each other. friends(X,Y):- likes(X,Y),likes(Y,X),
69 © 2020 J.E. Anderson
of knowledge separate 70 © 2020 J.E. Anderson
71 © 2020 J.E. Anderson
• No info about Janet liking Jack here!
© 2020 J.E. Anderson
no.
person(X), person(Y), X\=Y.
Prolog can make deductions only if all of the necessary knowledge has been defined
72
Jack is married to Janet. married(jack,janet).
One solution is to narrow the scope and assume that order indicates gender (e.g. the first participant is male)
Deductions
Deductions
likes(jack,janet).
friends(X,Y):- likes(X,Y),likes(Y,X), X\=Y. friends(jack,janet).
?- likes(jack,janet).
yes.
?- likes(janet,jack).
no.
In general, do not define facts with predicates that are also used as the conclusions to rules: something should either be defined as a fact or deduced, not both (modularity)
Prolog cannot (and should not) conclude that the premises are true even if the conclusion is true
Prolog can then conclude: friends(jack,janet).
Another Example
Fixing This
You may have defined relationships where you wanted either marriage participant in the 1st posn ?- married(janet,jack).
You can then move out a level and define the state of marriage non-recursively:
no.
You likely then tried something like:
married_to(X,Y) :- male(X), married(X,Y); female(X), married(Y,X).
married(X,Y):-married(Y ,X).
This new predicate avoids loops but does generate duplicates
This creates an infinite loop
Note that this predicate is defined in terms of
Insisting on the correct use of the predicate is 75
the base predicate married 76 © 2020 J.E. Anderson
the best practice
© 2020 J.E. Anderson
73 © 2020 J.E. Anderson
Prolog can also conclude: friends(janet,jack).
74 © 2020 J.E. Anderson
Instead of adding a friends fact, add the fact: likes(janet,jack).
Fixing This (2)
Built-in Functions
You can also move out a level by deriving marriage as opposed to stating it as a fact: married(X,Y):-wife(X,Y). married(X,Y):-wife(Y ,X). married(X,Y):-husband(X,Y). married(X,Y):-husband(Y ,X).
Prolog contains a variety of built-in functions
i.e., married is now derived and all facts are in terms of husband/wife (or h/h, w/w)
• var(X) returns true if X is not currently bound to a value
You need to maintain a pair of facts but there is no longer a gender assumption
These are useful when you know that supplying an unbound variable will cause problems to a definition, or where there is an easier way to calculate something depending on which variables are bound
This will still generate duplicates but not infinite recursion when using married © 2020 J.E. Anderson
• Loads of these: look them up! 78 © 2020 J.E. Anderson
User-Defined Functions
User-Defined Functions
If you want to declare your own functions, define them using meaningful predicates
Weirdness: for example, min(3, 4, 4) is true !?
min(X,Y,Z) :- X