plays(alice, leadguitar).
plays(noah, drums).
plays(mike, leadguitar).
plays(mike, drums).
plays(katie, baseguitar).
plays(drew, leadguitar).
plays(drew, baseguitar).
duetwith(Person1,Person2):-
plays(Person1,L),
plays(Person2,L),
Person1 \= Person2.
I write a new rule called combo that determines whether or not three people can make a combo with a drummer, a base guitar, and a lead guitar.
combo(Person1,Person2,Person3):-
plays(Person1,X),
plays(Person2,Y),
plays(Person3,Z),
X \= Y,
Y \= Z,
X\=Z.
Can drew, alice, and mike make a combo?
combo(mike,alice,drew).
true so the answer is yes they can make a combo.
I need help understanding the steps the program takes to answer the above query in prolog. Any help with a list of steps is greatly appreciated so I can gain a deeper understanding of each step Prolog takes.
Here is an example of a list of steps Prolog takes for a different example just to give an idea of what I am looking for.
In the case of talkswith(bob,allen), the engine took the following steps:
In
talkswith(Person1,Person2):- speaks(Person1,L), speaks(Person2,L), Person1 \= Person2.
replace every occurrence of Person1 with bob and Person2 with allen to get
talkswith(bob,allen) :-
speaks(bob,L),
speaks(allen,L),
bob \= allen.
Let’s see if we can find a value for L that makes the right side true. Start with
speaks(bob,L).What can L be? Here are our facts:- speaks(allen, russian).
- speaks(bob, english).
- speaks(mary, russian).
- speaks(mary, english).
In fact 1, the first slot isn’t bob, so that won’t work. In fact 2, the first slot is bob, so let’s try
L = englishinspeaks(allen,L), bob \= allen.Now we are askingspeaks(allen,english), bob\= allen.- Back to the knowledge base. Does
speaks(allen,english)match a fact? Not fact 1, not fact 2, not fact 3, not fact 4. This fails. - Now we back up to step 2. Fact 2 didn’t work out, so let’s try fact 3. No, that isn’t bob. Fact 4 isn’t bob either. We can’t find a value for L that works, so the search failed.
Prolog uses syntactic unification which never does replacement. A free variable can only be bound once to a value. If it looks like a variable is being changed more than once, it is not. There can be many stack frames and for each stack frame a new set of variables can be created.
For these facts
and this predicate
and this query
First read SWI-Prolog Debugging and Tracing Programs
Run the query with trace, unify port enabled and leashing off.
Prolog looks for a predicate that matches the query. When Prolog looks for a predicate it searches by predicate name, in this case
combo, and arity, in this case3and finds only one predicate with one clause. Prolog also searches for predicates in the order they appear in the source code. There is more to it (indexing) but that level of detail is not needed to explain this simple query.Once Prolog has found a clause/fact based on predicate name and arity it checks that the query and head of the clause or fact can be unified.
mikeunifies withPerson1.Person1is now bound tomike.aliceunifies withPerson2.Person2is now bound toalice.drewunifies withPerson3.Person3is now bound todrew.If the previous statement unifies, then the next statement is called. Each statement is a query in itself. So running the query
plays(mike,X).as a stand alone query is the same as this statement in the clause. There are many facts forplays/2and two of them matchplays(mike,X).Prolog uses the first one it finds, however since there are more than one, a choice point is made. We will call this specific choice pointplays(mike,X) - cp1and refer back a specific choice point when a corresponding REDO is encountered.Once Prolog has found a clause/fact based on predicate name and arity it checks that the query and head of the clause can be unified.
playsunifies withplaysmikeunifies withmike_7040unifies withleadguitar._7040is bound toleadguitar.This is just completing the ports of the Prolog box model. It shows the result of
Call: (9) plays(mike, _7040). No unification takes place for this statement.Same pattern for
alice. Alice has only one fact so not choice points generated for her.Same pattern for
drew. Since drew has two facts forplays(drew,X).a choice point is generated.plays(drew,X) - cp1This is the fourth statement
X \= YwithXis bound toleadguitarandYis bound toleadguitarSince
leadguitaris not different fromleadguitarthis query fails. Upon failure Prolog goes back to the last choice point (Redo) and tries to find another solution.Remember the last choice point created,
plays(drew,X) - cp1. Since something failed the query is tried with another possible solution. Since the first choice point forplays(drew,X)failed withXbeingleadguitar, the second fact is used,plays(drew,baseguitar).Just shows that the second fact for
plays(drew,X)is being used.It shows the result of
Redo: (9) plays(drew, _7040).The remainder is just more copy/paste of what has been done already and changing out the statements, variables, bound values, etc.
This answer is similar, but has more detail.
Of note is this question
is not answered by this query
because if these facts are added
this query
says true but
alice,noahandmikeare not playing the leadguitar, drums, and baseguitar.