I am having trouble following the trace function in Prolog.

Question

I am new to Prolog and computer programming in general. I have been going through the exercises in Learn Prolog Now! and have been getting along alright but occasionally, when I do run into difficulty, I attempt to use the trace function to follow the program line for line and see how it is working or what is going wrong but I can't make heads or tails of what is being listed by trace. I'll give an example...

One of the exercises was to fill out a crossword grid with a predicate crossword/6. These are all the facts and rules in the answer:

 word(abalone,a,b,a,l,o,n,e).
 word(abandon,a,b,a,n,d,o,n).
 word(enhance,e,n,h,a,n,c,e).
 word(anagram,a,n,a,g,r,a,m).
 word(connect,c,o,n,n,e,c,t).
 word(elegant,e,l,e,g,a,n,t).

crossword(V1,V2,V3,H1,H2,H3):-
word(H1,_,H12V12,_,H14V22,_,H16V32,_),
word(H2,_,H22V14,_,H24V24,_,H26V34,_),
word(H3,_,H32V16,_,H34V26,_,H36V36,_),

word(V1,_,H12V12,_,H22V14,_,H32V16,_),
word(V2,_,H14V22,_,H24V24,_,H34V26,_),
word(V3,_,H16V32,_,H26V34,_,H36V36,_).

This works just fine. But I wanted to know how it worked, I wanted to see how the computer works its way through the rules step by step. So I used trace on the query crossword(V1,V2,V3,H1,H2,H3). What follows are just the first ten line or so of what is produced.

[trace]  ?- crossword(V1,V2,V3,H1,H2,H3).
  Call: (8) crossword(_5238, _5240, _5242, _5244, _5246, _5248) ? creep
  Call: (9) word(_5244, _5658, _5660, _5662, _5664, _5666, _5668, _5670) ? creep
  Exit: (9) word(abalone, a, b, a, l, o, n, e) ? creep
  Call: (9) word(_5246, _5658, _5660, _5662, _5664, _5666, _5668, _5670) ? creep
  Exit: (9) word(abalone, a, b, a, l, o, n, e) ? creep
  Call: (9) word(_5248, _5658, _5660, _5662, _5664, _5666, _5668, _5670) ? creep
  Exit: (9) word(abalone, a, b, a, l, o, n, e) ? creep
  Call: (9) word(_5238, _5658, b, _5662, b, _5666, b, _5670) ? creep
  Fail: (9) word(_5238, _5658, b, _5662, b, _5666, b, _5670) ? creep
  Redo: (9) word(_5248, _5658, _5660, _5662, _5664, _5666, _5668, _5670) ? creep
  Exit: (9) word(abandon, a, b, a, n, d, o, n) ? creep
  Call: (9) word(_5238, _5658, b, _5662, b, _5666, b, _5670) ? creep
  Fail: (9) word(_5238, _5658, b, _5662, b, _5666, b, _5670) ? creep

I know that the first line is just a restatement of the query but with the variables changed into arbitrary numbers. Then it goes to the first goal of the rule, and again, the variables are simply instantiated as arbitrary numbers. This goal sends the program to the first fact in the database, namely word(abalone,a,b,a,l,o,n,e).

Now is where I start to get confused. Why is the next line after that, the first goal again, but with the first variable changed from _5244 to _5246? Then I get an Exit: word(abalone,a,b,a,l,o,n,e) - by the way, I'm not sure what Call: and Exit: mean exactly either - followed again by the same line but with the first variable changed from _5246 to _5248. What is going on here? Why are all the other variables constant and just the first one is changing?

A little further down I get even more baffled. With the line Call: (9) word(_5238, _5658, b, _5662, b, _5666, b, _5670) ? creep, where are the b's coming from and why are there three of them? I figured the first one is there because it is the second letter of abalone, thus filling that spot in the crossword, but why are the next two b's there? Shouldn't they be 'l' and 'n'?

I realize that this is probably very simple to someone who understands Prolog well but I have no idea what is going on. And that is a problem because the trace function is probably the single most useful tool in learning Prolog. If I can't use it and understand it then I won't be able to check how things work along the way as I learn. If anyone is able to just clear this up for me and maybe suggest a way for me to get better at reading and understanding trace I would really appreciate it.

Taku Koyahata Taku Koyahata · Accepted Answer · 2018-02-19T03:21:15

If you are using SWI-Prolog, I recommend gtrace(type "gtrace." and call predicate)

_5238 means a Variable .

when you call word/6 , Variables are patternmatched to first candidate and a choice point is generated. in this case, assume 6(number of word/8 definitions) "or" sentenses are generated.

if pattenmatch is failed,prolog tryes next candidate. if pattenmatch is success,prolog goes to next line(and next choice points are generated) if all choices are failed, prolog goes back to previous choice point and try next candidates at the point(backtrack)

notice choice points are generated at each word/8 calling individually.

at all choice points, prolog remembers which candidate now testing.

and notice when backtrack occured , all variables at the choice point are become free(prolog variables are not permitted to be changed. either a value or free)

I am having trouble following the trace function in Prolog.

1 Answers