We are working with the following knowledge base:
house_elf(dobby).
witch(hermione).
witch('McGonagall').
witch(rita_skeeter).
magic(X):- house_elf(X).
magic(X):- wizard(X).
magic(X):- witch(X).
The question of the exercise was:
Which of the following queries are satisfied? Where relevant, give all the variable instantiations that lead to success.
I am stuck on question 5:
?- magic(Hermione).
Also draw the search tree for the query magic(Hermione) .
Although I understand what is kind of happening with the query, I am getting confused in how to draw a query search tree. Also the fact that that in our query (Hermione) is a variable is also leading to more confusion?
Would you please mind guiding me and explaining what goes on when this query is proposed to Prolog?
Thanks
Atoms versus Variables
A string starting with a capital letter, like, Hermione, is a variable. If it starts with a lower case letter, like hermione, it's an atom (think of it as a "constant" as in other languages). Or if it's in single quotes, like 'Hermione', it is also an atom.
The following is a fact:
witch(hermione).
It could be read: hermione is a witch. How it's really read (or more specifically, what it's semantic meaning is) is up to you, the programmer.
If I query this fact at the Prolog prompt, it will succeed:
| ?- witch(hermione).
yes
(Note, this is gprolog, so it yields yes. I think SWI Prolog would say true, but they both mean "success".)
I can also query with a variable, and Prolog will tell you what instantiations (settings) of the variable will make it true:
| ?- witch(Hermione).
Hermione = hermione ? ;
Hermione = 'McGonagall' ? ;
Hermione = rita_skeeter
(1 ms) yes
Remember: Hermione is a variable, and hermione is an atom. They are NOT the same thing. So the variable, Hermione can have any one of the above values to make witch(Hermione) be true. You could just as well queried, witch(Fred) and gotten the same results above with Fred instead of Hermione.
Basic Predicate Logic
Now let's look at the predicate, magic/1 (the 1 here indicates the arity, or how may arguments magic has):
magic(X):- house_elf(X).
magic(X):- wizard(X).
magic(X):- witch(X).
Semantically, you can read this as, X is magic if X is a house_elf, OR X is magic if X is a wizard, OR X is magic if X is a witch.
If we then query:
| ?- magic(Hermione).
Prolog will attempt to find out what instantiations of Hermione will make this succeed and tell you what those values are. In all of your facts and predicates, it will find the first match at the clause magic(X):- house_elf(X)., using Hermione as the variable in place of X, and it will find that if Hermione = dobby, then house_elf(Hermione) will be true, and, therefore, magic(Hermione) will be true. It will show that as the first solution: Hermione = dobby:
| ?- magic(Hermione).
Hermione = dobby ? ;
By pressing ; here (or SPACE), Prolog will try to find the next solution, and in this case it won't find the next success until it goes to the next clause, magic(X):- wizard(X).. Assuming you have some facts for wizard/1, it will succeed on those. If wizard/1 isn't defined in your facts or predicates, then you'll get an existence error from Prolog stating that it doesn't know what wizard/1. Prolog will keep walking through your predicate clauses, looking for ways to make it succeed, and telling you what value (instantiation) of Hermione will make it so until it has exhausted all the cases. Then it will finally stop.
I'll leave it as an exercise to figure out the search tree, but do a Google search on "Prolog search tree" to find some good examples. I assume you have Prolog interpreter in which you can enter your code and play with queries to see what happens. You can enable tracing (enter trace.) to see some details on what Prolog is doing on queries as well. All of these methods can help understanding of some aspects of Prolog operation.