Learn prolog exercise 2.3

Question

Im going thru the learn prolog website to try to learn some prolog and are trying to under stand exercise 2.3. I guess every call to word() goes one down into some sort of stack or so and that would explain why it seems to change the words from the end back to the beginning. But how come that it goes back down again if it changes one of the words a bit up?

Like:

a criminal eats a criminal

a criminal eats a big kahuna burger

a criminal eats every criminal

a criminal eats every big kahuna burger

word(article,a).
word(article,every).
word(noun,criminal).
word(noun,'big kahuna burger').
word(verb,eats).
word(verb,likes).

sentence(Word1,Word2,Word3,Word4,Word5) :-
    word(article,Word1),
    word(noun,Word2),
    word(verb,Word3),
    word(article,Word4),
    word(noun,Word5).

Then an swi-prolog question is it possible to get it to say yes/no instead of true/false?

Best Regards Anders Olme

Answer 1

Let me expand a bit on what starblue said.

Logically, this program says that any set of five things is a sentence if the first thing is an article, the second thing is a noun, the third thing is a verb, the fourth thing is another article and the fifth thing is another noun. The magic of Prolog is that you don't have to tell it how to get the answer, such as "try every article for the first word, then loop trying every noun for the second word, and so forth"; instead you just state your problem declaratively (the first word is an article, etc.) and Prolog will figure it out. So as long as your question is stated logically, you should (eventually) get every possible valid answer.

Because Prolog runs on an actual computer though, it must have an actual strategy for finding the answers, and that strategy is depth first search: it binds each variable in turn, trying every possibility until it can unify that variable, then it moves on to the next variable. When you ask for the next solution, it backs up to the last unification that had other possibilities and tries to find another one that satisfies the predicate. This is why the generated sentences come out in the order they did: word 5 unified last, so when Prolog backs up, it retries word 5. When it exhausts all the possible unifications for word 5, it backs up to word 4 and then moves forward again to word 5. So it will eventually try every possibility for all five words. If you don't like the order in which it's trying, you can change the order in which you bind the variables. For example, if you want it to retry the first word, then the second, you could rewrite the program to this:

sentence(Word1,Word2,Word3,Word4,Word5) :-
    word(noun,Word5),
    word(article,Word4),
    word(verb,Word3),
    word(noun,Word2),
    word(article,Word1).

?- sentence(X,Y,Z,Q,A), write([X,Y,Z,Q,A]).
[a,criminal,eats,a,criminal] ;
[every,criminal,eats,a,criminal] ;
[a,big kahuna burger,eats,a,criminal]

True to your expectation, this is being managed internally by a stack. Most modern Prologs are implemented with a technique called the WAM, the Warren Abstract Machine. The WAM is like most other programming language virtual machines in that there is a call stack, but there's also a second stack called the trail which it pushes variables onto at each binding. Backtracking then works by popping the last variable off the trail and trying to unify it and resume from there. If there is no other unification for this variable, it pops another variable off the stack and backs up further. When Prolog runs out of trail, it simply returns false, because no binding was possible.