About Prolog
. Facts. A fact is a basic assertion about some world. (Babe is a pig; pigs like mud.)
. Rules. A rule is an inference about the facts in that world. (An animal likes mud if it is a pig.)
. Query. A query is a question about that world. (Does Babe like mud?)
Basic Facts
In some languages, capitalization is entirely at the programmer’s discretion,
but in Prolog, the case of the first letter is significant. If a word
begins with a lowercase character, it’s an atom—a fixed value like a
Ruby symbol. If it begins with an uppercase letter or an underscore,
it’s a variable. Vari abl e values can change; atoms can’t. Let’s build a
simple knowledge base with a few facts. Key the following into an editor:
Download prolog/friends.pl
likes(wallace, cheese).
likes(grommit, cheese).
likes(wendolene, sheep).
friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z).
| ?- likes(wallace, sheep).
no
| ?- likes(grommit, cheese).
yes
Basic Inferences and Variables
| ?- friend(wallace, wallace).
no
| ?- friend(grommit, wallace).
yes
| ?- friend(wallace, grommit).
yes
| ?- friend(wendolene, grommit).
no
Filling in the Blanks
| ?- ['code/prolog/food.pl'].
food_type(velveeta, cheese).
food_type(ritz, cracker).
food_type(spam, meat).
food_type(sausage, meat).
food_type(jolt, soda).
food_type(twinkie, dessert).
flavor(sweet, dessert).
flavor(savory, meat).
flavor(savory, cheese).
flavor(sweet, soda).
food_flavor(X, Y) :- food_type(X, Z), flavor(Y, Z).
| ?- food_type(What, meat).
What = spam ?;
What = sausage ?;
no
| ?- food_flavor(sausage, sweet).
no
| ?- flavor(sweet, What).
What = dessert ?;
What = soda
yes
| ?- food_flavor(What, savory).
What = velveeta ?;
What = spam ?;
What = sausage ? ;
no
Map Coloring
different(red, green). different(red, blue).
different(green, red). different(green, blue).
different(blue, red). different(blue, green).
coloring(Alabama, Mississippi, Georgia, Tennessee, Florida) :-
different(Mississippi, Tennessee),
different(Mississippi, Alabama),
different(Alabama, Tennessee),
different(Alabama, Mississippi),
different(Alabama, Georgia),
different(Alabama, Florida),
different(Georgia, Florida),
different(Georgia, Tennessee).
| ?- coloring(Alabama, Mississippi, Georgia, Tennessee, Florida).
Alabama = blue
Florida = green
Georgia = red
Mississippi = red
Tennessee = green?
…
Unification, Part 1
Download prolog/ohmy.pl
cat(lion).
cat(tiger).
dorothy(X, Y, Z) :- X + lion, Y = tiger, Z bear.
twin_cats(X, Y) :- cat(X), cat(Y).
| ?- dorothy(lion, tiger, bear).
yes
| ?- dorothy(One, Two, Three).
One = lion
Three = bear
Two = tiger
yes
| ?- twin_cats(One, Two).
One = lion
Two = lion?
…
1. We issued the query twin_cats(One, Two) . Prolog binds One to X and Two to Y. To solve these, Prolog must start working through the goals.
2. The first goal is cat(X).
3. We have two facts that match, cat(lion) and cat(tiger). Prolog tries the first fact, binding X to lion, and moves on to the next goal.
4. Prolog now binds Y to cat(Y). Prolog can solve this goal in exactly the same way as the first, choosing lion.
5. We’ ve satisfied both goals, so the rule is successful. Prolog reports the values of One and Two that made it successful and reports yes.
Two = lion ?a
One = lion
Two = tiger
One = tiger
Two = lion
One = tiger
Two = tiger
(1 ms) yes
Recursion
Download prolog/family.pl
father(zeb, john_boy_sr).
father(john_boy_sr, john_boy_jr).
ancestor(X, Y) :-
father(X, Y).
ancestor(X, Y) :-
father(X, Z), ancestor(Z, Y).
| ?- ancestor(john_boy_sr, john_boy_jr).
true ?
no
| ?- ancestor(zeb, john_boy_jr).
true?
| ?- ancestor(zeb, Who).
Who = john_boy_sr ? a
Who = john_boy_jr
no
| ?- ancestor(Who, john_boy_jr).
Who = john_boy_sr ? a
Who = zeb
(1 ms) no
Lists and Tupl es
Unification, Part 2
| ?- (1, 2, 3) = (1, 2, 3).
yes
| ?- (1, 2, 3) = (1, 2, 3, 4).
no
| ?- (1, 2, 3) = (3, 2, 1).
no
| ?- (A, B, C) = (1, 2, 3).
A =1
B =2
C = 3
yes
| ?- (1, 2, 3) = (A, B, C).
A =1
B =2
C = 3
yes
| ?- (A, 2, C) = (1, B, 3).
A =1
B =2
C = 3
yes
| ?- [1, 2, 3] = [1, 2, 3].
yes
| ?- [1, 2, 3] = [X, Y, Z].
X =1
Y =2
Z = 3
yes
| ?- [2, 2, 3] = [X, X, Z].
X =2
Z = 3
yes
| ?- [1, 2, 3] = [X, X, Z].
no
| ?- [] = [].
| ?- [a, b, c] = [Head|Tail].
Head =a
Tail = [b,c]
yes
| ?- [] = [Head|Tail].
no
| ?- [a] = [Head|Tail].
Head =a
Tail = []
yes
| ?- [a, b, c] = [a|Tail].
Tail = [b,c]
(1 ms) yes
| ?- [a, b, c] = [a|[Head|Tail]].
Head =b
Tail = [c]
yes
Lists and Math
list_math.pl
count(0, []).
count(Count, [Head|Tail]) :- count(TailCount, Tail), Count is TailCount + 1.
sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum, Tail), Total is Head + Sum.
average(Average, List) :- sum(Sum, List), count(Count, List), Average is Sum/Count
| ?- count(What, [1]).
What = 1 ? ;
no
sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum, Tail), Total is Head + Sum.
| ?- sum(What, [1, 2, 3]).
What = 6 ? ;
no
Using Rules in Both Directions
| ?- append([oil], [water], [oil, water]).
yes
| ?- append([oil], [water], [oil, slick]).
no
| ?- append([tiny], [bubbles], What).
What = [tiny,bubbles]
yes
| ?- append([dessert_topping], Who, [dessert_topping, floor_wax]).
Who = [floor_wax]
yes
| ?- append(One, Two, [apples, oranges, bananas]).
One = []
Two = [apples,oranges,bananas] ? a
One = [apples]
Two = [oranges,bananas]
One = [apples,oranges]
Two = [bananas]
One = [apples,oranges,bananas]
Two = []
(1 ms) no
1. Write a rule called concatenate(List1, List2, List3) that can concatenate
an empty list to List1.
2. Add a rule that concatenates one item from List1 onto List2.
3. Add a rule that concatenates two and three items from List1 onto
List2.
prolog/concat_step_1.pl
| ?- concatenate([], [harry], What).
What = [harry]
yes
prolog/concat_step_2.pl
concatenate([], List, List).
concatenate([Head|[]], List, [Head|List]).
| ?- concatenate([malfoy], [potter], What).
What = [malfoy,potter]
yes
prolog/concat_step_3.pl
concatenate([], List, List).
concatenate([Head|[]], List, [Head|List]).
concatenate([Head1|[Head2|[]]], List, [Head1, Head2|List]).
concatenate([Head1|[Head2|[Head3|[]]]], List, [Head1, Head2, Head3|List]).
| ?- concatenate([malfoy, granger], [potter], What).
What = [malfoy,granger,potter]
yes
prolog/concat.pl
concatenate([], List, List).
concatenate([Head|Tail1], List, [Head|Tail2]) :-
concatenate(Tail1, List, Tail2).
. Start with this:
concatenate([1, 2], [3], What)
. The first rule doesn’t apply, because [1, 2] is not an empty list. We
unify to this:
concatenate([1|[2]], [3], [1| T ail 2- A]) :- concatenate([2], [3], [ T ail 2- A])
Everything unifies but the second tail. We now move on to the
goals. Let’s unify the right side.
. We try to apply the rule concatenate([2], [3], [ T ail 2- A]). That’s going to
give us this:
concatenate([2|[ ]], [3], [2| T ail 2- B ]) :- concatenate([ ], [3],T ail 2- B)
Notice thatT ail 2- B is the tail ofT ail 2- A. It’s not the same as the originalT
ail 2 . But now, we have to unify the right side again.
. concatenate([ ], [3],T ail 2- C) :- concatenate([ ], [3], [3]) .
. So, we knowT ail 2- C is [3]. Now, we can work back up the chain.
Let’s look at the third parameter, plugging inT ail 2 at each step.
T ail 2- C is [3], which means [2| T ail 2- 2 ] is [2, 3], and finally [1| T ail 2 ] is [1,
2, 3]. What is [1, 2, 3].